[WEEK05] B-Tree

B-Tree

[출처] https://dzone.com/articles/database-btree-indexing-in-sqlite

B-Tree는 균형 잡힌 다진 검색 트리Balanced Multi-way Search Tree다. 특히 디스크 기반의 저장 장치에서 데이터를 효율적으로 저장하고 검색하기 위해 설계된 자료구조다. 데이터베이스나 파일 시스템에서 많이 사용된다.

주요 특징

• 각 노드는 최대 M개의 자식을 가질 수 있음 (M: 차수)
• 모든 리프 노드는 동일한 깊이에 존재함
• 내부 노드는 최소 ⌈M/2⌉개의 자식을 가져야 함
• 키들은 정렬된 상태로 저장되고, 이진 탐색이 가능함

예시 구조 (차수 M = 4인 B-Tree)

           [10 20]
         /   |    \
       [5] [15]  [25 30]

🔼 B-Tree 삽입 연산 (Insertion)

기본 개념

• 새로운 키를 삽입할 때는 항상 리프 노드에 삽입한다.
• 삽입 대상 노드가 가득 찼다면(split) 해당 노드를 두 개로 나누고, 중간 키를 부모로 올린다.
• 루트가 가득 찬 경우에도 마찬가지로 루트를 분할하고 새로운 루트를 생성한다.

삽입 시 처리 순서

1. 루트가 가득 찼다면, 새로운 루트를 만들고 루트를 분할.
2. 삽입할 위치까지 내려가되, 내려가기 전에 자식이 가득 차 있는 경우 먼저 분할함.
3. 리프 노드에 도달하면 빈 자리에 삽입.

🔽 B-Tree 삭제 연산 (Deletion)

삭제 케이스

1. 리프 노드에서 삭제
   → 바로 삭제하고 끝.
2. 내부 노드에서 삭제
   → 두 가지 방법 중 하나를 사용:
   • 왼쪽 자식 서브트리의 최대값을 가져와 대체
   • 오른쪽 자식 서브트리의 최소값을 가져와 대체
3. 삭제 시 자식 노드가 최소 키 수(t-1)
   → 이 경우는 병합(merge) 또는 형제 노드에서 빌림(borrow)을 통해 키 수를 유지해야 한다.

삭제의 핵심

• 항상 모든 노드는 최소 키 수(t-1) 이상을 유지해야 한다.
• 필요 시 borrow 또는 merge로 구조를 조정한다.

재조정 과정

1. key 수가 여유있는 형제의 지원을 받는다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

---

B-Tree vs Binary Search Tree

항목	Binary Search Tree	B-Tree
자식 노드 수	최대 2개	최대 M개
트리 깊이	깊어질 수 있음	상대적으로 얕음
디스크 I/O	비효율적	매우 효율적
사용 사례	메모리 내 자료 구조	데이터베이스, 파일시스템

---

C언어로 B-Tree 구현

아래 코드는 차수는 t=2 (최대 3개의 키, 최대 4개의 자식) 기준으로 작성되었고, 삽입/삭제/순회 기능을 포함하고 있다.

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

#define MIN_DEGREE 2

typedef struct BTreeNode {
    int *keys;
    int t;
    struct BTreeNode **C;
    int n;
    int leaf;
} BTreeNode;

BTreeNode* createNode(int t, int leaf) {
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->t = t;
    node->leaf = leaf;
    node->keys = (int*)malloc(sizeof(int) * (2 * t - 1));
    node->C = (BTreeNode**)malloc(sizeof(BTreeNode*) * (2 * t));
    node->n = 0;
    return node;
}

void traverse(BTreeNode* root) {
    if (root != NULL) {
        for (int i = 0; i < root->n; i++) {
            if (!root->leaf)
                traverse(root->C[i]);
            printf("%d ", root->keys[i]);
        }
        if (!root->leaf)
            traverse(root->C[root->n]);
    }
}

int findKey(BTreeNode *node, int k) {
    int idx = 0;
    while (idx < node->n && node->keys[idx] < k)
        ++idx;
    return idx;
}

void removeFromLeaf(BTreeNode *node, int idx) {
    for (int i = idx + 1; i < node->n; ++i)
        node->keys[i - 1] = node->keys[i];
    node->n--;
}

