MySQL을 공부하다보면 항상 나오는 주제중 "Index는 B-Tree를 사용한다"를 볼 수 있습니다. 하지만 B-Tree에 대해서 추상적인 학습만 이뤄져 이번 기회에 정리해보려 합니다.

B-tree에 들어가기 앞서 이진 트리에 대해 간단하게 짚고 넘어가보겠습니다.

Binary Search Tree

이진 탐색 트리(BST, Binary Search Tree)는 정렬된 메모리 자료 구조로, 키-값 쌍 검색에 사용됩니다. 이진 탐색 트리의 특징은 다음과 같습니다.

• 각 노드는 키와 두 개의 자식 포인터를 가집니다.
• 왼쪽 자식에는 키 값보다 작은 값들이 저장되고, 오른쪽 자식에는 키 값보다 큰 값들이 저장됩니다.
• 왼쪽과 오른쪽 자식들도 동일한 특징을 가집니다.
• 특정 데이터를 검색할 때, O(log) 시간을 가지며, Array의 전체 탐색에 비해 빠른 탐색 시간을 가집니다.

이진 탐색 트리의 단점 중 하나는 삽입하는 값에 따라 트리가 불균형해질 수 있다는 점이 있습니다. 즉, 한쪽으로 편향된 트리가 형성될 수 있으며, 이는 빠른 검색의 장점을 무효화될 수 있습니다. 따라서 이런 불균형 트리를 균형 트리로 재구성하는 트리 리밸런싱이 필요합니다.

균형 트리는 N개의 원소에 대해 높이가 log N이며, 왼쪽과 오른쪽 트리의 높이 차가 최대 1인 트리입니다. 이러한 높이 차이를 "균형 인수(balance factor)"라고 부르며 다음과 같이 표현할 수 있습니다.
balance_factor = height(right_subtree) - height(left_subtree)
균형 트리는 균형 인수가 -1 <= balance factor <= 1 의 범위를 가집니다.

트리 리밸런싱 방법으로는 단일 회전과 이중 회전이 있습니다. 각 회전은 루트 노드를 변경하여 좌우 높이 차이를 줄이는 방법입니다.

이러한 이진 탐색 트리는 디스크에 데이터를 저장하기에는 다음과 같은 적합하지 않는 부분이 존재합니다.

• 하나의 노드에 하나의 키만 저장되기 때문에(팬아웃이 낮음) 트리 리밸런싱과 노드 재배치, 포인터 갱신이 빈번하게 발생합니다. 즉, 트리 유지 보수 비용을 증가시킵니다.
• 포인터를 통해 노드간 연결되기 때문에, 부모 노드와 자식 노드가 서로 다른 디스크 페이지에 저장될 수 있어 여러 페이지가 조회해야 할 수 있습니다. 이는 지역성이 결여될 수 있습니다.(캐싱과도 연관이 있습니다.)

따라서 이진 탐색 구조에서의 단점으로 인해 디스크에 저장하기에는 부적합합니다. 디스크에 저장하기 좋은 구조는 다음과 같은 특징을 가집니다.

• 인접한 키의 지역성이 좋아야 하며, 큰 팬 아웃 값을 가지는 트리
• 트리 순회 중 디스크 탐색 횟수를 줄이기 위한 낮은 트리 높이

그렇다면 디스크 기반 자료 구조에 대해서 알아볼까요?

디스크 기반 자료 구조

디스크 기반 자료 구조는 데이터를 메모리에 전부 저장할 수 없는 상황에서 주로 사용됩니다. 이러한 구조는 데이터의 일부를 메모리에 캐시하고 나머지를 효율적으로 접근할 수 있는 형태로 설계됩니다.

디스크 기반 자료 구조는 저장 매체의 구조를 고려해서 설계되며, 디스크 접근 횟수를 최소화하도록 설계됩니다. 또한 내부 구조를 최적화하고 지역성을 높여 페이지를 넘나드는 포인터를 최소화해야 합니다.

이진 탐색 트리가 디스크에 저장하기 불리한 이유 중 하나는 트리 리밸런싱 과정에서 발생하는 오버헤드입니다. 이는 디스크에 노드들의 포인터를 저장하는 과정에서 많은 페이지 조회가 필요하기 때문입니다. 이를 해결하기 위해 B-Tree는 팬아웃을 크게 하고, 트리의 높이와 노드 포인터의 수, 트리 리밸런싱 빈도를 줄이도록 설계되었습니다.

