B+ Tree
Published:
LSM 트리에 관한 지난 포스트에서 B+ 트리에 대한 언급이 있었습니다. LSM 트리를 이해하는 데에 도움이 되지만 추가하기 너무 길어져서 별도의 포스팅으로 정리한다는 것이었는데요. 이 포스팅에서는 B+ 트리에 대해서 다뤄보고자 합니다. 기본적인 구조에서부터 어떻게 삽입, 삭제, 업데이트가 이루어지는지, 그리고 왜 B+ 트리가 효과적인지에 대해 살펴볼 예정입니다.
대부분의 논문과 책에서 B+ 트리를 말할 때 일반적으로 B 트리라고 부릅니다. 엄밀히 말하면 B 트리와 B+ 트리는 다른 자료구조이지만 많은 자료에서 B 트리는 다루지 않고 B+ 트리를 다루고, B+ 트리를 B 트리로 부르기 때문에 이 포스팅에서도 B 트리로 부르도록 하겠습니다.
이 문서는 A. Silberschatz의 Database System Concepts와 A. Petrov의 Database Internals에서 일부 발췌하였습니다.
Binary Tree
학부 1학년 혹은 2학년때 배우는 트리의 가장 기본적인 변형이 이진 트리(binary tree)입니다. 이진 트리는 하나의 루트 노드(root node)를 가지며, 모든 노드는 0개, 1개, 혹은 2개의 자식 노드를 가집니다. 새로운 값이 삽입될 때는 해당 값이 노드에 저장된 값보다 작으면 왼쪽 노드를, 크면 오른쪽 노드를 탐색하는 식으로 트리를 탐색해 탐색되는 노드가 없을 때 해당 위치에 새로운 값을 저장하는 방식으로 진행합니다.
Advantages?
이진 트리의 장점은 이상적인 상황에서 이론적인 탐색 시간이 $O(log_2N)$이라는 점입니다 ($N$은 노드의 개수). 어떤 값을 탐색할 때, 루트 노드 기준으로 절반은 찾는 쪽의 반대편 서브트리에 위치해 있으므로 탐색할 필요가 없고, 다음 노드에서도 절반은 반대편 서브트리에 있어서 탐색할 필요가 없고… 해서 매 레벨을 내려갈 때마다 탐색할 양이 절반으로 감소합니다. 탐색할 양이 exponential하게 감소하기 때문에 탐색 시간이 $O(log_2N)$이 나오는 것이죠.
Disadvantages!
간단한 자료구조인 만큼 단점도 명확합니다. 여기서는 왜 이진 트리와 비슷한 트리들이 디스크 기반 데이터베이스 시스템에서 사용되지 않는지 간단하게 살펴보겠습니다.
우선 앞서 말씀드린 장점은 이상적인 상황에서의 이진 트리의 장점입니다. 극단적인 상황을 예로 들자면, 트리에 입력되는 값들이 계속 증가한다면 이진 트리의 오른쪽 노드에만 새로운 노드들이 추가될 것입니다. 이렇게 극단적인 경우에서 이진 트리는 일종의 리스트로 볼 수 밖에 없고 탐색 시간은 $O(N)$으로 수렴합니다. 이런 상황을 방지하기 위해 이진 트리는 노드의 삽입 혹은 삭제가 발생할 때 트리를 회전하는 등의 방식으로 트리의 균형을 유지하고자 노력합니다. 하지만 이런 트리의 밸런싱 작업들은 하나하나가 추가적인 비용입니다.
디스크 기반 시스템에서 이진 트리가 사용되지 않는 이유는 크게 두 가지가 있습니다.
첫 번째는 지역성(spatial locality)입니다. 이진 트리에 값들이 추가될 때 특정한 순서를 따르지 않고 임의로 추가가 되기 때문에 값이 가까운 노드들이 실제로 디스크에 가깝게 위치한다는 보장이 없습니다. 즉 어떤 노드의 두 자식 노드들이 여러 디스크 페이지에 걸쳐 위치할 수 있다는 의미입니다.
두 번째는 트리의 높이입니다. 이진 트리에서 하나의 노드는 단 두 개의 자식 노드를 가지기 때문에, 하나의 노드를 찾기 위해서는 $O(log_2N)$개의 노드를 찾아 내려가야 할 수 있습니다.
이렇듯 최악의 경우 이진 트리는 하나의 노드를 찾을 때 $O(log_2N)$개의 디스크 페이지를 읽어와야 할 수 있습니다. $O(log_2N)$개의 레벨을 탐색해야 하고, 각 노드가 모두 다른 디스크 페이지에 위치한다면 해당하는 모든 디스크 페이지를 살펴야 하기 때문입니다. 이런 문제들을 통해 우리는 다음과 같은 자료구조를 필요로 한다는 것을 알 수 있습니다.
- 노드가 가질 수 있는 자식 노드의 수가 많다 (= fanout이 크다)
- 트리의 높이가 낮다
이런 특성을 만족하는 대표적인 자료구조가 이번 포스팅에서 다루는 B 트리입니다.