....
기초적인 B-트리(tree) 알고리즘의 변형과 성능을 논하기 이전에, B-트리 용어를 좀 더 형식적으로 기술하는 것이 필요하다. 차수(order)나 리프(leaf) 등과 같은 용어의 철저한 정의를 제공하는 것은 B-트리로 구분되기 위해 자료구조가 지녀야만 하는 성질을 설명할 수 있도록 한다.
다시 말해, B-트리의 성질에 대한 이러한 정의는 B-트리로부터 키를 삭제하는 절차와 같은 문제에 대한 논의를 할 수 있도록 한다.
불행하게도, B-트리에 관한 문헌은 B-트리와 관련된 용어를 이용하는데 있어 동일하지 않다. 그러므로 문헌을 읽고 새로운 개발을 하는 것은 약간의 융통성과 예비 지식을 필요로 한다. 독자는 기본적인 용어의 다른 사용에 대해서도 알 필요가 있다.
예를 들어, Bayer와 McCreight, Comer 그리고 몇몇 다른 학자들은 한 트리의 한 페이지 안에 있는 키들의 최소 개수를 B-트리의 차수라고 간주한다. 그러므로, 우리의 페이지 당 최대 4개의 키를 유지할 수 있는 초기 B-트리 예에서 이것이 Bayer와 McCreight의 표기에 따르면, 차수가 2가 된다. 이와 같이 차수에 대한 정의를 이용해서 만일 최대 키의 개수가 홀수개인 페이지에 대해 차수를 계산하려 한다면 문제가 발생한다. 예를 들어, 다음과 같은 질문을 생각해보자. Bayer와 McCreight의 구조에서, 차수가 3인 B-트리의 페이지는 6개의 키를 담고 있는 경우에 가득 차는가, 혹은 7개의 키를 담고 있는 경우 가득 차는가?
Knuth와 몇몇 학자들은 B-트리의 차수를 한 페이지가 가질 수 있는 자손(descendant)들의 최대 개수로 정의하여 위와 같이 홀 / 짝수에서 오는 혼동을 피하였다. 이러한 차수의 정의를 이 책에서는 계속 사용한다. Knuth의 정의는 Bayer의 정의와 2가지 측면에서 다르다. 즉, 최소가 아닌 최대를 참고하고, 다른 하나는 키보다는 자손들을 고려한다는 것이다.
B-트리의 페이지가 분할되는 경우, 자손들은 새로운 페이지와 오래된 페이지 사이에서 가능한한 균등하게 나뉘어진다. 즉, 루트와 리프 노드를 제외한 모든 페이지는 최소한 m / 2 개의 자손을 갖는다.
다른 저자에 의해서 사용되는 또다른 용어는 리프이다. Bayer와 McCreight는 B-트리에서 가장 낮은 키의 레벨을 리프 레벨로 간주한다. 이것은 이 책에서 사용한 용어와 일치한다. Knuth를 포함한 학자들은 B-트리의 리프들을 가장 낮은 레벨의 키보다 한 레벨 아래에 있다고 간주한다. 다시 말하면, 트리의 가장 낮은 레벨의 키에 의해 지시되는 실제 데이터 레코드를 리프로 생각하였다. 이 책에서는 이러한 정의를 사용하지 않고, B-트리 노드의 가장 낮은 레벨로써 리프의 표현을 사용한다.
마지막으로, 많은 저자들은 이 책의 B-트리에 대한 정의를 B+ 트리라고 부른다(B-Tree는 B 마이너스 트리가 아니다). B-트리란 용어는 오직 단말 노드에서만이 아니라, 모든 노드에서 데이터 레코드 참조를 가지는 B-트리의 버전에 종종 사용된다. 주된 차이점은 이 책의 버전은 단말 노드에 완전한 인덱스를 가지고 있고, 더 높은 레벨 인덱스일수록 내부 노드를 이용한다는 것이다. 이것은 내부 노드 내 각각의 키가 각각의 더 낮은 레벨에서 중복되기 때문에 키의 중복을 일으킨다. 다른 버전은 키의 중복을 제거하고 대신에 내부 노드에 데이터 레코드 참조를 포함한다. 이것은 공간과 검색 시간을 줄이는 것처럼 보이지만, 사실은 그렇지 않다. 이러한 버전의 주된 결점은 내부 노드의 크기가 같은 차수의 B-트리의 내부 노드 크기보다 훨씬 크다는 것이다. 이러한 차이점을 보는 또 다른 방법은 내부 노드의 동일한 총 공간에 대해서, 데이터 참조를 제거하는 것에 의해 트리의 차수를 두드러지게 증가시키는 것이다. 결과적으로 그것은 얕은 트리를 생성한다. 물론 트리가 얕으면 얕을수록, 검색은 더 빨라진다.
....
Reference
Micheal J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addision Wesley
Library/File Structure