Bulk-Loading of a B+-Tree (Bottom-Up Approach)

key들이 쭉 저장되어 있는 배열이 주어졌을 때,
이 배열에 저장되어 있는 key들을 통해서 B+-Tree를 Bottom-Up 방식으로 생성하는 것은 어떻게 구현해야 할까?
 
현재 진행하고 있는 연구에서 이를 구현하기 위해 코드를 3번이나 갈아엎는 시행착오를 겪게 되었다.
이 과정을 통해서 깨달았던 것들을 여기에 정리하고자 한다.
 
 

Top-Down Approach

---

보통 B+-Tree를 생성하고자 한다면 Top-down 방식을 생각할 것이다.
 
Top-down 방식은 search → insert → split 단계로 진행된다.
 

1. root에서부터 시작하여, 현재 tree에 넣고자 하는 key를 저장할 수 있는 leaf node를 찾는다.
2. 해당 leaf node에 key를 insert 한다.
3. 만약 leaf node가 꽉 차있어서 insert를 진행하지 못한다면, split을 진행한 후에 insert 한다.
   경우에 따라서 parent 즉, internal(non-leaf) node부터 root까지 재귀적으로 split이 발생할 수 있다.

 

재귀적으로 split을 발생시키려면 어느 경로를 통해 해당 leaf node까지 도달한 것인지를 저장하고 있어야 하는데,
이는 stack을 통해서 구현할 수 있다.
 
search 단계에서 방문하는 internal node들의 주소를 push 하여 저장하고 있다면,
split이 발생한 경우 pop을 통해서 부모의 주소를 알아내어 추가적인 작업을 진행할 수 있는 것이다.
 
 

Bulk Loading (Bottom-Up Approach)

---

Bulk Loading은 커다란 dataset을 데이터베이스에 한 번에 넣어야 할 때 사용한다. (아래 글 참고)

What does "bulk load" mean?

 
이때 Bottom-Up 방식으로 tree를 생성하게 되는데, 그 절차는 다음과 같다.
 

1. key들을 오름차순으로 정렬한다.
2. 정렬된 순서대로, leaf node에 key를 insert 한다.
3. 만약 leaf node가 꽉 차있어서 insert를 진행하지 못한다면, split을 진행한 후에 insert 한다.
   경우에 따라서 parent 즉, internal(non-leaf) node부터 root까지 재귀적으로 split이 발생할 수 있다.

 

why & how ..?

여기서 의문이 발생한다.
 

• Top-Down 방식과는 무슨 차이가 있고, 왜 Bottom-Up 방식이 더 빠르다고 하는가?
• leaf node가 여러 개 존재한다면, 어느 leaf node에 insert를 진행해야 하는가?
• Top-Down 방식에서는 stack을 통해서 부모가 누구인지를 알 수 있었으니 split을 재귀적으로 발생시킬 수 있었는데,
  여기서는 부모가 누구인지를 어떻게 알 수 있는가?

 

---

 
모든 의문에 대한 답은 '정렬'에서부터 시작한다.
 
key들을 오름차순으로 insert 한다면, tree는 무조건 왼쪽에서 오른쪽으로 & 아래에서 위로 만들어지는 것을 볼 수 있다.
 
 
우선 Top-Down 방식으로, 오름차순으로 key를 넣으면서 tree를 직접 한번 그려보자.
 
예를 들어, 한 node에 저장할 수 있는 key의 개수는 최대 3개라고 하고,
현재 tree에는 root node만이 존재하며 key는 1, 2, 3이 저장되어 있다고 하자.
편의상 그림에서 pointer를 저장하는 부분은 생략하였다.
 

 
여기서 [insert 4]가 발생한다면, 현재 root에는 더 이상 key를 저장할 수 없기 때문에 split이 발생한다.
새로 생겨난 leaf node에 key 4가 저장되고 key 3이 윗 level에 저장되어야 하는데, 방금 root가 split 되었기 때문에 새로운 root가 만들어진다.
 

 
그 후, [insert 5]와 [insert 6]이 발생한다면 가장 오른쪽에 있는(= 가장 최근에 생겨난) leaf node에만 key가 추가되고,
 

 
[insert 7]이 발생한다면, split이 발생하여 바로 윗 level에 key가 insert 된다.
 

 
 
 
이런 식으로 그림을 계속 그리다 보면 아래와 같은 규칙을 발견할 수 있다.
 

1. 각 level의 가장 오른쪽에 있는 node들에만 key가 추가된다.
2. 이에 split이 발생하는 node들도 각 level에서 가장 오른쪽에 위치한다.
3. 이미 split이 발생한 node들은 더 이상 건드려지지 않는다. 즉, key가 새로 insert 되지 않아 node가 split 되지도 않는다.

 
이렇게 tree의 변형이 일어나는 위치가 특정되는데, 여기서 이점을 얻게 되는 것이다.
 
 
 
만약 key들이 무작위로 들어오게 된다면, Top-Down 방식으로 구현하는 것은 불가피하다.
 
해당 key를 insert 해야 하는 위치가 leaf node들 중 어느 곳에 있을지를 모르기 때문에,
즉 tree에서 insert과 split이 발생할 수 있는 위치는 모든 곳에 퍼져있기 때문에 search를 반드시 먼저 진행해야 했던 것이다.
 
 
하지만 Bulk loading에서는 tree에 저장되어야 하는 key들이 전부 정의되어 있는 상황이다.
이에 정렬을 진행할 수 있고, 그 순서대로 insert를 진행한다면 각 level의 어느 위치에 insert이 발생하는지를 곧바로 알 수가 있다.
 
