B 트리

전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다.

n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 생각해 보자. 키집합은 정렬되어 있다고 한다. (즉, s1<s2<s3...<sn) 그 노드는 n+1자식노드를 가리키는 포인터로 구성된다. 즉, t0,t1,t2...tn.

B-트리의 기본 개념은 내부 노드의 자식 노드의 수가 미리 정해진 범위 내에서 변경가능하다는 것이다. 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나 혹은 다른 노드와 합쳐지게 된다. 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 합침을 통한 재균형 과정은 다른 자가 균형 이진 탐색 트리만큼 자주 일어나지 않지만, 저장 공간에서의 손실은 있게 된다. 자식 노드의 최소 및 최대수는 일반적으로 특별한 구현에 대해서 결정되어 있다. 예를 들어, 2-3 B-트리(혹은 단순히 2-3 트리)에서 각 내부 노드는 2 또는 3개의 자식 노드를 가질 수 있다. 만약 허용되지 않은 수의 자식 노드를 가질 경우, 해당 내부 노드는 부적절한 상태에 있다고 한다.

B-트리는 노드 접근시간이 노드에서의 연산시간에 비해 훨씬 길 경우, 다른 구현 방식에 비해 상당한 이점을 가지고 있다. 이는 대부분의 노드가 하드디스크와 같은 2차 저장장치에 있을 때 일반적으로 일어난다. 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블록 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다.

B-트리의 창시자인 루돌프 바이어는 'B'가 무엇을 의미하는지 따로 언급하지는 않았다. 가장 가능성 있는 대답은 리프 노드를 같은 높이에서 유지시켜주므로 균형잡혀있다(balanced)는 뜻에서의 'B'라는 것이다. '바이어(Bayer)'의 'B'를 나타낸다는 의견도, 혹은 그가 일했던 보잉 과학 연구소(Boeing Scientific Research Labs)에서의 'B'를 나타낸다는 의견도 있다.

B-트리의 노드는 대개 항목과 자식 포인터의 순서 집합으로 표현된다. 루트 노드를 제외한 모든 노드는 임의의 수 L, U(L<U)에 대해 최소 L 항목, 최대 U 항목을 가지고 있으며, 최대 U+1개의 자식 포인터를 가지고 있다. 모든 내부 노드에서, 자식 포인터의 수는 언제나 항목 개수보다 하나가 많다. 모든 리프 노드가 동일한 높이에 있기 때문에, 노드는 일반적으로 리프 노드인지 내부 노드인지 판별하는 수단을 가질 이유가 없다.

각 내부 노드의 항목은 부트리를 나누는 구분 값이다. 예를 들어, 어떤 내부 노드가 3개의 자식 노드(혹은 부트리)를 가지고 있다면, 그 내부 노드는 두개의 구분 값이나 항목 a₁과 a₂를 가지고 있어야 한다. 가장 왼쪽 부트리에 있는 모든 값은 a₁보다 작으며, 가운데 부트리의 모든 값은 a₁와 a₂의 사이에 있으며, 가장 오른쪽 부트리의 모든 값은 a₂보다 크게 된다.

탐색은 일반적인 방식, 즉 이진 탐색 트리와 동일한 방식으로 수행된다. 루트에서 시작하여, 하향식으로 탐색 대상의 값을 구분 값과 비교하며 자식 포인터를 찾아나가는 과정으로 진행한다.

부적절한 상태에 있는 노드란, 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드를 의미한다.

1. 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입한다.
2. 부적절한 상태의 노드가 없다면, 삽입 과정을 종료한다.
3. 만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리한다. 이 과정을 반복적으로 트리를 타고 올라가며 진행한다. 만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다.

L을 허용된 자식 노드의 최소수라고 하고 U를 최대수라고 하자. 그러면, 각 노드는 항상 L과 U 사이의 자식 노드를 가지게 된다. 단, 예외로 루트 노드의 경우 2에서 U사이의 어느 수의 자식 노드도 가질 수 있다. 다른 말로, 루트 노드는 최소수에서 예외로, 자신만의 최소수 2를 가진다는 것이다. 이는 트리가 적은 수의 항목을 가지는 것을 가능하게 한다. 하나의 자식 노드를 가지는 루트 노드는 전혀 의미가 없는데, 이는 해당 자식 노드에 연결된 부트리를 직접 루트 노드에 연결하면 되기 때문이다. 자식 노드를 가지지 않은 루트 노드 역시 불필요한데, 이는 항목이 없는 트리는 일반적으로 루트 노드조차 없는 것과 같기 때문이다.

• Ellis Horowitz,Sartaj Sahni,Dinesh Mehta: Fundamentals of Data Structures in C++. Computer science press.

• B+ 트리
• B* 트리
• 이진 트리