[C] B-TREE를 구현해보자 (1)

B-TREE

전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. -위키백과

쉽게 말하자면 B-TREE는 기존의 이진트리와는 달리 2개 이상의 자식을 가질 수 있는 이진트리이다.

*아래의 내용은 'INTRODUCTION TO ALGORITHMS 3rd Edition'을 참고했습니다.

디스크에 저장되어 있는 정보에 접근하는 시간이 디스크에서 얻은 정보를 메인메모리에서 처리하는 데 걸리는 시간보다 긴 경우가 종종 있기 때문에 디스크에 접근하는 횟수를 최대한 줄여야 한다.
최악의 경우에 트리의 높이만큼 디스크에 접근을 하게 되는데 B-TREE는 하나의 노드에 여러 개의 키를 저장할 수 있기 때문에 허용하는 키의 개수에 따라 트리의 높이가 크게 줄기에 디스크 접근 횟수에 있어서 유리하다.

B-TREE의 특징

1. B-TREE는 루트노드, 리프노드와 내부노드로 구성되어있다.
2. 모든 노드 x의 n개의 키들은 오름차순으로 정렬이 되어있다.
3. 각 내부노드 x는 자식 노드를 가리키는 x.n + 1개의 포인터를 가진다. 리프노드는 자식이 없으므로 포인터값을 갖지않는다.
4. 노드의 키들은 서브 트리에 저장되는 키들의 범위를 분할한다.
   ex) k1 <= x.key1 <= k2 <= x.key2 <= k3 ...
5. 모든 리프 노드는 트리 높이 h와 같은 깊이를 가진다.
6. 노드는 그들이 포함할 수 있는 키의 개수에 대해 상한과 하한을 가진다. 이런 한계를 B-트리의 최소 차수(minimum degree)라고 하는 일정한 정수 t >= 2을 이용해 표현한다.
   a. 루트를 제외한 모든 노드는 t - 1개 이상의 키를 가진다. 따라서 루트를 제외한 모든 내부 노드는 자식 노드를 적어도 t개 이상 가진다. 트리가 비지않았다면 루트는키를 적어도 하나 가진다.
   b. 모든 노드는 2t - 1개 이하의 키를 가진다. 따라서 하나의 내부 노드는 자식 노드를 최대 2t개 가진다. 어떤 노드가 키를 정확히 2t - 1개 갖는 경우, 그 노드를 가득 차있다고 한다.

코드

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MIN_DEGREE 3
#define MAX_KEY (MIN_DEGREE*2 - 1)

typedef struct _node {
    bool is_leaf;
    int key[MAX_KEY + 1], key_count;
    struct _node *linker[MAX_KEY + 2];
} node;

node *node_create();
void b_tree_create(node **root);
void b_tree_insert(node **root, int k);
void b_tree_delete(node *sub_root, node **root, int k);
void b_tree_search(node *sub_root, int k);
void node_insert(node *sub_root, int k);
void node_split(node *parent, int child_index);
void node_delete(node *sub_root, int k);
void move_key_right_to_left(node *left_child, node *right_child, int *parent_key);
void move_key_left_to_right(node *left_child, node *right_child, int *parent_key);
void merge_node(node *parent, node *left_child, node *right_child, int index);
void display(node *cur_node, int blanks);
void test_case(node **root);
int PRED(node *pred_child);
int SUCC(node *succ_child);

int main() {
    node *root;
    b_tree_create(&root);
    test_case(&root);
    display(root, 0);
}

void test_case(node **root) {
    int* out_arr = (int*)malloc(sizeof(int) * 1000000);
    for (int i = 0; i < 1000000; i++) {
		out_arr[i] = i;
    }
    for (int i = 0; i < 1000000; i++) 
    {
        int j = i + rand() / (RAND_MAX / (1000000 - i) + 1);
        int t = out_arr[j];
        out_arr[j] = out_arr[i];
        out_arr[i] = t;
    }
	for (int i = 0; i < 1000000; i++) {
        int r = out_arr[i];
        b_tree_insert(root, r);
    }
    for (int i = 0; i < 1000000; i++) {
        int r = out_arr[i];
        b_tree_delete(*root, root, r);
    }
}

node *node_create() {
    node *new_node = (node *)malloc(sizeof(node));
    if (new_node == NULL) {
        perror("Record creation.");
        exit(EXIT_FAILURE);
    }
    new_node->is_leaf = true;
    new_node->key_count = 0;
    return new_node;
}

void b_tree_create(node **root) {
    node *new_node = node_create();
    *root = new_node;
}

