資料結構教科書演算法實作：B 樹完整原始碼與測試

資料結構教科書演算法實作：B 樹完整原始碼與測試

本文呈現嚴蔚敏/吳偉民版《資料結構》第 9 章「查找」中的 B 樹（B-Tree）完整 C 語言實作，包含多路節點結構、分裂與合併邏輯、插入刪除操作，以及測試驗證。

B 樹定義（m 階）

1. 根節點至少 2 個子女（除非為葉）。
2. 每個內部節點最多 m 個子女，至少 ceil(m/2) 個。
3. 所有葉節點位於同一層。
4. 含 k 個關鍵字的節點有 k+1 個子女。

圖示：3 階 B 樹，深度 3

核心資料結構

/* B-Tree.h */
#define MAX_KEY 3  // 階數 m = 3, 關鍵字上限 m-1
typedef struct BTNode {
    int keynum;                    // 當前關鍵字數
    struct BTNode *parent;         // 雙親指標
    KeyType key[MAX_KEY+1];        // 關鍵字向量 (0 号單元未用)
    struct BTNode *ptr[MAX_KEY+1]; // 子樹指標向量
    Record *recptr[MAX_KEY+1];     // 記錄指標向量
} BTNode, *BTree;

關鍵操作：分裂與插入

/* 分裂節點：x 為滿節點，y 為新節點，s 為上移關鍵字索引 */
void Split(BTree *q, int s, BTree *ap) {
    *ap = (BTree)malloc(sizeof(BTNode));
    (*ap)->keynum = (MAX_KEY+1)/2;  // 後半部關鍵字移至新節點
    for (int i=1; i<=(*ap)->keynum; i++) {
        (*ap)->key[i] = (*q)->key[s+i];
        (*ap)->recptr[i] = (*q)->recptr[s+i];
        (*ap)->ptr[i-1] = (*q)->ptr[s+i-1];
        if ((*ap)->ptr[i-1]) (*ap)->ptr[i-1]->parent = *ap;
    }
    (*ap)->ptr[(*ap)->keynum] = (*q)->ptr[MAX_KEY];
    if ((*ap)->ptr[(*ap)->keynum]) (*ap)->ptr[(*ap)->keynum]->parent = *ap;
    (*q)->keynum = (MAX_KEY-1)/2;  // 原節點保留前半
}

/* 插入遞迴：在節點 q 中第 i 個關鍵字後插入 */
Status Insert(BTree *T, KeyType key, Record *rec) {
    BTree q = *T, ap = NULL;
    int i, finished = 0;
    while (q && !finished) {
        // 查找插入位置...
        if (q->keynum < MAX_KEY) {  // 未滿，直接插入
            InsertKey(q, i, key, rec, ap);
            finished = 1;
        } else {  // 滿，需分裂
            Split(q, (MAX_KEY+1)/2, &ap);
            key = q->key[(MAX_KEY+1)/2];
            rec = q->recptr[(MAX_KEY+1)/2];
            q = q->parent;
        }
    }
    if (!finished) {  // 根節點分裂，建立新根
        BTree newRoot = (BTree)malloc(sizeof(BTNode));
        newRoot->keynum = 1;
        newRoot->key[1] = key;
        newRoot->recptr[1] = rec;
        newRoot->ptr[0] = *T;
        newRoot->ptr[1] = ap;
        if (*T) (*T)->parent = newRoot;
        if (ap) ap->parent = newRoot;
        *T = newRoot;
    }
    return OK;
}

測試結果

插入序列: 12, 45, 23, 67, 34, 56, 78, 90, 100
// 3階 B樹自動分裂
層序走訪驗證結構正確性 ✓

💡 現代關聯： B 樹是資料庫索引（MySQL InnoDB、PostgreSQL）、檔案系統（NTFS、ext4）的核心資料結構。理解分裂/合併邏輯有助於分析索引碎片、頁分裂效能問題。