B-Tree

균형 이진 트리중 하나로 트리간의 균형을 유지한다
이진 탐색 트리의 단점인 최악의 경우 선형 탐색 시간을 가진다는 단점을 보완하기 위해 개발이 되었다

Big-O Notation

Algorithm	Average	Worst case
Space	O(log n)	O(log n)
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

About B-Tree

1. 모든 리프노드가 아닌 노드는 최대 M개의 엔티티를 가진다
2. 모든 리프노드가 아닌 노드는 최소 M/2개의 엔티티를 가진다
3. 모든 리프노드가 아닌 노드가 K개의 엔티티를 가지면 자식 노드는 K+1개를 가진다
4. 모든 노드는 최대 M+1개의 자식노드를 가진다
5. 루트노드를 제외한 리프노드가 아닌 모든 노드들은 최소 ⌈m/2⌉ 의 자식 노드를 가진다
6. 루트노드가 리프노드가 아니라면 최소 두개의 자식 노드를 가진다
7. 모든 외부노드는 같은 레벨에 존재하며 아무런 정보도 가지고 있지 않다
8. 각 노드의 엔티티는 정렬된 상태이다
9. 엔티티의 중복은 불가능하다
   
   
   

B-Tree 구현

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

#define M 3
#define DATATYPE int
#define BTreeNode struct BTreeNode

BTreeNode {
    DATATYPE *data; // data array
    BTreeNode **childPtr; // child node array of data
    int leaf; // is leaf?
    int n; // number of data
} *root = NULL, *np = NULL, *x = NULL;

BTreeNode *init() {
    int i;
    np = malloc(sizeof(BTreeNode)); // allocate node
    np->data = malloc(sizeof(int) * M); // allocate data array
    np->childPtr = malloc(sizeof(BTreeNode) * (M + 1)); // allocate child node array
    np->leaf = 1; //leaf
    np->n = 0; //has no data
    for (i = 0; i < M + 1; i++)
        np->childPtr[i] = NULL; // init childn node
    return np;
}

//순회
void circuit(BTreeNode *p, int degree) {
    putchar('\n');
    int i, j;
    for (j = 0; j < degree; j++) printf("  ");
    for (i = 0; i < p->n; i++) {
        if (p->childPtr[i] != NULL) {  // if p is not leaf
            circuit(p->childPtr[i], degree + 1);
            for (j = 0; j < degree; j++) printf("  ");
        }
        printf("%d ", p->data[i]);
    }
    if (p->childPtr[i] != NULL)     // if p is not leaf
        circuit(p->childPtr[i], degree + 1);
    putchar('\n');
}

int compare(const void *a, const void *b) {
    return *(DATATYPE *) a > *(DATATYPE *) b ? 1 : -1;
}

// sorting data array
void sort(int *p, int n) {
    qsort(p, n, sizeof(DATATYPE), compare);
}

//devide child
DATATYPE splitChild(BTreeNode *x, int i) {
    // allocate np1, np3 after devide node x
    int j;
    DATATYPE mid;
    BTreeNode *np1, *np3, *y;
    /*
        ↙x↘
     np1   np3
     */
    np3 = init();
    // if x doesnt have parent node
    if (!(i ^ -1)) { // i==-1
        //devide M/2
        mid = x->data[M >> 1];
        x->data[M >> 1] = 0;
        x->n--;
        np1 = init();
        x->leaf = 0;
        for (int j = 0; j < M >> 1; j++) {
            np1->data[j] = x->data[j];
            np1->childPtr[j] = x->childPtr[j];
            np1->n++;
            x->data[j] = 0;
            x->n--;
        }
        np1->childPtr[M >> 1] = x->childPtr[M >> 1];
        for (j = (M >> 1) + 1; j < M; j++) {
            // np3 node will takes right side of x node
            np3->data[j - (M>>1) - 1] = x->data[j];
            np3->childPtr[j - (M>>1) - 1] = x->childPtr[j];
            np3->n++;
            // delete from x node
            x->data[j] = 0;
            x->n--;
        }
        np3->childPtr[j - (M>>1) - 1] = x->childPtr[j];
        np1->leaf = np1->childPtr[0] == NULL ? 1 : 0;
        np3->leaf = np3->childPtr[0] == NULL ? 1 : 0;
        // make child node of x as NULL
        for (j = 0; j < M + 1; j++)
            x->childPtr[j] = NULL;
        x->data[0] = mid;
        x->childPtr[0] = np1;
        x->childPtr[1] = np3;
        x->n++;
        // make np1 root
        root = x;
    } else { // if x has parent node
        y = x->childPtr[i];
        mid = y->data[M >> 1];
        y->data[M >> 1] = 0;
        y->n--;
        for (j = (M >> 1) + 1; j < M; j++) {
            // np3 node will takes right side of x node
            np3->data[j - ((M >> 1) + 1)] = y->data[j];
            np3->n++;
            y->data[j] = 0;
            y->n--;
        }
        x->childPtr[i + 1] = y;
        x->childPtr[i + 1] = np3;
    }
    return mid;
}

// insert value
void insert(DATATYPE input_value) {
    int i;
    DATATYPE temp;
    x = root;
    if (x->n == M)
        temp = splitChild(x, -1);
    // if root node is NOT NULL
    // current node is leaf and is it full
    if (x->leaf == 1 && x->n == M) {
        temp = splitChild(x, -1);
        x = root;
        // find place to insert
        for (i = 0; i < (x->n); i++) {
            if ((input_value > x->data[i]) && (input_value < x->data[i + 1])) {
                i++;
                break;
            } else if (input_value < x->data[0])
                break;
            else
                continue;
        }
        x = x->childPtr[i];
    } else { // is not leaf
        while (!x->leaf) // find leaf node
        {
            for (i = 0; i < (x->n); i++) {
                if ((input_value > x->data[i]) && (input_value < x->data[i + 1])) {
                    i++;
                    break;
                } else if (input_value < x->data[0])
                    break;
                else
                    continue;
            }
            // is it full ? devide : NOT
            if ((x->childPtr[i])->n == M) {
                temp = splitChild(x, i);
                x->data[x->n] = temp;
                x->n++;
                continue;
            } else
                x = x->childPtr[i];
        }
    }

    x->data[x->n] = input_value;
    sort(x->data, x->n);
    x->n++;
}

int main(void) {
    int n;
    DATATYPE insert_value;
    printf("삽입할 원소의 개수를 입력하세요 : ");
    scanf("%d", &n);
    root = init();
    while (n--) {
        printf("원소를 입력하세요 : ");
        scanf("%d", &insert_value);
        insert(insert_value);
    }
    printf("트리를 순회합니다.\n");
    circuit(root, 0);
    return 0;
}

참조

https://en.wikipedia.org/wiki/B-tree
https://m.blog.naver.com/PostView.nhn?blogId=wari7i7&logNo=220854776817&proxyReferer=https%3A%2F%2Fwww.google.com%2F