int getPredecessor(BTreeNode *node, int idx) {
    BTreeNode *cur = node->C[idx];
    while (!cur->leaf)
        cur = cur->C[cur->n];
    return cur->keys[cur->n - 1];
}

int getSuccessor(BTreeNode *node, int idx) {
    BTreeNode *cur = node->C[idx + 1];
    while (!cur->leaf)
        cur = cur->C[0];
    return cur->keys[0];
}

void merge(BTreeNode *node, int idx) {
    BTreeNode *child = node->C[idx];
    BTreeNode *sibling = node->C[idx + 1];

    child->keys[node->t - 1] = node->keys[idx];

    for (int i = 0; i < sibling->n; ++i)
        child->keys[i + node->t] = sibling->keys[i];

    if (!child->leaf) {
        for (int i = 0; i <= sibling->n; ++i)
            child->C[i + node->t] = sibling->C[i];
    }

    for (int i = idx + 1; i < node->n; ++i)
        node->keys[i - 1] = node->keys[i];
    for (int i = idx + 2; i <= node->n; ++i)
        node->C[i - 1] = node->C[i];

    child->n += sibling->n + 1;
    node->n--;

    free(sibling->keys);
    free(sibling->C);
    free(sibling);
}

void borrowFromPrev(BTreeNode *node, int idx) {
    BTreeNode *child = node->C[idx];
    BTreeNode *sibling = node->C[idx - 1];

    for (int i = child->n - 1; i >= 0; --i)
        child->keys[i + 1] = child->keys[i];

    if (!child->leaf) {
        for (int i = child->n; i >= 0; --i)
            child->C[i + 1] = child->C[i];
    }

    child->keys[0] = node->keys[idx - 1];

    if (!child->leaf)
        child->C[0] = sibling->C[sibling->n];

    node->keys[idx - 1] = sibling->keys[sibling->n - 1];

    child->n += 1;
    sibling->n -= 1;
}

void borrowFromNext(BTreeNode *node, int idx) {
    BTreeNode *child = node->C[idx];
    BTreeNode *sibling = node->C[idx + 1];

    child->keys[child->n] = node->keys[idx];

    if (!child->leaf)
        child->C[child->n + 1] = sibling->C[0];

    node->keys[idx] = sibling->keys[0];

    for (int i = 1; i < sibling->n; ++i)
        sibling->keys[i - 1] = sibling->keys[i];

    if (!sibling->leaf) {
        for (int i = 1; i <= sibling->n; ++i)
            sibling->C[i - 1] = sibling->C[i];
    }

    child->n += 1;
    sibling->n -= 1;
}

void fill(BTreeNode *node, int idx) {
    if (idx != 0 && node->C[idx - 1]->n >= node->t)
        borrowFromPrev(node, idx);
    else if (idx != node->n && node->C[idx + 1]->n >= node->t)
        borrowFromNext(node, idx);
    else {
        if (idx != node->n)
            merge(node, idx);
        else
            merge(node, idx - 1);
    }
}

void removeFromNonLeaf(BTreeNode *node, int idx) {
    int k = node->keys[idx];

    if (node->C[idx]->n >= node->t) {
        int pred = getPredecessor(node, idx);
        node->keys[idx] = pred;
        removeKey(node->C[idx], pred);
    } else if (node->C[idx + 1]->n >= node->t) {
        int succ = getSuccessor(node, idx);
        node->keys[idx] = succ;
        removeKey(node->C[idx + 1], succ);
    } else {
        merge(node, idx);
        removeKey(node->C[idx], k);
    }
}

void removeKey(BTreeNode *node, int k) {
    int idx = findKey(node, k);

    if (idx < node->n && node->keys[idx] == k) {
        if (node->leaf)
            removeFromLeaf(node, idx);
        else
            removeFromNonLeaf(node, idx);
    } else {
        if (node->leaf) {
            printf("키 %d는 트리에 없습니다.\n", k);
            return;
        }

        int flag = ((idx == node->n) ? 1 : 0);

        if (node->C[idx]->n < node->t)
            fill(node, idx);

        if (flag && idx > node->n)
            removeKey(node->C[idx - 1], k);
        else
            removeKey(node->C[idx], k);
    }
}

