[C]B-TREE(2)

前回の投稿に続いて、B-TREEの演算過程を関数で簡単に見てみましょう.

1.ノード構造体宣言

まず最小回数を定数として宣言します.身長の個数や子供の個数の上限や下限は最小回数の影響を受けるのでよく使われます.
次にノード構造体を宣言する.
構造体は1です.リーフノードのbool値/2であることを確認します.格納鍵とサブ鍵の配列/3.キー数
からなる.

#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;

次に、メイン関数、テスト例を作成する関数です.
テスト例は、0からsizeの数値を生成し、ランダムに混合します.
ノードを作成するときにnode create関数を使用して、割り当てられたメモリがNULLであるかどうかを確認し、動的に割り当てられたメモリが正しいことを確認します.

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

void test_case(node **root, int size) {
	int* in_arr = (int*)malloc(sizeof(int) * size);
    int* out_arr = (int*)malloc(sizeof(int) * size);
    for (int i = 0; i < size; i++) {
    	in_arr[i] = i;
        out_arr[i] = i;
    }
    for (int i = 0; i < size; i++) 
    {
        int j = i + rand() / (RAND_MAX / (size - i) + 1);
        int t = out_arr[j];
        in_arr[j] = in_arr[i];
        in_arr[i] = t;
    }
    for (int i = 0; i < size; i++) 
    {
        int j = i + rand() / (RAND_MAX / (size - i) + 1);
        int t = out_arr[j];
        out_arr[j] = out_arr[i];
        out_arr[i] = t;
    }
	for (int i = 0; i < size; i++) {
        int r = in_arr[i];
        b_plus_tree_insert(root, r, r * 3);
    }
    for (int i = 0; i < size; i++) {
        int r = out_arr[i];
        b_plus_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;
}

2.B-TREE演算

各ノードの鍵数が最大(最小差分*2-1)のときにノードを挿入する場合は、ノードを2つのノードに分割する必要があります.
鍵を削除する場合、削除鍵を含むノードの鍵の個数が鍵の最小個数(最小差-1)より少ない場合は、鍵の最小個数と一致するようにノードをマージする必要があります.

1.ノードの分割

フルノードの分割(鍵数が最大)では、フルノードの中心鍵を親ノードに移動し、左右に2つのノードに分割します.
ノードを分割する関数を以下に示します.

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;
}

2.挿入

既定では、挿入はリーフノードでのみ行われます.したがって、ルートノードからリーフノードに至るまで、値を挿入する場所を見つける必要があります.
このとき,位置を探しながらいっぱいのノードに遭遇すると,すぐに分割する.これにより、挿入されたリーフノードが絶対満のノードにならないことが保証されるので、次の挿入演算を実行することができる.
挿入中にルートノードが分割されると、ルートノードの中央値をキーとするノードが新しいルートノードとなり、既存のルートノードが半分に分割され、新しいルートノードのサブノードとなる.
次に、挿入演算コードを示します.

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;

    //삽입할 자리를 찾는 검색을 수행하는 노드가 리프노드라면 k를 삽입
    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);
    }
}

次の図は、挿入プロセスを示しています.
図では,ノードの分割は下降時には行われず,挿入を実行した後に行われるが,結果は同じである.

分割なし挿入

分割挿入

ようこそ
-終了-