0. M-way Search Tree (B-Tree)

1. 각 노드가 0~m개의 subtree를 지닌다.
2. 다음 4가지 B-tree Order 속성을 만족시킨다.

   • root node가 leaf이거나(트리 전체 노드 = 1개), 2~m개의 subtree를 지닌다.
   • ceiling(m/2) <= internal nodes의 subtree 수 <= m
   • 모든 leaf node가 동일한 level에 위치한다. (perfectly balanced tree)
   • ceiling(m/2) - 1 <= leaf node의 entry 수 <= m - 1

1. Operation

자세한 구현 방법은 추후 다른 post에서 다루며, 개념들에 대해서만 설명한다.

1-1. Insertion

point: 삽입되어야 할 위치의 Node가 꽉 찼다면(Overflow) 해당 array를 2개로 쪼개 확장한다.

그림에서 보이는 바와 같이 Order가 5인 Tree는 각 Node별로 최대 4개의 값을 저장할 수 있다. 그래서 97을 삽입할 때, 기존 node가 꽉 차있기 때문에 확장이 필요하다. 5개의 값 중 median 값을 부모 node로 추대하고 나머지 값들을 두 개의 node에 일정하게 나눈다.

이러한 삽입 방식 때문에 B-Tree 삽입의 경우 top-down 형태의 binary tree와 달리 점차 위로 성장하는(bottom-up) 형태를 띈다. B-Tree 삽입에 있어 핵심은 node가 꽉 찼을 때 새로운 노드를 생성하고, median 값을 부모 node로 보낸 후, split하는 것이라고 할 수 있다.

1-2. Deletion

point: insertion 때와 반대로 삭제 후 해당 node의 entry < 최소 엔트리( "ceiling(m/2)-1" )일 경우(Underflow) 옆의 sibling node에서 entry를 가져와 최소 엔트리 조건을 충족하도록 조정한다. 만약 sibling node도 최소 엔트리만을 가지고 있어, 엔트리를 가져올 수 없는 경우, 두 node를 병합한다. (Reflow 작업)

1-3. Traversal: inorder traversal 이용

1-4. Search

이진 트리와 달리 내려가야 할 pointer를 보유한 entry에 대한 정보를 return 받아야 한다. 이를 확인하기 위해 성적 구간 문제에서 일반적으로 활용하는 방식처럼 맨 끝에서부터 target value >= entry value 인지를 확인한다.

2. B-Tree Application