void delete(BTreeNode **rootRef, int k) {
    BTreeNode *root = *rootRef;
    removeKey(root, k);

    if (root->n == 0) {
        BTreeNode *tmp = root;
        if (root->leaf)
            *rootRef = NULL;
        else
            *rootRef = root->C[0];

        free(tmp->keys);
        free(tmp->C);
        free(tmp);
    }
}

void insertNonFull(BTreeNode *x, int k) {
    int i = x->n - 1;
    if (x->leaf) {
        while (i >= 0 && k < x->keys[i]) {
            x->keys[i + 1] = x->keys[i];
            i--;
        }
        x->keys[i + 1] = k;
        x->n++;
    } else {
        while (i >= 0 && k < x->keys[i])
            i--;
        i++;
        if (x->C[i]->n == 2 * x->t - 1) {
            BTreeNode *y = x->C[i];
            BTreeNode *z = createNode(y->t, y->leaf);
            z->n = x->t - 1;

            for (int j = 0; j < x->t - 1; j++)
                z->keys[j] = y->keys[j + x->t];

            if (!y->leaf) {
                for (int j = 0; j < x->t; j++)
                    z->C[j] = y->C[j + x->t];
            }

            y->n = x->t - 1;

            for (int j = x->n; j >= i + 1; j--)
                x->C[j + 1] = x->C[j];
            x->C[i + 1] = z;

            for (int j = x->n - 1; j >= i; j--)
                x->keys[j + 1] = x->keys[j];
            x->keys[i] = y->keys[x->t - 1];
            x->n++;

            if (k > x->keys[i])
                i++;
        }
        insertNonFull(x->C[i], k);
    }
}

void insert(BTreeNode **rootRef, int k) {
    BTreeNode *r = *rootRef;
    if (r->n == 2 * r->t - 1) {
        BTreeNode *s = createNode(r->t, 0);
        s->C[0] = r;
        *rootRef = s;
        insertNonFull(s, k);
    } else {
        insertNonFull(r, k);
    }
}

// 테스트
int main() {
    BTreeNode *root = createNode(MIN_DEGREE, 1);

    int insertData[] = {10, 20, 5, 6, 12, 30, 7, 17};
    for (int i = 0; i < sizeof(insertData) / sizeof(insertData[0]); i++)
        insert(&root, insertData[i]);

    printf("초기 중위 순회: ");
    traverse(root);
    printf("\n");

    int deleteData[] = {6, 13, 7, 4, 2, 16};
    for (int i = 0; i < sizeof(deleteData) / sizeof(deleteData[0]); i++) {
        printf("키 %d 삭제 후: ", deleteData[i]);
        delete(&root, deleteData[i]);
        traverse(root);
        printf("\n");
    }

    return 0;
}

코드 실행 결과

---

📂 디스크 기반 B-Tree 시뮬레이션

실제 DBMS에서는 B-Tree 노드를 디스크의 블록 단위로 저장하고 필요할 때만 메모리로 로딩한다. 우리는 이걸 흉내 내기 위해 노드를 파일로 저장/불러오는 방식으로 구현할 것이다.

🔧 핵심 아이디어

• 각 노드에 고유한 ID 부여 → 파일 이름으로 사용 (예: "node_1.dat")
• 노드를 생성하거나 수정할 때 해당 ID로 파일에 저장
• 노드를 참조할 때마다 해당 ID의 파일을 읽어서 로드
• 메모리에 항상 전체 트리를 유지하지 않고, 필요한 노드만 로딩 → 디스크 접근 시뮬레이션

✅ 구현 기능 요약

• 디스크에서 노드 저장/불러오기
• 삽입 시 노드 분할 후 저장
• 간단한 디버그용 트리 출력

💻 코드 구현

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

#define DEGREE 2
#define MAX_KEYS (2 * DEGREE - 1)
#define MAX_CHILDREN (2 * DEGREE)
#define MAX_NODES 100

int node_counter = 0;

typedef struct BTreeNode {
    int id;
    int keys[MAX_KEYS];
    int children[MAX_CHILDREN];
    int num_keys;
    int is_leaf;
} BTreeNode;

char* node_filename(int id) {
    static char filename[32];
    sprintf(filename, "node_%d.dat", id);
    return filename;
}

void save_node(BTreeNode* node) {
    FILE *fp = fopen(node_filename(node->id), "wb");
    fwrite(node, sizeof(BTreeNode), 1, fp);
    fclose(fp);
}

