B-Tree 생성, 삽입

B-Tree의 구현은 크게 4가지로 나뉜다. 구현방법은 사람에 따라 달라질 수 있다. 개념을 이해하는데 걸리는 시간에 비해 구현에 시간이 오래걸리는데, indexing에 항상 주의하자.

 

0. 구조체 정의

1. 트리 및 루트노드 생성

2. 키 삽입

3. 키 삭제

0. 구조체 정의

  : Tree 구조체와, 그 안에 우리가 넣어줄 Node 구조체를 만든다. 차수에 따라 동적으로 할당해주기 위해 포인터와 malloc을 사용한다.

 

  1) Node

typedef struct btNode {

	int key_num;
	int* keys;
	struct btNode** child_pointer;
	struct btNode* link;
	bool isLeaf;

}btNode;

 

  2) Tree

typedef struct bTree {

	//int order;
	struct btNode* root;
	//int node_count;

}bTree;

 

1. B-tree의 생성(초기화)

1. 빈 Tree 생성

  : 빈 Tree를 만들고, root Node 한개를 만들어 추가한다. 처음에는 root Node가 leaf이기 때문에, isLeaf에 True를 할당한다.

bTree* create_tree(int order) {

	bTree* tree;
	tree = (struct bTree*)malloc(sizeof(struct bTree));
	tree->root = create_node(order, true);
	return tree;
}

 

2. 빈 Node 생성

  : 빈 Node를 만들고 key, child_pointer 배열을 최대차수에 따라 동적으로 할당한다.(최대차수는 전역변수로 선언한 뒤 입력받았다.)  

btNode* create_node(bool isLeaf_) {

	btNode* node;
	node = (struct btNode*)malloc(sizeof(struct btNode));
	node->child_pointer = (struct btNode**)malloc((order) * sizeof(struct btNode*));
	node->link = NULL;
	node->isLeaf = isLeaf_;
	node->key_num = 0;
	node->keys = (int*)malloc((order - 1) * sizeof(int));
	for (int i = 0; i < order - 1; i++) {
		(node->keys)[i] = -1;
	}
	return node;
}

 

3. 키 삽입

 : 여기서부터 조금 복잡하다. 키를 루트에 삽입할 때 사용하는 함수는 insert(), insertNonfull(), split()이다. 우리가 깊이 고민해야되는 부분은 '임의의 노드가 이미 키를 2t-1개 가지고 있을 때, 어떻게 삽입해줘야 하는가' 이다. 우선 간단한 예시를 살펴보자.

 

아래 그림과 같이 최대차수가 4(최소차수 t = 2)인 트리의 루트에 키가 3개 들어있다. 새로운 키 1개(3)가 더 들어가면 어떻게 될지 살펴보자.

 

1. 키 삽입 시도

 

노드 한개에 들어갈 수 있는 키는 최대 3개이다.

 

2. 새로운 노드 생성 후 루트 노드로 지정

  : 새로운 노드 s를 만들어 tree의 root로 지정하고, 기존 노드 r을 가리키게 한다.(삽입하려는 노드가 root가 아닌 경우에는 실행하지 않는다.) r의 isLeaf속성은 True로 바뀌어야 한다.

 

 

3. 기존 노드 Split

    1. r의 가운데 key를 노드 s로 올려준다.

    2. 새로운 노드 z를 만들고, r의 가운데 key 기준 우측 key값(t+1번째부터 2t-1번째까지)들을 모두 z로 옮긴다.

    3. Split하려는 노드가 Leaf 노드가 아니어서 Child Pointer들을 가지고 있는 경우, r의 Child Pointer도 노드 z로 옮겨줘야 한다.

    4. 각 노드들의 key 개수(key_num)을 업데이트한다.

 

 

4. 삽입 완료

  : Split이 완료되면 기존 노드(r)와, 새로 생긴 2개의 노드(s,z)는 모두 t-1개의 키를 갖는다. 모든 노드들이 새로운 키값을 넣을 공간이 있으므로, 새로운 키(3)을 알맞은 위치에 넣어준다.

 

 

※ 참고할 사항 ※

1. 삽입하는 과정에서, 새로운 키는 항상 Leaf Node에 추가해야한다.

2. 트리는 항상 기존 존재하던 노드 기준으로 위(Upward)로 자란다.

3. root 노드인 경우는 별도의 작업으로 처리해줘야하기 때문에 insert()함수가 존재하고, root가 아닌 노드인 경우에는 insertNonfull()에서 처리한다. 

4. 키를 삽입할 때 들어가야 할 자리(Leaf Node)를 찾기 위해 노드들을 탐색하며 내려가게 되는데, Leaf Node가 아니더라도 내려가는 과정의 모든 Node에 대해서 키의 개수가 2t-1개(최대)이면 split을 해줘야 한다. 이는 Leaf Node가 가득차서 Split을 할 경우에 다시 위로 올라가서 연산하는 것을 방지하기 위함이다. 

5. 가득 찬 경우에는 split()을 하지만, 가득차지 않은 경우에는 split()을 진행하지 않는다.

 

github.com/SunghyunChoi/btree_algorithm/blob/main/BTree.c

SunghyunChoi/btree_algorithm