B트리

1. 개요

- BST의 단점이 최악의 경우 트리의 모든 노드들이 선형적으로 길게 늘어서는 경우가 있을 수 있다는 것이므로, 이를 극복하기 위해 여러 아이디어가 제시되었다. 각 노드들이 갖는 양 서브트리의 높이차가 1 이하여야 한다는 AVL 트리나 루트에서 모든 외부노드까지 경로의 노드수가 최댓값이 커봐야 최솟값의 두 배여야 한다는 레드블랙 트리 또한 그 사례들이다.

- B트리는 ‘한 노드가 갖는 키값의 수가 각각 달라질 수 있다’, ‘모든 외부노드의 깊이는 동일하다’ 두 가지를 주요 개념으로 한 탐색트리다. 이러한 B트리의 특징은 트리 전체가 갖는 데이터의 양이 워낙 방대하여 각 노드를 서로 다른 파일 또는 저장장치에 저장해야 하는 등의 경우에서 탐색 시간 단축에 이점이 있다.

2. 정의

1) m원 B트리는 내부노드가 갖는 최대 차수(자식노드 수)가 m이고 최소 차수는 \(\lfloor {(m+1) \over 2} \rfloor \)인 트리다. (단, 루트노드의 최소 차수는 2이다.)

2) 모든 외부노드의 깊이는 동일하다. (즉, 루트에서 각 외부노드까지의 경로 길이가 모두 동일하다.)

- B트리 또한 탐색트리이므로, m원 탐색트리의 정의에 의해 m원 B트리의 각 노드가 갖는 키값의 개수는 (그 노드의 차수 - 1)개이다. 그리고 각 내부노드에 있는 키값들은 각 내부노드에 있는 키값들끼리 순서대로 정렬돼있으며, 내부노드의 자식노드들은 각 키값 사이에 배치된다. 또 그 자식노드들에 있는 키값들은 모두 그 부모노드의 두 키값 사이의 크기를 갖는다.

- m이 클수록 트리의 높이는 낮아지지만 한 노드에 들어가는 키값 수가 너무 많아져 탐색시간이 증가한다. m이 작아질수록 트리 높이가 높아져 디스크 접근 횟수가 늘어난다.

3. B트리의 탐색시간의 상한

- 레드블랙 트리의 경우와 마찬가지로 B트리의 높이의 상한은 B트리의 노드수의 하한을 구하면 알 수 있다. B트리의 노드수의 하한은 B트리의 모든 노드가 최소차수를 갖는 경우를 생각하면 구할 수 있다.

(1) 탐색트리의 외부노드수 = 탐색트리 전체 노드수 + 1이므로, B트리의 노드 수의 하한은 B트리의 외부노드수의 하한과 같다.

(2) 모든 노드가 최소차수를 갖는 B트리에 대해, 이 트리의 각 레벨에 있는 노드수를 차례대로 적어볼 수 있다. 먼저 루트노드는 하나이고, 루트노드의 최소차수는 정의상 2이므로 레벨2의 노드수는 2이다. 그리고 B트리의 최소차수는 루트를 제외하면 \(\lfloor { {m+1} \over 2 } \rfloor \)(이하 \(m_0\))이므로, 그 다음부터 각 레벨의 노드수는 공비가 \(m_0\)인 등비수열으로 생각할 수 있다. 즉, 최대 레벨 \(L\)이고 모든 노드가 최소차수를 갖는 m원 B트리의 레벨 \(L\)에 위치한 총 노드수는 \(2 m_0 ^ {L-2} \) 이다.

(3) 그런데 최대 레벨 \(L\)이고 모든 노드가 최소차수를 갖는 m원 B트리의 외부노드의 수는 다시 이 값의 \(m_0\)배, 즉 \(2 m_0 ^ {L-1} \)이다. 이 식으로부터 노드수 하한에 관한 부등식 \( n \geq 2 m_0 ^ {L-1} - 1\)을 얻는다.

(4) 이 부등식을 정리하여, B트리의 높이의 상한 = \(log_{m_0} {\left( {n+1} \over 2 \right)} + 1 \) 이다. 이 값이 B트리의 탐색시간의 상한으로, O 표기법으로 쓰면 O(logn)으로 쓸 수 있다.

4. B트리의 삽입

- 일반적인 탐색트리와 달리 B트리는 일단 말단노드에 키값을 삽입하고 말단노드가 포화되면(=그 노드의 키값 수가 m+1이 되면) 말단노드를 분할하고 거기서 나온 원소를 그 부모노드에 삽입하는 형태의 알고리즘을 갖는다. (이를 ‘상향식’이라 한다.) 포화된 노드를 분할하는 알고리즘은 다음과 같다.

(1) 포화된 노드의 \(m_0\)번째 키값을 기준으로, 이보다 작은 키값들은 노드 P에, 이보다 큰 키값들은 노드 Q에 넣는다. 그리고 \(m_0\)번째 키값을 부모노드에 삽입하고, 노드 P는 \(m_0\)의 왼쪽에, 노드 Q는 \(m_0\)의 오른쪽에 붙인다.

(2) 이 연산으로써 그 부모노드가 포화되었다면, 그 포화된 노드에 대해서도 위 (1)번 과정을 반복한다.

5. B트리의 삭제

- B트리의 삭제는 말단노드와 말단노드가 아닌 내부노드의 경우가 다르다.

1) 말단노드에서 키값 삭제

- 어떤 말단노드에서 삭제로 인해 키값 수가 \(m_0\)보다 적어졌다면, (1)먼저 부모노드의 키값을 키값 개수가 \(m_0\)보다 적어진 노드로 가져오고 (2)부모노드에 새로 생긴 빈자리는 부모노드의 키값을 가져간 노드의 형제노드로부터 끌어올린다.

- 만약 키값을 끌어올려야 할 형제노드도 키값 수가 너무 적어 그렇게 할 경우 형제노드도 키값 수가 \(m_0\)보다 적어지는 경우라면, 그렇게 하지 않고 그냥 두 노드를 병합한다. (이때, 키값 크기가 그 두 노드 사이인 부모노드의 키값도 아래로 끌어내려 함께 병합한다. 이로 인해 부모노드도 키값 수가 적어졌다면, 이 루프를 반복한다.)

2) 말단노드 아닌 내부노드에서 키값 삭제

- BST의 일반적인 삭제 시 inorder successor를 가져와 그 자리로 옮겨왔듯, B트리에서도 키값 삭제 시 같은 작업을 수행한다. 이로 인해 말단노드의 키값 개수가 \(m_0\)보다 적어졌다면, 위 1)의 과정을 수행하여 키값 개수를 늘려준다.

6. B+ 트리

- B+ 트리는 B트리와 유사한 트리로, B트리와 같은 구조를 가져 검색, 삽입, 삭제의 과정이 모두 같지만 말단노드 아닌 내부노드의 모든 키값이 말단노드에도 있는 트리이다. 관계 데이터베이스에서 인덱스를 처리하는 데 많이 사용한다.