void node_split(node *parent, int child_index) {
    node *right_child = (node *)malloc(sizeof(node));
    node *left_child = parent->linker[child_index];
    right_child->is_leaf = left_child -> is_leaf;
    right_child->key_count = MIN_DEGREE - 1;
    for (int i = 1; i <= MIN_DEGREE - 1; i ++) {
        right_child->key[i] = left_child->key[i + MIN_DEGREE];
    }
    if (!left_child->is_leaf) {
        for (int i = 1; i <= MIN_DEGREE; i++) {
        right_child->linker[i] = left_child->linker[i + MIN_DEGREE];
        }
    }
    right_child->linker[0] = parent;
    left_child->key_count = MIN_DEGREE - 1;
    for (int i = parent->key_count + 1; i >= child_index + 1; i--) {
        parent->linker[i + 1] = parent->linker[i];
    }
    parent->linker[child_index + 1] = right_child;
    for (int i = parent->key_count; i >= child_index; i--) {
        parent->key[i + 1] = parent->key[i];
    }
    parent->key[child_index] = left_child->key[MIN_DEGREE];
    parent->key_count += 1;
}

void b_tree_insert(node **root, int k) {
    node *curr_root = *root;
    if((*root)->key_count == MAX_KEY) {
        node *new_root = node_create();
        *root = new_root;
        new_root->is_leaf = false;
        new_root->linker[1] = curr_root;
        curr_root->linker[0] = new_root;
        node_split(new_root, 1);
        node_insert(new_root, k);
    }
    else {
        node_insert(curr_root, k);
    }
}

void node_insert(node *sub_root, int k) {
    int i = sub_root->key_count;
    if (sub_root->is_leaf){
        while (i >= 1 && k < sub_root->key[i]) {
            sub_root->key[i + 1] = sub_root->key[i];
            i -= 1;
        }
        sub_root->key[i + 1] = k;
        sub_root->key_count += 1;
    }
    else {
        while (i >= 1 && k < sub_root->key[i]) {
            i -= 1;
        }
        i += 1;
        if (sub_root->linker[i]->key_count == MAX_KEY) {
            node_split(sub_root, i);
            if (k > sub_root->key[i]) {
                i += 1;
            } 
        }
        node_insert(sub_root->linker[i], k);
    }
}

void b_tree_search(node *sub_root, int k){
    int i = 1;
    while(i < sub_root->key_count && k > sub_root->key[i]) {
        i = i + 1;
    }
    if (i <= sub_root->key_count && k == sub_root->key[i]) {
        printf("success find %d\n", k);
    } else if(sub_root->is_leaf == true) {
        printf("fail find %d\n", k);
    } else {
        b_tree_search(sub_root->linker[i], i);
    }
}

void b_tree_delete(node *sub_root, node **root, int k) {
    if ((*root)->key_count == 0) {
        if ((*root)->is_leaf) {
            printf("tree is empty\n");
            return;
        }
    }
    node_delete(sub_root, k);
    if ((*root)->key_count == 0) {
        if ((*root)->is_leaf) {
            printf("tree is empty\n");
            free(*root);
            b_tree_create(root);
            return;
        }
        else {
            node *old_root = *root;
            *root = (*root)->linker[1];
            free(old_root);
            return;
        }
    }
}

void node_delete(node *sub_root, int k) {
    if (sub_root->is_leaf){
        int original_key_count = sub_root->key_count;
        for (int i = 1; i <= sub_root->key_count; i ++) {
            if (sub_root->key[i] == k){
                for (int j = i; j < sub_root->key_count; j ++) {
                    sub_root->key[j] = sub_root->key[j + 1];
                }
                sub_root->key_count -= 1;
            }
        }
        if (original_key_count == sub_root->key_count) {
            printf("%d not in b-tree\n", k);
        }
        return;
    } 
    int i = 1;
    while(sub_root->key[i] <  k && i <= sub_root->key_count) {
        i += 1;
    }
    if (sub_root->key[i] == k && i <= sub_root->key_count) {
        node *left_child = sub_root->linker[i];
        node *right_child = sub_root->linker[i + 1];
        if (left_child->key_count >= MIN_DEGREE) { 
            int pred = PRED(left_child);
            sub_root->key[i] = pred;
            node_delete(left_child, pred);
            return;
        }
        else if (right_child->key_count >= MIN_DEGREE) { 
            int succ = SUCC(right_child);
            sub_root->key[i] = succ;
            node_delete(right_child, succ);
            return;
        } else {
            merge_node(sub_root, left_child, right_child, i);
            node_delete(left_child, k);
            return;
        }
        return;
    }
    if (i == sub_root->key_count + 1) { 
        node *left_child = sub_root->linker[i - 1];
        node *right_child = sub_root->linker[i];
        if (sub_root->linker[i]->key_count >= MIN_DEGREE) { 
            node_delete(sub_root->linker[i], k);
            return;
        }
        if (sub_root->linker[i - 1]->key_count >= MIN_DEGREE) { 
            move_key_left_to_right(left_child, right_child, &(sub_root->key[i - 1]));
            node_delete(right_child, k);
            return;
        }
        else { 
            merge_node(sub_root, left_child, right_child, i - 1);
            node_delete(left_child, k);
            return; 
        }
        return;
    }
    else {
        node *left_child = sub_root->linker[i];
        node *right_child = sub_root->linker[i + 1];
        if (sub_root->linker[i]->key_count >= MIN_DEGREE) { 
            node_delete(sub_root->linker[i], k);
            return;
        }
        if (sub_root->linker[i + 1]->key_count >= MIN_DEGREE) { 
            move_key_right_to_left(left_child, right_child, &(sub_root->key[i]));
            node_delete(left_child, k);
            return;
        }
        else {
            merge_node(sub_root, left_child, right_child, i);
            node_delete(sub_root->linker[i], k);
            return;
        }
        return;
    }
}

