《資料結構》課本源碼解析：B+ 樹查找算法完整實現（嚴蔚敏版第 9 章）

《資料結構》課本源碼解析：B+ 樹查找算法完整實現（嚴蔚敏版第 9 章）

B+ 樹是檔案系統與資料庫索引的核心資料結構。本文基於嚴蔚敏/吳偉民版《資料結構》第 9 章源碼，系統解析 B+ 樹定義、與 B 樹差異、關鍵操作邏輯與測試驗證。

B+ 樹核心特性（vs B 樹）

節點結構定義

// B+Tree.h
#define MAX_KEYS 3  // 階數 m = 4，最多 3 個關鍵字

typedef struct BPNode {
    int keynum;                    // 當前關鍵字數
    struct BPNode *parent;         // 雙親指針
    KeyType key[MAX_KEYS + 1];     // 關鍵字向量 (0 閒置)
    struct BPNode *ptr[MAX_KEYS + 1]; // 子樹指針
    Record *recptr[MAX_KEYS + 1];  // 記錄指針 (僅葉節點有效)
    struct BPNode *next;           // 葉節點鏈表指針
} BPNode, *BPTree;

核心操作：查找

// B+Tree.c
Result SearchBPTree(BPTree T, KeyType K) {
    BPTree p = T, q = NULL;
    int found = 0, i = 0;

    while (p && !found) {
        i = SearchNode(p, K);  // 節點內二分/順序查找
        if (i > 0 && i <= p->keynum && p->key[i] == K) found = 1;
        q = p;
        p = p->ptr[i];         // 移至子樹
    }

    if (found) {
        // 非葉節點命中，需繼續下沉至葉節點獲取記錄指針
        while (p) {
            q = p;
            p = p->ptr[0];  // 最左子樹
        }
        return (Result){q, SearchNode(q, K), 1};
    } else {
        return (Result){q, i, 0}; // 返回插入位置
    }
}

插入與分裂邏輯

1. 查找定位葉節點插入位置
2. 若節點未滿（keynum < m-1），直接插入有序位置
3. 若節點已滿，分裂：
   • 建立新節點，將後一半關鍵字/指針移入
   • 中間關鍵字上移至雙親（B+ 樹特有：上移關鍵字在葉節點仍保留副本）
   • 遞歸處理雙親分裂，可能增加樹高
4. 維護葉節點鏈表 next 指針

刪除與合併/借用邏輯

1. 查找定位葉節點關鍵字
2. 刪除關鍵字與記錄指針
3. 若節點關鍵字數 < ⌈m/2⌉ - 1（下溢），嘗試：
   • 借用：相鄰兄弟節點富餘，從兄弟借一關鍵字，雙親關鍵字下旋
   • 合併：兄弟也剛好達下限，合併兩節點，刪除雙親分隔關鍵字，遞歸向上

測試驗證

// B+Tree-main.c
int main() {
    BPTree T = NULL;
    // 讀取測試數據 TestData_Table.txt
    // 依次插入、查找、遍歷葉節點鏈表驗證有序性
    // 輸出樹結構圖形化表示
}

測試數據（TestData_Table.txt）：

25 30 40 50 60 70 80 90 100
10 20 30 40 50 60 70 80 90
...

測試結果：

• 插入序列構建平衡 B+ 樹
• 查找既有/不存在關鍵字均正確返回
• 葉節點鏈表遍歷輸出嚴格遞增序列
• 範圍查詢（如 30-70）通過鏈表 O(k) 完成

工程落地要點

• 磁碟友好：節點大小對齊頁面（4KB），單次 I/O 讀取一節點
• 並發控制：鎖耦合、B-link 樹、樂觀鎖
• 批量操作：批次插入/刪除減少分裂合併頻率
• 壓縮技術：前綴壓縮、差值編碼降低節點體積

B+ 樹以「非葉純索引、葉節全數據、葉鏈支援範圍」三大特性，成為關係型資料庫（MySQL InnoDB、PostgreSQL）、檔案系統（NTFS、ext4、ReFS）、鍵值存儲（LevelDB、RocksDB）的標準索引結構。掌握其核心邏輯，是後端存儲引擎開發的必修課。