[인덱스 시리즈2] 데이터베이스 B+Tree Index

이번에는 B+Tree index에 대해 알아보자


먼저 B+Tree index 예시 사진을 보자

구조를 살펴보면, 위의 Root node, Internal nodes, Leaf nodes를 합쳐서 B+Tree index라고 한다.
Srinivasan, Wu, Mozart와 같이 이름으로 index가 설정되어 있는 상황이다.


(45565, Katz, Comp.Sci,75000) 에 해당하는 행을 찾는 상황을 생각해보자


그럼 위의 사진에서
Root node의 Mozart 이전 포인터, Internal nodes의 Gold 다음 포인터, Leaf nodes의 Gold 다음 포인터로 Katz를 찾을 수 있다.
여기서 중요한 것은 총 3번에 거쳐서 행을 찾는다는 것이다. 여기서 B+트리의 중요한 특징이 나오는데
B+트리는 root부터 leaf까지 거치는 모든 높이가 같다.


또 다른 특징을 정리해보면,
- root나 leaf 노드가 아닌 노드의 경우 (n/2의 올림) ~ n 사이의 children 노드를 가지고 있다.
(여기서 n은 node의 포인터의 개수다.)
- leaf node는 ((n-1)/2의 올림) ~ n-1 사이의 값을 가지고 있다.

등이 있다.

---

노드의 구조

다음으로, 각 노드의 구조에 대해 살펴보자

- Ki은 search key라고 하며, 크기 순서대로 정렬되어 있다.
- Pi는 pointer로
non-leaf일 경우에는 자기 자신의 children을 가리키고 있다.
leaf일 경우에는 record나 record의 bucket을 가리키고 있다.

---

B+Tree의 높이

트리 구조에서 데이터를 찾는데 높이가 큰 영향을 미친다.
그럼 B+Tree에서의 높이는 어떨까?
K개의 search key가 있을 때, tree의 높이는 최대

이다. (여기서 n/2는 node의 포인터의 개수다.)


왜냐하면, 루트 노드가 포인터를 2개를 가지고 시작하는데
만약, 트리의 높이가 2이라면, 리프노드는 약 n/2만큼의 포인터를 가지게 된다.
만약, 트리의 높이가 3이라면, 리프노드는 또 약 n/2만큼의 포인터를 가진다.
따라서 리프노드의 포인터의 수는 (n/2) * (n/2) * (n/2) * (n/2) * (n/2) * .... * (n/2) = K 가 된다.
따라서 (n/2)^h = K 이고
트리의 높이 h는 위와 같은 식이 나오게 된다.


이 뜻은 다시 말하면, 데이터 약 100만 개를 높이 4의 B+트리에 저장할 수 있다는 뜻이다.
왜냐하면 보통 node의 사이즈를 disk block의 사이즈와 같게 설계하는데 disk block 사이즈는 보통 4 KB이다.
따라서 매 index entry마다 40바이트라고 가정하면 n은 보통 100정도의 수치가 나온다.


n = 100, K = 100만으로 계산을 해보면
그렇게 되면 log 50 (1,000,000) = 4 정도가 된다.
즉, 높이 4로 100만 개 이상의 데이터를 저장할 수 있다!


만약 균형이 잡힌 이진 탐색 트리 였다면? 100만 개의 데이터면 약 높이 20을 찾아봐야 한다.
(이진 탐색 트리의 높이는 균형이 잘 잡혀 있다면, 높이가 h일 때, 최대 노드의 개수는 2^(h+1)-1이다.)


따라서 데이터베이스에서는 탐색이 빠른 B+Tree 인덱스를 주로 사용한다!

---

B Tree와의 비교

B+ Tree를 보면 Gold가 2번 나오고, Srinivasan이 2 번 나오고 하나의 search key가 여러 번 나오는 것을 알 수 있다.
왜냐하면 B+ Tree에서는 leaf node까지 가야만 해당하는 record를 찾을 수 있기 때문이다.


하지만 B Tree에서는 leaf node까지 가지 않고도 internal nodes에서 바로 record로 갈 수 있게 만들었다.

B Tree의 장단점

B Tree의 장단점에 대해 살펴보자


B Tree의 장점
Tree의 node 개수를 적게 사용할 수 있고, 몇 개의 검색은 미리 찾을 수 있다.


B Tree의 단점
단지 몇 개만 미리 찾을 수 있다.
internal node에다가 바로 record로 갈 수 있는 포인터를 추가하였기 때문에 하나의 index entry가 커지게 되고, 결국에 포인터의 개수가 줄어들어 높이가 높아진다!
(높이가 높아지는 건 위에서도 언급했듯이 트리 구조의 탐색이 느려지는 영향을 미친다.)
또한 삽입과 삭제의 구현이 B+Tree에 비해 훨씬 복잡하다.


따라서 데이터베이스에서는 B Tree Index보다 B+Tree Index를 훨씬 많이 쓴다!


마지막으로 이러한 B+Tree index를 PostgreSQL 15, MySQL 8.0, Oracle 19c에서 모두 지원하고 있다.


더 알고 싶다면 아래 글을 참고하자!
https://durumiss.tistory.com/30

MySQL, Oracle, PostreSQL 비교 분석하기

참고 :
Database System Concepts 7th edition