1. B* 트리
- B 트리의 단점 : 구조를 유지하기 위해서 분리, 회전에 관한 연산이 수행되거나 새로운 노드가 생성된다.
- B 트리의 단점을 보완하기 위해 규칙이 추가되었다.
규칙
기존 B트리 특징을 따르면서,
- 기존에 [M/2]~M-1 개 까지 data 를 가졌는데,
- [2M/3]~M-1 까지의 data 를 가질 수 있고,
- 노드가 가득 차면 분리를 하지 않고, 이웃한 형제 노드로 자료를 재배치 한다. (더 이상 재배치가 불가능 하면 당연히 분할)
분할을 해도 재배치 과정이 필요하기 때문에, 분할을 최소화하면 시간을 많이 아낄 수 있다.
2. B+ 트리
- B 트리의 경우 탐색에 오버헤드가 많이 들어감.
- 노드 안에서 찾고, 또 내려가서 찾고...
규칙
- 같은 레벨에 있는 형제 노드는 연결리스트 형태로 구성해서
- 부모로 다시 돌아오지 않고 형제 내에서 탐색을 할 수 있다.
- 내부 노드는 원래 B 트리와 똑같이 구성됨.
- 차수가 M 일때, [M/2] ~ M 개의 자식을 가질 수 있고,
- 키 값은 [M/2] - 1 ~ M-1 개.
- 최소 차수 t 는 자식 수의 하한값으로, M = 2*t - 1
- 단말 노드의 경우, 키값이 M 개 (마지막이 연결리스트 필드)
- 실제 데이터는 리프에 있음!!! 내부 노드는 탐색을 위한 노드인 것.
- 분할을 할 때, 하나의 키 값을 기준으로 갈라지긴 하는데, 그 값이 부모 노드에도 들어간다.
- 오른쪽 자식의 첫번째 값이 부모의 키에 들어가 있음.
- 내부 노드가 분할을 할 때는 그냥 B트리처럼 분할됨.
- 모든 단말 노드는 연결리스트로 연결되어 있다.
용어
-
index node : leaf node 가 아닌 내부 노드
-
data node : leaf node
-
index node 에는 포인터 주소가 존재하고, 다음 노드를 가리킴
-
data node 에는 데이터가 존재한다.
구현
- 원래는 노드 합치고 이럴때 부모의 key 값이 어떤 위치에 있는지를 알고, (pos)
- pos (왼쪽 자식), pos+1 (오른쪽 자식) 으로 접근해야 했는데,
- 그러지 않고 연결리스트로 해당 리스트의 맨 오른쪽에 있는 링크 타고 접근하면 됨.
구조체
# define DEGREE 3
# define LEAF 0
# define INDEX 1
# define EMPTY 0
# define FULL 1
typedef int Element;
typedef struct Node {
int type;
int n;
Element key[2 * DEGREE - 1];
struct Node *child[2 * DEGREE];
struct Node *next;
} Node;
typedef struct {
Node *root;
} B_Plus_Tree;ADT
void create(B_Plus_Tree* tree);
void insert(B_Plus_Tree* tree, Element key);
// index node / data(leaf) node 일 때, 삽입/분할이 각각 다르기 때문에 각각 필요하다.
void B_Tree_Split_Child(Node* node, int i);
void split_child(Node* node, int i);
void B_Tree_Insert_Nonfull(Node* node, Element key);
void insert_nonfull(Node* node, Element key);
// 삭제
void delete(B_Plus_Tree* tree, Element key); // 루트인지 아닌지 따져서 삭제하는 함수를 부름.
void del(Node* node, Element key); // 실제로 삭제를 수행.
// 트리를 출력해주는 함수.
void display(B_Plus_Tree* tree);
void display_main(Node* node, int h);
void B_Plus_Tree_Leaf_Check(B_Plus_Tree* x);create
void create(B_Plus_Tree* tree) {
Node* temp = (Node *)malloc(sizeof(Node));
if (temp == NULL) {
printf("B 트리 생성 실패");
return;
}
temp->next = NULL;
temp->type = LEAF;
temp->n = 0;
tree->root = temp;
}삽입
- 들어갔는데
2-1. 분할이 필요 없는 경우 (insert_nonfull)
2-2. 분할이 필요한 경우 (split_child / B_Tree_Split_Child 호출)
void insert(B_Plus_Tree* tree, Element key) {
Node* node = tree->root;
// 노드가 꽉 찼다면 새 노드를 할당하여 분할.
if (node->n == 2 * DEGREE - 1) {
Node* new = malloc(sizeof(Node));
if (new == NULL) {
printf("노드 생성 실패");
return;
}
tree->root = new;
new->type = INDEX;
new->next = NULL;
// 새로운 노드를 할당해서 루트로 사용하고,
new->n = 0;
new->child[0] = node;
// 분할 절차를 거쳐서 오른쪽 왼쪽 자식으로 이용한다.
// 분할이 끝나면 루트에도 인덱스가 할당될 것임.
if (node->type == LEAF) {
split_child(new, 0);
} else {
// 단말 노드가 아니면 B트리와 같은 방식으로 분할.
B_Tree_Split_Child(new, 0);
}
insert_nonfull(new, key);
}
// 노드가 꽉 차지 않았다면, 루트에 삽입.
else {
insert_nonfull(node, key);
}
}2-1
void insert_nonfull(Node* node, Element key) {
int i = node->n;
// leaf 노드면 그대로 데이터를 넣으면 됨.
if (node->type == LEAF) {
// B 트리 코드에서는 인덱스 찾는 과정과 배열 미는걸 따로 했는데,
// 여기에선 동시에 진행.
i--;
while (i >= 0 && key < node->key[i]) {
node->key[i + 1] = node->key[i];
i--;
}
node->key[i + 1] = key;
(node->n)++;
}
// index node 라면 자식에 삽입을 시도.
// 만약 또 index 라면 삽입될 위치까지 계속 타고 내려가게 됨.
// LEAF 가 되는게 재귀의 탈출 조건.
else {
while (i >= 1 && key < node->key[i - 1]) {
i--;
}
if ( (node->child[i])->n == 2 * DEGREE - 1) {
if (node->type == LEAF) {
split_child(node, i);
} else {
B_Tree_Split_Child(node, i);
}
if (key > node->key[i]) {
i++;
}
}
insert_nonfull(node->child[i], key);
}
}2-2 에서 리프 노드인 경우.
// 노드에 새 데이터 넣기 전에 분할부터 하는거임.
// node 에는 원래 삽입될 노드의 부모와 그 부모에서 삽입될 위치가 어딘지가 넘어옴
void split_child(Node* node, int index) {
Node* right = (Node *)malloc(sizeof(Node));
if (right == NULL) {
printf("노드 할당 실패");
return;
}
// 부모에서 왼쪽 자식이 분할되어야 하는 노드.
// 왼쪽 자식 node->child[index] 을 분할해서 부모로 하나의 인덱스가 올라가고
// 그 부모의 왼쪽 자식은 지금 왼쪽 자식 t (뒤가 잘린) 이 될거고,
// 뒷부분은 new 에 할당해서 오른쪽 자식으로 쓸 것임.
Node *left = node->child[index];
right->type = left->type;
right->n = DEGREE;
// 일단 해당 노드에서 저장할 위치 확보 : 하나씩 뒤로 밀기.
for (int j = node->n; j > index; j--) {
node->key[j] = node->key[j-1];
node->child[j+1] = node->child[j];
}
// 분할.
for (int j = 0; j < DEGREE; j++) {
right->key[j] = left->key[DEGREE - 1 + j];
}
left->n = DEGREE - 1;
right->next = left->next;
left->next = right;
// 분할된 각각을 부모의 왼쪽 (원래 왼쪽 수정한거라 할당은 필요 X)
// 올라오는 값을 부모의 인덱스
// 오른쪽 자식 new 로 사용.
node->key[index] = left->key[DEGREE-1]; // new->key[0] 과 같은 뜻임.
// DEGREE - 1 / DEGREE 개로 왼쪽 오른쪽 나뉘는데,
// t 에 뒷쪽 데이터를 실제 삭제하는게 아니라 n만 바꿔쓴다.
// key 의 index 가 0 ~ DEGREE - 2 까지이므로 t->key[DEGREE - 1]은 결국 오른쪽의 첫번째와 다름 없음.
node->child[index + 1] = right;
node->n++;
}2-2 에서 내부 노드인 경우
void B_Tree_Split_child(Node * node, int index) {
Node* right = (Node *)malloc(sizeof(Node));
if (right == NULL) {
printf("노드 할당 실패");
return;
}
Node *left = node->child[index];
right->type = left->type;
right->n = DEGREE - 1; // 이 부분이 약간 다름.
for(int j = 0; j < DEGREE - 1; j++) {
right->key[j] = left->key[DEGREE + j];
}
if (node->type == INDEX) {
for(int j = 0; j < DEGREE - 1; j++) {
right->child[j] = left->child[DEGREE + j];
}
}
left->n = DEGREE - 1;
for (int j = node->n; j > index; j--) {
node->child[j + 1] = node->child[j];
node->key[j] = node->key[j-1];
}
node->child[index + 1] = right;
node->key[index] = right->key[0]; // t->key[DEGREE - 1]
node->n++;
}삭제
- 회전이 필요 없는데
1-1. 그냥 삭제가 가능한 경우
1-2. 키 값이 바뀌는 경우
- 회전이 필요함
키 값이 바뀌는 부분도 적용 필요할듯.
2-1. 왼쪽이 충분하면 왼쪽 마지막을 오른쪽 처음으로
그럼 당연히? 부모 노드의 키값도 바뀌어야함.
2-2. 오른쪽이 충분하면 오른쪽 첫번째를 왼쪽 처음으로
역시 부모노드 키 값 바뀜.
2-3. 둘다 불충분하면 왼쪽 노드에 합치면서, 부모 노드도 하나씩 땡김.
void delete(B_Plus_Tree* tree, Element key) {
Node* node = tree->root;
// 내부 노드(루트)인데 노드 내 데이터 개수가 하나이고,
// 노드 왼쪽 오른쪽 자식이 각각 DEGREE - 1 씩 차있으면
// DEGREE - 1 + DEGREE - 1 == 2 * DEGREE - 1 이니까 (root 에 있는건 인덱스니까 안셈)
// 왼쪽 자식으로 오른쪽 합쳐놓고 del 을 호출해서 실제 삭제.
if ((node->n == 1 && node->type == INDEX) && ((node->child[0])->n == DEGREE - 1 && (node->child[1])->n == DEGREE - 1)) {
Node* left = node->child[0];
Node* right = node->child[1];
// 자식이 단말이면 그냥 합쳐버리면 되고,
if (left->type == LEAF) {
for ( int j = 0; j < DEGREE - 1; j++) {
left->key[j + DEGREE - 1] = right->key[j];
}
left->n = 2 * DEGREE - 2
left->next = NULL;
tree->root = left;
free(node);
free(right);
del(left, key);
}
// 자식이 index 면,
// 키만 있는거니까 역시 합치면 됨.
else {
left->key[DEGREE - 1] = node->key[0];
left->child[DEGREE] = right->child[0];
for (int j = 0; j < DEGREE - 1; j++) {
left->key[DEGREE + j] = right->key[j];
left->child[DEGREE + j + 1] = right->child[j + 1];
}
left->n = 2 * DEGREE - 1;
tree->root = left;
free(node);
free(right);
del(left, key);
}
}
// 그게 아니라면?
// 자식 노드에는 DEGREE 만큼은 자식이 들어가 있으니
// 노드를 합칠 필요 없이 삭제하면 됨.
else {
del(node, key);
}
}
// B 트리에서는 삭제부터 냅다 하고 회전은 나중에 처리했는데,
// 삭제하러 가는 길에 여기서 삭제하면 불충분할거같아 -> 먼저 합쳐놓고 마지막에 삭제.
void del(Node *node, Element key) {
int i = node->n;
while (i > 0 && node->key[i - 1] > key) {
i--;
}
int i_for_key = node->n;
while (i > 0 && node->key[i - 1] >= key) {
i_for_key--;
}
// 1. 삭제할 데이터가 있는 노드가 리프 노드라면 키를 삭제하면 됨.
if(node->type == LEAF) {
if (node->key[i_for_key] == key) {
for (int j = i_for_key; j < node->n - 1; j++) {
node->key[j] = node->key[j + 1];
}
node->n--;
return;
} else {
printf("트리에 삭제할 키 값이 없음");
return;
}
}
// 2. 리프 노드가 아니면서 삭제할 노드가 빈곤..
else if ((node->child[i])->n == DEGREE - 1) {
Node * del_child = node->child[i];
// 삭제할 자식의 타입이 indenode
// 타고 내려가면서 합치고, 재귀호출해서 삭제할 leaf 찾아서 삭제
if (del_child->type == INDEnode) {
// 2-1. 해당 노드의 왼쪽 노드가 충분
if (i != 0 && (node->child[i - 1])->n > DEGREE - 1) {
Node* left = node->child[i - 1];
for(int j = DEGREE - 2; j >= 0; j--) {
del_child->key[j + 1] = del_child->key[j];
}
if (del_child->type == INDEnode) {
for(int j = DEGREE - 1; j >= 0; j--) {
del_child->child[j + 1] = del_child->child[j];
}
}
// 부모에서 오른쪽 첫번쨰로 넘어오고, 왼쪽 마지막이 부모로.
del_child->key[0] = node->key[i+1];
del_child->child[0] = left->child[left->n];
del_child->n++;
node->key[i - 1] = left->key[left->n - 1];
left->n--;
}
// 2-2. 오른쪽 노드가 충분
else if (i != node->n && (node->child[i + 1])->n > DEGREE - 1) {
// 부모에서 왼쪽 마지막으로 넘어오고 오른쪽 첫번째가 부모로
Node* right = node->child[i + 1];
del_child->key[DEGREE - 1] = node->key[i];
del_child->child[DEGREE] = right->child[0];
del_child->n++;
for(int j = 0; j < right->n - 1; j++) {
right->key[j] = right->key[j + 1];
right->child[j] = right->child[j + 1];
}
right->child[right->n - 1] = right->child[right->n];
right->n--;
}
// 2-3. 왼쪽 오른쪽 다 불충분.. -> 합쳐야함.
else {
// 맨 왼쪽 자식일 때, 오른쪽으로 합침.
if (i == 0) {
Node *right = node->child[i + 1];
for (int j = 0; j < DEGREE - 1; j++) {
right->key[j + DEGREE] = right->key[j];
right->key[j] = del_child->key[j];
}
if (right->type == INDEnode) {
for ( int j = 0; j < DEGREE ; j++) {
right->child[j + DEGREE] = right->child[j];
right->child[j] = del_child->child[j];
}
}
right->key[DEGREE-1] = node->key[i];
right->n = DEGREE * 2 - 1;
for (int j = 0; j < node-> n - 1; j++) {
node->key[j] = node->key[j+1];
node->child[j] = node->child[j+1];
}
node->child[node->n - 1] = node->child[node->n];
free(del_child);
del_child = right;
node->n--;
}
// 아닌 경우엔 왼쪽으로 합침
else {
Node* left = node->child[i];
left->key[DEGREE - 1] = node->key[i - 1];
for (int j = 0; j < DEGREE - 1; j++) {
left->key[DEGREE + j] = del_child->key[j];
}
if (left->type == INDEnode) {
for (int j = 0; j < DEGREE; j++) {
left->child[DEGREE + j] = del_child->child[j];
}
}
left->n = 2 * DEGREE - 1;
for (int j = i; j < node-> n; j++) {
node->key[j - 1] = node->key[j];
node->child[j] = node->child [j+1];
}
free(del_child);
del_child = left;
node->n--;
}
}
// 리프가 아닌 경우 합치고 다시 해당 child 에 대해서 삭제를 호출.
// 리프인 경우 키가 삭제되며 끝남.
del(del_child, key);
}
// 삭제할 자식의 타입이 leaf -> child 에 대한 처리를 할 필요가 없다.
else {
// 2-1. 왼쪽이 충분해서 왼쪽 마지막 값 가져옴.
if (i != 0 && (node->child[i - 1])->n > DEGREE - 1) {
Node* left = node->child[i - 1];
for (int j = DEGREE - 2; j >= 0; j--) {
del_child->key[j + 1] = del_child->key[j];
}
del_child->key[0] = left->key[left->n - 1];
del_child->n++;
node->key[i - 1] = left->key[left->n - 1];
left->n--;
}
// 2-2. 왼쪽은 불충분. 오른쪽이 충분하면 오른쪽 첫번째 값 가져옴.
else if (i != node->n && (node->child[i + 1])->n > DEGREE - 1) {
Node* right = node->child[i + 1];
del_child->key[DEGREE - 1] = right->key[0];
del_child->n++;
for (int j = 0; j < right->n - 1; j++) {
right->key[j] = right->key[j + 1];
}
node->key[i] = right->key[0];
right->n--;
}
// 2-3. 둘다 불충분해서 노드를 합쳐야함.
else {
if (i == 0) {
Node* right = node->child[i + 1];
for (int j = 0; j < DEGREE - 1; j++) {
del_child->key[DEGREE - 1 + j] = right->key[j];
}
del_child->n = 2 * DEGREE - 2;
del_child->next = right->next;
for (int j = 1; j < node->n; j++) {
node->key[j - 1] = node->key[j];
node->child[j] = node->child[j + 1];
}
node->n--;
free(right);
}
else {
Node* left = node->child[i - 1];
for (int j = 0; j < DEGREE - 1; j++) {
left->key[DEGREE - 1 + j] = del_child->key[j];
}
left->n = 2 * DEGREE - 2;
left->next = del_child->next;
for (int j = i; j < node->n; j++) {
node->key[j - 1] = node->key[j];
node->child[j] = node->child[j + 1];
}
node->n--;
free(del_child);
del_child = left;
}
}
del(del_child, key);
}
}
// 갈 곳이 풍족함 -> 아래로 보낸다.
else {
del(node->child[i], key);
}
return;
}
참고, 출처
개념
- https://ssocoit.tistory.com/217
- https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Plus-Tree
- https://velog.io/@mongle/Data-structure-B-tree-B-tree
코드
- http://egloos.zum.com/voals/v/1670081
- https://github.com/Jeongseo21/Data_structure---B_tree/blob/main/%5BData%20structure%5D%20B%20tree/%5BData%20structure%5D%20B%20tree/B%2Btree.c
사진
0년차 iOS 개발자입니다.