void move_key_right_to_left(node *left_child, node *right_child, int *parent_key) {
    left_child->key[MIN_DEGREE] = *parent_key;
    left_child->key_count += 1;
    *parent_key = right_child->key[1];
    right_child->key_count -= 1;
    left_child->linker[MIN_DEGREE + 1] = right_child->linker[1];
    for (int j = 1; j <= right_child->key_count; j++) {
        right_child->key[j] = right_child->key[j + 1];
    }
    if (!left_child->is_leaf) {
        for (int j = 1; j <= (right_child->key_count) + 1; j++ ) {
            right_child->linker[j] = right_child->linker[j + 1];
        }
    }
}

void move_key_left_to_right(node *left_child, node *right_child, int *parent_key) {
    for (int j = right_child->key_count; j >= 1; j--) {
        right_child->key[j + 1] = right_child->key[j];
    }
    int left_sibling_key_count = left_child->key_count;
    if (!right_child->is_leaf){
        for (int j = (right_child->key_count) + 1; j >= 1; j--) {
            right_child->linker[j + 1] = right_child->linker[j];
        }
        right_child->linker[1] = left_child->linker[left_sibling_key_count + 1];
    }
    right_child->key_count += 1;
    right_child->key[1] = *parent_key;
    *parent_key = left_child->key[left_sibling_key_count];
    left_child->key_count -= 1;
}

void merge_node(node *parent, node *left_child, node *right_child, int index) {
    left_child->key[left_child->key_count + 1] = parent->key[index];
    for (int j = index; j < parent->key_count; j++) {
        parent->key[j] = parent->key[j + 1];
    }
    for (int j = index + 1; j <= parent->key_count; j++) {
        parent->linker[j] = parent->linker[j + 1];
    }
    parent->key_count -= 1;
    for (int j = 1; j <= right_child->key_count; j++) {
        left_child->key[MIN_DEGREE + j] = right_child->key[j];
    }
    if (!left_child->is_leaf) {
        for (int j = 1; j <= (right_child->key_count) + 1; j++) {
            left_child->linker[MIN_DEGREE + j] = right_child->linker[j];
        }
    } 
    left_child->key_count += (right_child->key_count + 1);
    free(right_child);
}

int PRED (node *pred_child) {
    if (pred_child->is_leaf) {
        return pred_child->key[pred_child->key_count];
    } else {
        return PRED(pred_child->linker[(pred_child->key_count) + 1]);
    }
}

int SUCC (node *succ_child) {
    if (succ_child->is_leaf) {
        return succ_child->key[1];
    } else {
        return SUCC(succ_child->linker[1]);
    }
}

void display(node *cur_node, int blanks) {
    int i;
    if (cur_node->key_count == 0) {
        printf("tree is empty\n");
        return;
    }
    if (cur_node->is_leaf) {
        for (i = 1; i <= cur_node->key_count; i++) {
            for (int j = 1; j <= blanks; j ++)
                printf("---!");
            printf("%d\n", cur_node->key[i]);
        }
        return;
    }
    for (i = 1; i <= cur_node->key_count; i++) {
        display(cur_node->linker[i], blanks + 1);
        for (int j = 1; j <= blanks; j ++)
            printf("---!");
        printf("%d\n", cur_node->key[i]);
    }
    display(cur_node->linker[i], blanks + 1);
    return;
}

3일 동안 b-tree를 잡고 있으니 이제 어떤 구조인지 조금 감이 오는 것 같다.
특히 거의 처음써보는 C언어와 포인터에 조금은 익숙해진 것 같다.
역시 부딪혀보는게 가장 빨리 배우는 방법인 것 같다.

다음 포스팅은 위 코드를 간단히 설명해보도록 하겠습니다.

피드백 환영합니다.
-끝-