[야매 알고리즘] B-tree(2)

야매 알고리즘?

알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다.

전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다.

 

B-tree의 특징

이전 글에서 B-tree의 특징과 장점, 그리고 B-tree를 왜 사용하는지에 대해 대략적으로 알아봤다. 하지만 대략적인 특징을 아는 것으로는 B-tree를 구현할 수 없다. 이 글에선 B-tree의 특징을 좀 더 디테일하게, 그리고 좀 더 전공자 느낌 나게 알아보겠다.

 

B-tree의 특징은 다음과 같다.

1. 자식 노드의 개수를 최대 M개 가질 수 있는 B-tree를 M차 B-tree라고 한다. (단 M >= 2)
2. Internal node (root도, leaf도 아닌 노드)는 최소 [M / 2] 개 이상, 최대 M 개 이하의 자식을 가진다.
3. 2번 특징에 의해 internal node는 최소 [M / 2] - 1 개 이상, 최대 M - 1 개 이하의 key를 가진다.
4. Leaf 노드는 최소 [(M - 1) / 2] 개 이상, 최대 M - 1 개 이하의 key를 가진다.
5. 노드의 key가 x개라면, 그 노드의 자식 노드 개수는 x + 1 개이다.
6. 각 노드에 들어있는 key는 정렬되어있다. 그리고 그 key 값이 자식 노드의 key 값의 범위를 분할한다.
7. Root 노드에서 모든 leaf 노드까지의 경로 상의 간선 개수가 동일하다. 즉 모든 leaf node의 level이 동일하다.
8. Root가 leaf 노드일 경우(B-tree에 다른 노드가 없는 경우), root 노드는 0개에서 n-1개 사이의 key를 가질 수 있다.
9. Root가 leaf 노드가 아닐 경우, 최소 두 개의 자식 노드를 가진다.

*Introduction to Algorithm 책을 참고하고 있지만, 책에서 설명하는 B-tree의 특징 중 하나인 최소 차수(minimum degree) 개념은 따로 설명하지도, 적용하지도 않으려고 한다. 최소 차수를 사용하지 않고도 위의 설명으로 B-tree를 정의내릴 수 있기 때문이다. 예를 들어 최소 차수 t가 2인 B-tree는 자식 노드를 2개에서 최대 4개 가질 수 있는 4차 B-tree라고 볼 수 있는데, 최고 차수 개념으로는 최대 자식 노드 개수가 2t개 이므로 4개, 6개, 8개 이렇게 짝수로 늘어난다. 그렇다고 해서 최소 차수 개념이 짝수 차수(예를 들어 4차, 6차, 8차...) B-tree만 설명할 수 있는 것이 아니다. 예를 들어 t = 2일 때 자식 노드가 최대 4개 이므로 3차 B-tree는 t = 2인 B-tree에 포함된(?) 개념이라고 볼 수 있다. 그냥 최대 key 개수를 4개가 아닌 3개로 제한하면 되기 때문이다 (각 노드의 key가 3개가 넘으면 노드를 split). 즉 최고 차수 t의 개념으로 설명하든, M차 B-tree로 설명하든지 상관 없는데, 내가 과제로 제출해야 하는 B-tree는 t가 아닌 M이 입력으로 들어오기 때문에 M차 B-tree의 개념으로 설명하겠다. 

 

**위키피디아(영문)과, Introduction to Algorithm 책을 살펴본 결과, 차수에 대한 개념 설명이 여러가지이다. Introduction to Algorithm 책에서는 Bayer와 MCCreight, Comer의 정의를 따르고, 내가 정리한 것은 Knuth의 정의인 것으로 보인다.

The literature on B-trees is not uniform in its terminology.Bayer and McCreight (1972), Comer (1979), and others define the order of B-tree as the minimum number of keys in a non-root node. points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. Knuth (1998) avoids the problem by defining the order to be the maximum number of children (which is one more than the maximum number of keys).

출처: https://en.wikipedia.org/wiki/B-tree