Binary Search Tree에는 균형이 깨질 수 있다는 치명적인 단점이 있었다. 균형을 어떻게 보완할 수 있었을까?

B-Tree

• 모든 리프 노드의 depth가 동일
• 하나의 노드 안에는 최대 m-1개의 데이터가 존재
• 자식 노드 수는 자신의 데이터 수보다 1많음
• 노드 당 자식 수는 [m/2] ~ m개
• 단일 노드 내에서 데이터는 정렬됨

이러한 조건을 만족할 때, m차 B-Tree라 한다.

삽입 데이터 수 제한을 넘어서는 경우: 리프 노드에 데이터가 삽입될 여유가 없을 경우, 가운데 데이터를 윗 레벨로 튕겨내는 과정을 반복한다. 이 과정에서 튕겨지는 데이터의 좌우 데이터는 분리되어 각각 노드를 형성하게 된다.

삭제 ?

play 삭제 시 데이터 정렬방법을 공부하고 파이썬으로 구현해보기.