B+ Tree Index

B+ Tree Index란?

B+ Tree index란 B+ Tree라는 자료구조를 사용한 database index를 말한다.

B+ Tree를 사용하여 index를 구현하면 기존 방식의 index보다 더 좋은 성능의 index를 구현할 수 있다.

 

기존 indexed-sequential file의 경우 파일이 커질수록 많은 overflow block이 발생하고,

이에 따라 성능이 하락하기 때문에 주기적으로 재구성을 해야 한다.

 

하지만 B+ Tree의 경우 삽입 삭제 시 자동으로 구조를 유지하기 때문에 주기적으로 재구성할 필요가 없다.

물론 삽입 삭제 시 추가적인 overhead가 발생하나, 재구성에 필요한 시간이 더 크기 때문에 B+ Tree가 유리하다.

 

이런 장점들 때문에 모든 relational database system에서 B+ Tree를 지원하고 있으며,

거의 모든 file system에서도 B+ Tree를 사용한다.

 

 

 

Structure

전체적인 B+ Tree의 구조는 다음과 같다.

 

기본적으로 Tree 형태로 구성되며, 각각의 노드는 pointer와 key 값이 번갈아 반복되는 구조를 갖고 있다.

 

 

leaf node의 pointer들은 다음 칸의 key 값에 해당하는 데이터의 실제 위치를 저장하며,

마지막 pointer는 다음 leaf node의 위치를 저장한다.

 

P1은 K1의 주소, P2는 K2의 주소, ... P(n-1)은 K(n-1)의 주소, P(n)은 다음 leaf node의 주소를 저장한다.

즉 (P1, K1) - (P2, K2) - ... - (P(n-1), K(n-1)) - P(n) 형태로 저장한다.

 

 

non-leaf node의 pointer들은 child node의 위치를 저장한다.

key 값을 기준으로 왼쪽 pointer는 key 값보다 작은 key 값의 노드를,

key 값을 기준으로 오른쪽 pointer는 key 값보다 크거나 같은 key 값의 노드를 가리키게 된다.

 

P1은 K1보다 작은 값의 key 들을 포함하는 노드의 주소를 가리키며,

P2는 K2보다 작고 K1보다 크거나 같은 key들을 포함하는 노드의 주소를 가리킨다.

즉, P1 < K1 <= P2 < K2 <= P3 < ... < K(n-1) <= P(n) 형태로 저장된다. 

 

 

 

Search

탐색 방법은 BST와 비슷하다.

 

현재 key 값보다 작은 값의 key들은 왼쪽 포인터가 가리키는 노드에,

현재 key 값보다 크거나 같은 값의 key들은 오른쪽 포인터가 가리키는 노드에 위치한다.

 

이를 바탕으로 탐색 과정을 구성해보자.

 

현재 노드를 cur, 찾는 데이터의 key 값을 target 이라고 했을 때,

1. cur = root

2. while(cur != leaf)

    2-1. K(0)부터 차례대로 살펴보며 target보다 크거나 같은 최초의 key 값을 찾는다. (이를 K(i)라 하자)

    2-2. K(i)=target 이면 P(i+1)이 가리키는 노드로, K(i)>target 이면 P(i)가 가리키는 노드로 이동한다.

    2-3. 크거나 같은 key 값이 없다면 null이 아닌 마지막 포인터가 가리키는 노드로 이동한다.

3. (cur==leaf) K(0)부터 차례대로 살펴보며 target과 같은 key 값을 찾는다. (이를 K(i)라 하자)

4. P(i)가 가리키는 곳에서 데이터를 가져온다.

 

 

그렇다면 실제 예를 통해서 탐색 과정을 살펴보자.

 

위와 같이 이름을 key 값으로 가지며 알파벳 순으로 정렬된 B+ Tree를 예로 살펴보자.

이 B+ Tree에서 "El Said" 라는 이름의 데이터를 찾아보자.

 

 

먼저 root 노드에서 첫번째 key 값부터 살펴보며 "El Said"보다 크거나 같은 최초의 key 값을 찾는다.

이 경우 K(0)인 "Mozart"가 "El Said"보다 알파벳 순으로 크기 때문에 P(0)를 따라 다음 노드로 이동한다.

 

 

다시 다음 노드의 K(0)부터 살펴보며 "El Said"보다 크거나 같은 최초의 key 값을 찾는다.

이 경우 K(2)인 "Gold"가 "El Said"보다 알파벳 순으로 크기 때문에 P(2)를 다라 다음 노드로 이동한다.

 

 

이제 leaf node에 도착했으므로 K(0)부터 살펴보며 "El Said"를 찾는다.