유비쿼터스 B-Tree

B-Tree는 검색 항목을 빠르게 찾을 수 있는 게층형 자료 구조입니다. B-Tree는 팬아웃이 높고 트리의 높이가 낮아 디스크에 적합한 구조입니다.

• 구조: B-Tree는 루트, 내부 노드, 리프 노드로 구성됩니다. 루트 노드는 트리의 최상위 노드로 부모 노드가 없으며, 내부 노드는 루트와 리프 노드를 연결하는 모든 노드를 포함합니다. 리프 노드는 자식 노드가 없는 최하위 계층의 노드입니다.
• 특징: B-Tree는 키의 순서가 보장되는 자료구조입니다. 따라서 이진 탐색과 같은 알고리즘을 사용하여 데이터 접근 시 O(log) 시간이 소요됩니다. 또한 하나의 노드에 여러 키(팬 아웃이 큼)를 저장하기 때문에 데이터 접근 시 이진 탐색 트리보다 적은 페이지 접근수를 가집니다.

B-Tree에서의 데이터 접근에 대해서 살펴봤으니, 데이터 추가가 어떻게 이뤄지는지 살펴보겠습니다.

B-Tree 노드 분할

일반적으로 B-Tree에 데이터를 추가할 때는 먼저 삽입 위치를 탐색한 후 데이터를 삽입합니다. 리프 노드에 더 이상 저장할 공간이 없다면 해당 노드를 둘로 나누는 작업을 수행합니다. 이를 오버플로우 상태라고 합니다.

노드 분할 작업의 조건은 다음과 같습니다.

• 리프 노드: 최대 N개의 키-값을 저장할 수 있으며, 새로운 키-값 쌍 삽입 시 용량이 초과하는 경우
• 리프가 아닌 노드: 최대 N + 1개의 포인터를 저장할 수 있으며, 포인터 추가 시 용량이 초과하는 경우

노드 분할은 새로운 노드를 할당하고, 키의 절반을 새로운 노드로 옮기 후 첫 번째 키와 포인터를 부모 노드에 추가하는 방식으로 이뤄집니다. 또한 부모 노드에 추가되는 키는 승급되었다고 표현합니다. 또한 분할 지점의 키를 분할 지점(미드 포인트)라고 부릅니다.

부모 노드도 오버플로우 상태가 되면, 부모 노드 역시 분할 과정을 거칩니다.

위 과정을 다음 네 단계로 요약할 수 있습니다.
1. 새로운 노드를 할당합니다.
2. 분할 노드 키의 절반을 새로운 노드로 복사합니다.
3. 새로운 키를 알맞은 노드에 삽입합니다.
4. 분할 노드의 부모 노드에 분할 키와 새로운 노드를 가리키는 포인터를 추가합니다.

B-Tree 노드 병합

B-Tree에서 데이터 삭제는 데이터 추가와 유사하게 이뤄집니다. 삭제 대상을 찾은 뒤 해당 위치의 데이터를 삭제 마킹합니다. 데이터가 위치한 노드에 일정 개수 이하의 키만 남으면 되면 인근 형제 노드와 병합합니다. 이를 언더플로우라고 합니다. 하나의 노드로 합칠 수 없는 경우에는 키를 두 노드에 균형있게 분배합니다. 병합 과정에서 분할 과정과 유사하게 상위 노드로 전파될 수 있습니다.

병합 과정을 세 단계로 요약할 수 있습니다.
1. 모든 키를 오른쪽 노드에서 왼쪽 노드로 복사합니다.
2. 부모 노드에서 오른쪽 노드를 가리키는 포인터를 제거합니다.(리프 노드 병합 또는 강등)
3. 오른쪽 노드를 제거합니다.

요약

• 이진 탐색 트리는 트리의 깊이가 깊고 팬아웃이 낮아 디스크에 저장하기에는 적합하지 않는 구조이다.
• B-Tree는 트리의 깊이가 낮고, 팬아웃이 높아 디스크에 저장하기 적합한 구조이다.
• B-Tree는 데이터 추가, 삭제 과정에서 노드가 분리/병합될 수 있습니다.