B+-Tree에서 node들은 물리적으로는 가까이 존재하지 않기에 search 비용은 굉장히 큰데,
이 과정을 없앴기에 tree를 만들어 내는 속도가 훨씬 빨라질 수 있는 것이다.
 
 

어떻게 구현할 수 있는가?

각 level에서 가장 오른쪽에 위치해 있는 node들의 주소값만을 계속 저장하고 있으면 된다.
 
나는 rightMostNodes라는 배열을 선언하여 이들을 관리하였다.

Node *root = nullptr;
Node **rightMostNodes = nullptr;

...

// tree에서 최대로 생성될 수 있는 level만큼 공간을 미리 할당한다.
rightMostNodes = new Node *[maxLevels];

// 초기화
root = new Node();
rightMostNodes[0] = root;

 
아래는 leaf level에서 split이 발생하여 새로운 leaf node가 생겨났을 때,
non-leaf level에 새로운 key와 pointer를 저장하기 위해서 불리는 재귀 함수이다.
 
여기서 중요한 포인트 2가지는 다음과 같다.
 

1. rightMostNodes에 저장되어 있는 주소값을 통해 곧바로 key와 pointer 값들을 저장한다.
2. 만약 특정 level에서 node가 새로 생겨났다면,
3. rightMostNodes[level]에 저장되어 있는 값을 해당 node의 주소값으로 갱신한다.

void insertInNonLeafs(uint64_t levelOfChild, uint64_t key, Node *newChild) {
    uint64_t level = levelOfChild + 1;
    
    // 아래 level에서 split 되었던 node가 root인 경우
    if (rightMostNodes[levelOfChild] == root) {
        root = new Node();
        root->insertPointer(rightMostNodes[levelOfChild]);
        rightMostNodes[level] = root;
    }

    // split이 발생하지 않는 경우
    if (rightMostNodes[level]->numberOfKeys < NUMBER_OF_KEYS_IN_TREE_NODE) {
        rightMostNodes[level]->insertKey(key);

    // split이 발생하는 경우
    } else {
        Node *nextNonLeaf = new Node();
        split(rightMostNodes[level], nextNonLeaf);
        insertInNonLeafs(level, rightMostNodes[level]->keys[MIDDLE_OF_KEYS], nextNonLeaf);

        // 재귀 후에 rightMostNodes에 대한 갱신을 진행한다.
        rightMostNodes[level] = nextNonLeaf;
        rightMostNodes[level]->insertKey(key);
    }
    
    rightMostNodes[level]->insertPointer(newChild);
}

 
이렇게 node들의 insert 패턴을 알고 있다면 Bottom-Up 방식을 굉장히 간단하게 구현할 수 있다.
 
 

split을 발생시키지 않고, node를 꽉 채우는 것은 안 되는가?

내가 코드를 와장창 뒤엎게 된.. 가장 결정적으로 잘못된 생각이었다.

B+-Tree를 생성하는 데 있어서 split 연산이 너무 큰 오버헤드를 가지고 있다고 생각하고 있었고 공간도 낭비하게 되는 것으로 보였다. 그리고 넣어야 하는 key들을 전부 미리 알고 있는 상황에서 split을 굳이 구현해야 하는지에 대한 의문이 들었다.
 
 
아래처럼 node들을 꽉 채워서 tree를 그려보면, 각 level에 들어가는 key들 사이에는 규칙이 존재하는 것을 볼 수 있다.
 

 
이에 생각했던 방법은 아래와 같다.
 

1. 각 level 별로 key들을 쭉 저장하여 node들을 미리 정의해 둔다.
2. root부터 시작하여 아래 level의 node들을 pointer로 연결한다.

 
상당히 괜찮은 아이디어 같이 보였으나..
구현을 할수록 어딘가 매우 이상하다는 것을 느꼈고, tree를 조금 더 그려보니 깨달음을 얻을 수 있었다.
 
만약 key가 48까지였다면?? 아래와 같이 괴상한 모양의 tree가 만들어진다.
 

 
 
여기서 가장 큰 문제점은 균형 트리(Balanced tree)가 아니게 구현되어 버리는 것이다.
이상적인 index는 균등하게 위치해 있는데, 여기서는 어느 한쪽으로 몰려버렸기 때문에 가장 오른쪽에 있는 pointer가 두 level을 건너뛰는 것을 볼 수 있다.
 
 
 

---

 
이번 시행착오를 통해서 얻을 수 있었던 깨달음은 B+-Tree에서 split은 균형 트리를 만들기 위한 과정이라는 것이고,
non-leaf들을 꽉 채워서 구현하게 된다면 균형이 깨져버리는 순간이 발생하기 때문에 특정 key 개수가 아니라면 이는 이상한 접근이라는 것이다.
 
미리 key들을 넣어두고 나중에 pointer를 연결하는 방식은 수학적으로 어떻게든 풀어낼 수 있을 것 같으나...
생각하길 포기했다.  (-_-)
 
 
이렇게 해서 split은 불가피한 연산임을 깨달았지만, 오버헤드가 커다란 연산이라는 것에는 변함이 없다.
 
따라서 새로 생겨난 node에 값을 직접 복사하지 않고, pointer만을 바꿔서 최적화하는 방법을 현재 생각해보고 있다.
(구현해보고 괜찮다면 블로그에 써볼수도..)