B+TREE는 B-TREE와 거의 유사하지만 약간의 차이가 있다.
B+TREE의 특징
-
B-TREE에서는 키와 데이터가 동일했지만 B+TREE에서는 키와 데이터가 분리되어있다. B+TREE에서 내부노드에 존재하는 키는 데이터를 찾아가는 이정표 역할을 해주고 리프노드에 있는 키는 키가 가리키고 있는 데이터와 일대일 대응을 한다.
(이때 같은 키가 내부노드, 리프노드에 중복해서 존재할 수 있다. 두 키는 각각 이정표의 역할과 데이터를 직접 가리키는 역할을 한다.) -
리프노드의 자식에는 데이터가 들어가있고 키와 데이터들이 1대1 대응을 하므로 리프노드의 자식의 수는 key의 개수와 동일하다.
-
그리고 마지막 데이터들은 연결리스트로 연결되어있다. 따라서 B-TREE에서는 불가능했던 선형탐색이 가능하다.
코드
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>
#define MIN_DEGREE 2
#define MAX_KEY (MIN_DEGREE*2 - 1)
typedef struct _node {
bool is_leaf;
int key[MAX_KEY + 1], key_count;
struct _node *pointer[MAX_KEY + 2], *parent, *left, *right;
} node;
node *node_create();
void b_plus_tree_create(node **root);
void b_plus_tree_insert(node **root, int k, int value);
void b_plus_tree_delete(node *sub_root, node **root, int k);
void b_plus_tree_search(node* sub_root, int k);
void b_plus_tree_linear_search(node* sub_root, int k, int n);
void node_insert(node *sub_root, int k, int v);
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 bind_node(node *parent, node *left_child, node *right_child, int index);
void bind_leaf_node(node *parent, node *left_child, node *right_child, int index);
void display(node *cur_node, int blanks);
void test_case(node **root, int size);
int SUCC(node *succ_child);
int main() {
node *root;
b_plus_tree_create(&root);
test_case(&root, 1000);
b_plus_tree_search(root, 500);
b_plus_tree_linear_search(root, 150, 20);
display(root, 0);
}
void test_case(node **root, int size) {
int* out_arr = (int*)malloc(sizeof(int) * size);
for (int i = 0; i < size; 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];
out_arr[j] = out_arr[i];
out_arr[i] = t;
}
for (int i = 0; i < size; i++) {
int r = out_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;
new_node->parent = NULL;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
void b_plus_tree_create(node **root) {
node *new_node = node_create();
*root = new_node;
}
void b_plus_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 (!sub_root->is_leaf){
if (k == sub_root->key[i]) {
b_plus_tree_search(sub_root->pointer[i + 1], k);
} else {
b_plus_tree_search(sub_root->pointer[i], k);
}
} else if (sub_root->is_leaf) {
if (k == sub_root->key[i]) {
printf("success\n");
int* value_point = (int*)sub_root->pointer[i];
printf("key=%d, value=%d \n", sub_root->key[i], *value_point);
// printf("%p")
} else {
printf("fail\n");
}
}
}
void b_plus_tree_linear_search(node* sub_root, int k, int n) {
int i = 1;
while (i <= sub_root->key_count && k > sub_root->key[i]) {
i = i + 1;
}
if (!sub_root->is_leaf){
if (k == sub_root->key[i]) {
b_plus_tree_linear_search(sub_root->pointer[i + 1], k, n);
} else {
b_plus_tree_linear_search(sub_root->pointer[i], k, n);
}
} else if (sub_root->is_leaf) {
if (k == sub_root->key[i]) {
int cnt = 0;
for (int j = i; cnt < n && j <= sub_root->key_count; j ++, cnt ++){
int* value_point = (int*)sub_root->pointer[j];
printf("%d ", *value_point);
}
sub_root = sub_root->right;
while(1) {
if (sub_root == NULL){
break;
}
for (int j = 1; cnt < n && j <= sub_root->key_count; j ++, cnt ++){
int* value_point = (int*)sub_root->pointer[j];
printf("%d ", *value_point);
}
if (cnt == n){
break;
}
sub_root = sub_root->right;
}
printf("\n");
} else {
printf("%d not in tree\n", k);
}
}
}
void b_plus_tree_insert(node **root, int k, int v) {
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->pointer[1] = curr_root;
curr_root->parent = new_root;
node_split(new_root, 1);
node_insert(new_root, k, v);
}
else {
node_insert(curr_root, k, v);
}
}
void node_split(node *parent, int child_index) {
node *right_child = node_create();
node *left_child = parent->pointer[child_index];
right_child->is_leaf = left_child -> is_leaf;
if (right_child->is_leaf) {
right_child->key_count = MIN_DEGREE;
for (int i = 1; i <= MIN_DEGREE; i ++) {
right_child->key[i] = left_child->key[i + MIN_DEGREE - 1];
}
for (int i = 1; i <= MIN_DEGREE; i ++) {
right_child->pointer[i] = left_child->pointer[i + MIN_DEGREE - 1];
}
right_child->right = left_child->right;
left_child->right = right_child;
right_child->left = left_child;
}
else {
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];
}
for (int i = 1; i <= MIN_DEGREE; i++) {
right_child->pointer[i] = left_child->pointer[i + MIN_DEGREE];
}
}
right_child->parent = parent;
left_child->key_count = (MIN_DEGREE - 1);
for (int i = parent->key_count + 1; i >= child_index + 1; i--) {
parent->pointer[i + 1] = parent->pointer[i];
}
parent->pointer[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 node_insert(node *sub_root, int k, int v) {
int *value = (int *)malloc(sizeof(int));
*value = v;
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];
sub_root->pointer[i + 1] = sub_root->pointer[i];
i -= 1;
}
sub_root->key[i + 1] = k;
sub_root->pointer[i + 1] = (void *)value;
sub_root->key_count += 1;
}
else {
while (i >= 1 && k < sub_root->key[i]) {
i -= 1;
}
i += 1;
if (sub_root->pointer[i]->key_count == MAX_KEY) {
node_split(sub_root, i);
if (k > sub_root->key[i]) {
i += 1;
}
}
node_insert(sub_root->pointer[i], k, v);
}
}
void b_plus_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_plus_tree_create(root);
return;
}
else {
node *old_root = *root;
*root = (*root)->pointer[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){
free(sub_root->pointer[i]);
for (int j = i; j < sub_root->key_count; j ++) {
sub_root->key[j] = sub_root->key[j + 1];
sub_root->pointer[j] = sub_root->pointer[j + 1];
}
sub_root->key_count -= 1;
break;
}
}
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->pointer[i];
node *right_child = sub_root->pointer[i + 1];
if (right_child->key_count >= MIN_DEGREE) {
node_delete(right_child, k);
sub_root->key[i] = SUCC(sub_root->pointer[i + 1]);
return;
}
if (left_child->key_count >= MIN_DEGREE) {
move_key_left_to_right(left_child, right_child, &(sub_root->key[i]));
node_delete(right_child, k);
return;
} else {
if (!left_child->is_leaf) {
bind_node(sub_root, left_child, right_child, i);
}
else {
bind_leaf_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->pointer[i - 1];
node *right_child = sub_root->pointer[i];
if (right_child->key_count >= MIN_DEGREE) {
node_delete(right_child, k);
return;
}
if (left_child->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 {
if (!left_child->is_leaf) {
bind_node(sub_root, left_child, right_child, i - 1);
}
else {
bind_leaf_node(sub_root, left_child, right_child, i - 1);
}
node_delete(left_child, k);
return;
}
return;
}
else {
node *left_child = sub_root->pointer[i];
node *right_child = sub_root->pointer[i + 1];
if (left_child->key_count >= MIN_DEGREE) {
node_delete(left_child, k);
return;
}
if (right_child->key_count >= MIN_DEGREE) {
move_key_right_to_left(left_child, right_child, &(sub_root->key[i]));
node_delete(left_child, k);
return;
}
else {
if (!left_child->is_leaf) {
bind_node(sub_root, left_child, right_child, i);
}
else {
bind_leaf_node(sub_root, left_child, right_child, i);
}
node_delete(sub_root->pointer[i], k);
return;
}
return;
}
}
void move_key_right_to_left(node *left_child, node *right_child, int *parent_key) {
if (!left_child->is_leaf) {
left_child->key[(left_child->key_count) + 1] = *parent_key;
left_child->key_count += 1;
left_child->pointer[(left_child->key_count) + 1] = right_child->pointer[1];
left_child->pointer[(left_child->key_count) + 1]->parent = left_child;
right_child->key_count -= 1;
*parent_key = right_child->key[1];
for (int j = 1; j <= right_child->key_count; j++) {
right_child->key[j] = right_child->key[j + 1];
right_child->pointer[j] = right_child->pointer[j + 1];
}
right_child->pointer[(right_child->key_count) + 1] = right_child->pointer[right_child->key_count + 2];
}
if (left_child->is_leaf) {
left_child->key[(left_child->key_count) + 1] = *parent_key;
left_child->key_count += 1;
left_child->pointer[(left_child->key_count)] = right_child->pointer[1];
right_child->key_count -= 1;
for (int j = 1; j <= right_child->key_count; j++) {
right_child->key[j] = right_child->key[j + 1];
right_child->pointer[j] = right_child->pointer[j + 1];
}
*parent_key = right_child->key[1];
}
}
void move_key_left_to_right(node *left_child, node *right_child, int *parent_key) {
if (!right_child->is_leaf) {
right_child->pointer[(right_child->key_count) + 2] = right_child->pointer[right_child->key_count + 1];
for (int j = right_child->key_count; j >= 1; j--) {
right_child->key[j + 1] = right_child->key[j];
right_child->pointer[j + 1] = right_child->pointer[j];
}
right_child->key[1] = *parent_key;
right_child->key_count += 1;
*parent_key = left_child->key[left_child->key_count];
right_child->pointer[1] = left_child->pointer[left_child->key_count + 1];
right_child->pointer[1]->parent = right_child;
left_child->key_count -= 1;
}
if (right_child->is_leaf) {
for (int j = right_child->key_count; j >= 1; j--) {
right_child->key[j + 1] = right_child->key[j];
right_child->pointer[j + 1] = right_child->pointer[j];
}
right_child->key[1] = left_child->key[left_child->key_count];
right_child->key_count += 1;
*parent_key = left_child->key[left_child->key_count];
right_child->pointer[1] = left_child->pointer[left_child->key_count];
left_child->key_count -= 1;
}
}
void bind_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->pointer[j] = parent->pointer[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];
}
for (int j = 1; j <= (right_child->key_count) + 1; j++) {
left_child->pointer[MIN_DEGREE + j] = right_child->pointer[j];
}
left_child->key_count += (right_child->key_count + 1);
free(right_child);
}
void bind_leaf_node(node *parent, node *left_child, node *right_child, int 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->pointer[j] = parent->pointer[j + 1];
}
parent->key_count -= 1;
for (int j = 1; j <= right_child->key_count; j++) {
left_child->key[MIN_DEGREE - 1 + j] = right_child->key[j];
left_child->pointer[MIN_DEGREE - 1 + j] = right_child->pointer[j];
}
left_child->key_count += right_child->key_count;
free(right_child);
}
int SUCC (node *succ_child) {
if (succ_child->is_leaf) {
return succ_child->key[1];
} else {
return SUCC(succ_child->pointer[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 | ", cur_node->key[i]);
int *value = (int *)cur_node->pointer[i];
printf("%d\n", *value);
}
return;
}
for (i = 1; i <= cur_node->key_count; i++) {
display(cur_node->pointer[i], blanks + 1);
for (int j = 1; j <= blanks; j ++)
printf("---!");
printf("%d\n", cur_node->key[i]);
}
display(cur_node->pointer[i], blanks + 1);
return;
}
코드의 내용은 B-TREE와 거의 비슷하다.
다만 주의해야할 점이 몇가지 있다.
1. 데이터 넣기
typedef struct _node {
bool is_leaf;
int key[MAX_KEY + 1], key_count;
struct _node *pointer[MAX_KEY + 2], *parent, *left, *right;
} node;구조체를 선언할 때 자식들이 들어가는 pointer에는 node 포인터가 들어가도록 했다.
하지만 만약 데이터로 숫자가 들어간다고 하면 int 포인터를 담아야 한다.
이때 int 포인터를 void포인터로 형변환해 넣어준다.
void포인터는 다양한 자료형의 포인터와 호환이 되기 때문이다.
(이때문에 void포인터는 범용포인터라고도 불린다.)
int *value = (int *)malloc(sizeof(int));
*value = v;
...
sub_root->pointer[i + 1] = (void *)value;하지만 void 포인터는 자료형이 정해지지 않았으므로 값을 가져오거나 저장할 크기도 정해지지 않았기 때문에 역참조가 불가능하다.
따라서 역참조를 할 때는 다시 다른 자료형으로 형변환이 필요하다.
int *value = (int *)cur_node->pointer[i];
printf("%d\n", *value);2. 삽입
만약 리프노드가 꽉차 분할을 해야할 때 B-TREE에서는 중앙값에 있는 키를 그대로 부모로 올려보냈지만 B+TREE에서는 중앙값에 있는 키를 올려보냄과 동시에 분할된 노드 중 하나에도 그대로 남겨놓는다.
그림으로 나타내면 아래와 같다.
앞서 말한 것처럼 올라간 키는 데이터 값을 찾아가는 이정표 역할을 하게 되고 아래 남은 키는 데이터와 일대일로 가리키는 역할을 한다.
(아래 그림에서 리프노드 밑에 데이터값이 존재한다고 가정한다.)
3. 리프노드의 자식의 개수
리프노드의 자식은 각 키가 가리키고 있는 데이터로 리프노드의 자식의 개수는 키의 개수와 같다.
따라서 리프노드에서의 삽입이나 삭제를 할 때 내부노드의 자식의 개수와 혼동하지 않도록 해야한다.
피드백 환영합니다.
-끝-
piopiop1178@gmail.com