B-트리에 대해서 알아보기

요즘에는 데이터베이스 관련 공부를 하고 있는데 습득한 지식을 기록해두는 것이 좋다고 생각해 글을 작성한다.

소개

데이터베이스에서는 데이터를 저장하는 방식이 다르다. 크게 봐서는 온메모리와 디스크로 나뉘는데 온메모리는 쉽게 말해 RAM 같은 곳에서 상주하는 것이고 디스크는 HDD, SSD 과 같은 것이다. B-트리는 이 중에서 디스크 저장할 때 사용되는 알고리즘이고 페이지-블럭-플레인-다이 등의 구조에서 효율적인 관리에 대한 방법을 제시한다.

 

실제로도 사용이 되고 있는 B-트리 구조의 정확한 표기는 B+-트리 이다. 여기에서는 편의를 위해 B-트리로 표기한다.

 

B-트리란? (feat. Binary Tree)

Binary 트리의 약자로 혼돈할 수 있지만 그것은 맞지 않다. 쉽게 말해 B-트리는 self-balancing-tree 로 풀어서 말하자면 균형을 스스로 맞출 수 있는 능력이 있는 트리이다.

 

가장 중요한 특징 2개는 팬아웃과 밸런싱 작업이다.

 

팬아웃 (fanout)

팬아웃은 쉽게 말해 퍼지는 정도를 가리킨다. 이진 트리에서는 자식 노드가 2개씩 있는데 여기에서 2라는 상수가 팬아웃을 가리킨다고 보면 된다. B-트리 는 이진 트리와 달리 자식 노드, 즉 서브트리가 2개로 국한되지 않고 수십 혹은 수백 개가 될 수 있다.

 

팬아웃이 높다는 뜻은 이로 인해 트리가 변경하는 정도가 줄어드는 구조를 가진다. 또한 연속으로 데이터를 저장하기 때문에 탐색 비용이 저렴하다. 하나의 노드가 하나의 페이지로 되어 있기 때문에 연속으로 저장되어 있는 블럭 등으로 탐색비용이 절감되는 효과를 볼 수 있다.

 

밸런싱 작업

B-트리의 다른 특징은 밸런싱 작업인데 일반적인 트리 구조와 달리 노드의 용량, 값 추가, 삭제 등으로 인한 병합 혹은 분산 등을 실행할 수 있다. 또한 이러한 작업들을 통해서 스스로 밸런싱 할 수 있는 특징이 있다.

 

---

트리 구조

각 노드는 디스크의 페이지 단위를 사용하기 때문에 B-트리에서 한 노드는 페이지로 볼 수 있다. 더 나아가기 전에 먼저 이진 트리에 대해서 잠깐 살펴보자.

 

https://commons.wikimedia.org/wiki/File:Sorted_binary_tree.svg

보면 각 노드는 두 개의 자식 노드를 가질 수가 있다. 보통 순서는 작은 경우 왼쪽, 큰 경우 오른쪽으로 배치가 된다.

 

예를 들어 F 노드보다 작은 B 노드는 왼쪽에 배치되었고 F 노드보다 큰 G 노드는 오른쪽에 배치되어 있다. 이렇게 왼쪽/오른쪽으로 배치가 되기 때문에 비교할 때 더 수월하고 log2 의 시간 복잡도로 계산이 된다.

 

흔히들 위에 그림처럼 각 노드를 원으로 표현을 하는데 이렇게 할 수 있는 이유는 위와 같은 경우에는 각 노드에 값이 따로 지정되어 있기 때문이다. 하지만 한 개의 값이 아닌 여러 개의 값을 가지거나 애초에 값이 아닌 포인터만 저장되어야 하는 경우들이 있는데 그것이 바로 B-트리 이다. 

 

노드 종류

 

트리에는 3가지 종류의 노드가 있다고 볼 수 있다:

• 루트 노드: 루트 노드와 같은 경우에는 부모 노드가 없는 노드이다. 따라서 최상위 노드라고 생각하면 된다.
• 내부 노드: 내부 노드는 최상위 노드인 루트 노드와 리프 노드 사이에 있는 노드들이다.
• 리프 노드: 트리에서 가장 최하위에 있는 노드들이며 이 노드들은 자식 노드가 없는 것이 특징이다.

B-트리

일반적인 이진 트리와 달리 B-트리 는 모든 노드에 데이터 값을 저장하지 않는다. 즉, 리프 노드에만 데이터 값이 들어가고 그 외에는 다른 노드를 가리키는 포인터가 저장이 된다. 따라서 다음과 같은 형태로 볼 수 있다.

 

https://upload.wikimedia.org/wikipedia/commons/3/37/Bplustree.png

위 트리를 보게 되면 이진 트리와 비슷하게 일단 구성되어 있다는 것을 볼 수가 있다. 루트 노드에서부터 자식 노드로 내려가는 모습이 동일하다.

 

하지만 다른 점이 몇가지가 있다. 일단 리프 노드를 제외한 노드들, 즉 비리프 노드들은 키와 포인터가 존재한다. 가장 상위에 있는 루트 노드는 [3, 5] 의 키가 존재한다. 그리고 그 밑으로는 포인터가 존재하는데 이 때 가장 왼쪽에 있는 포인터는 첫번째 키보다 작은 값들을 가리키고 가장 오른쪽은 마지막 키보다 크거나 같은 값들은 가리킨다. 나머지 포인터들은 가장 왼쪽과 가장 오른쪽 키들 가운데 값들을 지니고 있다.

 

B-트리 변형

B-트리 의 경우에는 여러 변형된 형태로도 나올 수 있는데 위에는 하나의 변형된 예시이다. 보면 리프 노드에 빨간색으로 표시된 포인터가 있는데 이건 형제 노드를 가리키는 포인터다.

 

이러한 변형에서 얻을 수 있는 이익은 부모로 다시 돌아가 또 찾아야 되는 번거로움과 오버헤드를 줄일 수 있다는 점에서 효율적이다. 이것 외에도 이중 연결 리스트 형식으로 서로 간에 연결이 되어 있어 왔다갔다 할 수 있는 변형도 있다.