효율적인 트리(tree) 구조를 유지하는데 가장 큰 문제는, 최적의 트리 탐색 성능을 제공하기 위해서 트리는 정렬된 상태로, 균형 트리를 이루어야 한다는 것이다. 그러나 트리의 균형을 잡는 연산은 매우 비싸다. 이진 트리가 이상적인 상태를 유지한다고 하더라도, 이진 탐색은 디스크 상주 인덱싱에 비해서 그다지 빠르지 않다.
트리가 최적의 탐색 성능을 제공하기 위해서는, 트리는 균형을 이루어야 하는데, 이것은 가능한 한 루트에서 가장 끝에 위치한 각각의 노드까지 경로가 최대한 비슷해야 한다는 것을 의미한다. 즉, 트리가 최악의 성능을 보이는 경우는 일렬로 노드가 연속되어 붙어 있을 때이며, 이 경우 사실 트리라기보다는 리스트에 더 가깝다. 역사적으로 트리를 균형 상태로 유지하기 위해 AVL 트리나, 페이지화 된 이진 트리(paged binary tree)와 같은 기법들이 연구되었다.
AVL 트리는 높이-균형 트리이며, 이것은 하나의 공통 루트를 공유하는 두 개의 서브 트리의 높이 사이에 허용되는 차이의 양에 한계를 두고 있다. AVL 트리에서 최대 허용 차이는 1이다. 그러므로 AVL 트리는 높이-균형-1-트리, 혹은 HB(1) 트리라고 한다.
높이-균형 트리는, 정렬된 순서로 인덱스를 유지하는 것이 비싸다는 점에 대해 어느 정도 해결책을 제시한다. 트리의 균형을 잡기 위해 소모되는 연산은, AVL 트리의 경우 가장 복잡한 회전이라고 하더라도 다섯 개의 포인터 재지정만 필요하다.
그렇다면, 이제 남은 문제는 너무 많은 탐색을 요구하는 이진 탐색이다. 이것은, 이진 탐색 트리의 디스크 사용이 극히 비효율적이라는 점에서 출발한다. 다시 말해, 이진 탐색 트리의 노드를 읽을 때, 단지 세 개의 유용한 정보만 얻을 수 있다. 키 값과 왼쪽, 오른쪽 서브 트리의 주소만 읽을 수 있는데, 디스크가 한번에 읽을 수 있는 정보는 최소 512 바이트라는 점을 생각한다면 이것은 대단한 낭비가 아닐 수 없다. 따라서, 최소한 한번에 읽는 페이지 단위를 모두를 사용하는 전략을 선택하는 것이 필수적인 요소가 된다. 페이지화 된 이진 트리는 그런 한가지 방법이다. 페이지화 된 이진 트리는 같은 디스크 페이지에 여러 개의 이진 노드를 읽어들인다. 따라서, 디스크에서 필요로 하는 정보가 방금 읽어들인 페이지에 있다면, 그만큼의 디스크 접근 비용을 절약하게 된다.
페이지화 된 이진 트리는 같은 디스크 페이지에 여러 개의 이진 노드를 위치시킴으로써 이 문제를 다룬다. 페이지화 된 시스템에서는 단지 몇 바이트를 얻기 위해 디스크 탐색에 비용을 소비하지 않는다. 대신에 일단 디스크의 한 영역을 탐색하며, 파일에서 한 페이지 전체를 읽어들인다. 이 페이지는 많은 개별 레코드로 구성될 수 있다. 만약 필요로 하는 다음 정보가 방금 읽어온 페이지에 있다면 디스크에 다시 접근하지 않고도 이 요청을 만족할 수 있으며, 그만큼 디스크 접근 비용을 절약하게 된다.
그러나, 페이지화 된 트리를 구성하는데 데이터를 루트에서부터 채워나간다고 하면, 전형적인 트리의 불균형 문제가 발생한다. 페이지화 된 트리에서 트리의 균형을 유지하는 것은 쉬운 문제가 아니다. 즉, 몇 페이지만 재배열하면서 지역적으로만 효과를 미치는 알고리즘을 작성하는 것은 매우 어려운 문제이다. 재배열과 균형 조절은 트리의 많은 부분에서 일어나는데, 이것은 가장 피하고 싶은 상황이다. 그러나, 이런 상황은 페이지의 크기가 커짐에 따라 더욱 복잡해진다. 따라서, 페이지로 키를 모으는 생각이 디스크 탐색을 줄여준다는 측면에서 상당히 좋더라도 모든 문제를 완전하게 해결하지 못한다.
B-트리(B-Tree)는 바로 이런 문제에 대해 해답을 제공한다.B-트리의 중요한 개념은, 트리를 형성하는데 루트에서부터 트리를 형성하는게 아니라, 밑에서부터 형성해 나갈 수도 있다는 점이다. Bayer와 McCreight는 루트에서부터 트리를 형성하는 것 자체에 문제가 있다는 점을 지적했다. 좋지 않은 상황을 되돌리는 방법을 발견하는 것보다(트리의 균형을 잡는), 전체적으로 그 어려움을 피하는데 중점을 두었다. B-트리의 경우, 루트가 이미 만들어진 후 그것을 변경할 방법을 찾는 것보다, 다 구성된 트리에서 루트가 나타나도록 한다.
Reference
Micheal J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addison Wesley