이 경우 K(1)이 "El Said"이므로 P(1)을 통해 데이터베이스에 접근하여 우리가 찾는 데이터를 가져올 수 있다.

 

 

 

Insertion

삽입 과정은 다음과 같이 이루어진다.

 

먼저 삽입하려는 데이터의 key 값과 일치하는 key 값이 있는지 B+ Tree index에서 찾는다.

1. key 값이 존재하면, 저장된 pointer를 통해 데이터베이스에 접근하여 데이터를 수정

2. key 값이 존재하지 않으면

    2-1. 데이터베이스에 데이터를 삽입

    2-2. B+ Tree의 leaf node(맨 처음 탐색한 위치)에 공간이 있으면 pointer, key 삽입

    2-3. leaf node에 공간이 없으면 해당 노드를 split 후 빈 공간에 삽입

 

삽입 과정 역시 BST와 비슷하나, 마지막에 노드에 빈 공간이 없으면 해당 노드를 split하여 새 노드를 구성한다.

 

split이란 기존 노드가 새로 삽입할 노드를 포함해 n개의 (pointer, value) 쌍을 갖고 있다고 가정했을 때,

노드의 절반을 떼어 n/2(소수일 경우 올림)번째 (pointer, value) 쌍을 첫번째 쌍으로 갖는 새 노드를 만드는 것을 말한다.

 

이 때 split 후 새로 생긴 노드의 위치를 parent 노드에 추가해주어야 하는데,

parent 노드 또한 공간이 없다면 split을 실행하며, 이렇게 더 이상 노드가 split 되지 않을 때까지 반복한다.

만약에 root 노드까지 split 될 경우 새 root 노드를 생성한다.

 

 

이해가 잘 안된다면 실제 예시를 통해 살펴보자.

 

위와 같은 B+ Tree에 "Adams" 라는 key 값이 삽입되는 경우를 생각해보자.

 

 

먼저 "Adams" 라는 key 값을 탐색해보고, leaf node에 해당 key 값이 존재하지 않는 것을 확인하였다.

그렇다면 이제 해당 leaf node에 새 (pointer, key) 쌍을 삽입해야 하는데 공간이 없다.

따라서 해당 노드를 split 해주어야 한다.

 

 

기존 노드의 쌍 3개 + 새로 삽입할 노드의 쌍 1개 = 4개이므로 뒤쪽 2개의 쌍을 떼어 새 노드를 만들자.

이 경우 "Califieri"와 "Crick"이 떼어져 새 노드로 분리되었다.

 

이제 새로 삽입한 데이터인 "Adams"를 맞는 자리인 "Brandt" 앞쪽에 삽입해주자.

 

 

마지막으로 새로운 노드가 추가되었으니 parent 노드에도 새 쌍을 추가해준다.

새 쌍을 추가한 parent 노드는 공간이 초과되지 않았으니 split을 하지 않고, 삽입은 여기서 완료된다.

 

만약에 parent 노드에도 새 쌍을 추가할 공간이 부족하다면 parent 노드도 split 해주어야 한다.

 

 

 

Deletion

삭제 과정은 다음과 같이 이루어진다.

 

1. B+ Tree index에서 key 값을 검색하여 데이터의 위치를 찾아 데이터베이스에서 데이터를 삭제한다.

2. B+ Tree index에서 삭제한 데이터의 (pointer, key) 쌍을 삭제한다.

3-1. 삭제 후 entry가 얼마 남지 않았고, 형제 노드와 merge가 가능한 경우 merge하여 하나의 노드로 만든다.

3-2. 삭제 후 entry가 얼마 남지 않았지만, 형제 노드와 merge가 불가능한 경우 redistribute한다.

4. parent 노드에서도 (pointer, key) 쌍을 삭제한 뒤 3-1과 3-2를 반복한다.

 

이 때, merge란 2개의 노드를 합쳐 1개의 노드를 만드는 작업이고,

redistribute는 entry가 많은 노드의 entry들을 entry가 적은 노드로 옮겨 균형을 맞추는 작업이다.

 

 

마찬가지로 예시를 통해 살펴보자.

 

위 B+ Tree에서 "Srinivasan" 데이터를 삭제해보자.

 

 

먼저 "Srinivasan" 이라는 key 값을 B+ Tree index의 leaf node에서 찾아 삭제한다.

 

 

"Srinivasan" entry를 삭제하자 "Wu" entry 1개만 남게 되었고, 이 때 형제 노드에 공간이 남아있으니 merge한다.

 

 

노드를 merge하여 합치게 되니 parent 노드에 entry가 부족하게 되었다.

그러므로 형제 노드의 entry 하나를 이동시켜 redistribute 해주자.

 

 

이제 entry가 부족한 노드가 없으므로 삭제 과정이 완료되었다.