BTreeNode* load_node(int id) {
    FILE *fp = fopen(node_filename(id), "rb");
    if (!fp) {
        printf("파일 node_%d.dat 열기 실패\n", id);
        return NULL;
    }
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    fread(node, sizeof(BTreeNode), 1, fp);
    fclose(fp);
    return node;
}

BTreeNode* create_node(int is_leaf) {
    BTreeNode* node = (BTreeNode*)calloc(1, sizeof(BTreeNode));
    node->id = node_counter++;
    node->is_leaf = is_leaf;
    save_node(node);
    return node;
}

void traverse(int id) {
    BTreeNode* node = load_node(id);
    if (!node) return;

    for (int i = 0; i < node->num_keys; i++) {
        if (!node->is_leaf)
            traverse(node->children[i]);
        printf("%d ", node->keys[i]);
    }

    if (!node->is_leaf)
        traverse(node->children[node->num_keys]);

    free(node);
}

void split_child(int parent_id, int i, int child_id) {
    BTreeNode* parent = load_node(parent_id);
    BTreeNode* child = load_node(child_id);

    BTreeNode* z = create_node(child->is_leaf);
    z->num_keys = DEGREE - 1;

    for (int j = 0; j < DEGREE - 1; j++)
        z->keys[j] = child->keys[j + DEGREE];
    
    if (!child->is_leaf) {
        for (int j = 0; j < DEGREE; j++)
            z->children[j] = child->children[j + DEGREE];
    }

    child->num_keys = DEGREE - 1;

    for (int j = parent->num_keys; j >= i + 1; j--)
        parent->children[j + 1] = parent->children[j];
    parent->children[i + 1] = z->id;

    for (int j = parent->num_keys - 1; j >= i; j--)
        parent->keys[j + 1] = parent->keys[j];
    parent->keys[i] = child->keys[DEGREE - 1];
    parent->num_keys++;

    save_node(child);
    save_node(z);
    save_node(parent);

    free(child);
    free(z);
    free(parent);
}

void insert_non_full(int node_id, int k) {
    BTreeNode* node = load_node(node_id);
    int i = node->num_keys - 1;

    if (node->is_leaf) {
        while (i >= 0 && k < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = k;
        node->num_keys++;
        save_node(node);
        free(node);
    } else {
        while (i >= 0 && k < node->keys[i])
            i--;
        i++;

        BTreeNode* child = load_node(node->children[i]);
        if (child->num_keys == MAX_KEYS) {
            split_child(node_id, i, child->id);
            BTreeNode* updated = load_node(node_id);
            if (k > updated->keys[i])
                i++;
            free(updated);
        }
        free(child);
        insert_non_full(load_node(node_id)->children[i], k);
    }
}

void insert(int* root_id, int k) {
    BTreeNode* root = load_node(*root_id);
    if (root->num_keys == MAX_KEYS) {
        BTreeNode* s = create_node(0);
        s->children[0] = root->id;
        *root_id = s->id;
        split_child(s->id, 0, root->id);
        insert_non_full(s->id, k);
        free(s);
    } else {
        insert_non_full(root->id, k);
    }
    free(root);
}

int main() {
    int root_id;
    BTreeNode* root = create_node(1);
    root_id = root->id;
    free(root);

    int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};
    for (int i = 0; i < sizeof(keys)/sizeof(keys[0]); i++) {
        insert(&root_id, keys[i]);
    }

    printf("디스크 기반 B-Tree 중위 순회: ");
    traverse(root_id);
    printf("\n");

    return 0;
}

• node_0.dat, node_1.dat, ... 등의 파일이 생성되며 각 노드가 디스크에 저장됨
• 메모리에서는 필요한 노드만 load_node()로 로드하여 사용
• 삽입/분할 후 변경된 노드는 반드시 save_node()로 파일에 저장

코드 실행 결과

• 실행 후 현재 디렉토리에 node_*.dat 파일이 생성됨

---

[참고자료]

• CLRS: Introduction to Algorithms
• GeeksforGeeks - B-Tree
• [Jungle] Week2. 이진트리 | B-Tree

[Jungle] Week2. 이진트리 | B-Tree

• [자료구조] 그림으로 알아보는 B-Tree

[자료구조] 그림으로 알아보는 B-Tree

• B-tree(B-트리)란?

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정