B樹 C++ 完整實現：插入、刪除、分裂與合併詳解

B樹是數據庫索引的核心數據結構，本文提供一個基於 C++ 模板的完整 B樹實現，包含插入、刪除、分裂、合併等核心操作，並詳細解析關鍵邏輯。

B樹基本性質（m=3）

• 每個節點最多 2m-1 = 5 個關鍵字
• 非根節點至少 m-1 = 2 個關鍵字
• 根節點若非葉子，至少 2 個孩子
• 所有葉子節點在同一層

核心類設計

template <class T>
class BTnode {
    friend class BTree<T>;
    bool isleaf;           // 是否葉子
    int keyNum;            // 關鍵字數量
    BTnode* parent;        // 父節點
    BTnode* pchild[6];     // 子節點指針數組 (child_max = 6)
    T keyvalue[5];         // 關鍵字數組 (key_max = 5)
};

template <class T>
class BTree {
    BTnode<T>* root;
    // 核心操作：插入、分裂、刪除、合併、查找、打印
};

關鍵操作詳解

1. 插入流程

• 若樹為空，創建根節點
• 若根節點滿，分裂根節點，樹高增加 1
• 調用 Notfull_insert 向非滿節點插入
• 遞歸下降：內部節點找孩子，葉子節點直接插入並排序
• 遇到滿節點先分裂再繼續

2. 分裂操作 SplitBlock

將滿節點 node_child 分裂為左右兩個節點，中間關鍵字上移到父節點 node_parent 的 child_index 位置：

void SplitBlock(BTnode<T>* parent, int idx, BTnode<T>* child) {
    BTnode<T>* right = new BTnode<T>();
    right->isleaf = child->isleaf;
    right->keyNum = key_min;  // 2
    
    // 複製右半部關鍵字
    for (int i = 0; i < key_min; ++i)
        right->keyvalue[i] = child->keyvalue[i + child_min];
    
    // 非葉子需複製子指針並更新父指針
    if (!child->isleaf) {
        for (int i = 0; i < child_min; ++i) {
            right->pchild[i] = child->pchild[i + child_min];
            right->pchild[i]->parent = right;
        }
    }
    child->keyNum = key_min;
    
    // 父節點騰出位置，上移中間關鍵字
    for (int i = parent->keyNum; i > idx; --i) {
        parent->keyvalue[i] = parent->keyvalue[i-1];
        parent->pchild[i+1] = parent->pchild[i];
    }
    parent->keyvalue[idx] = child->keyvalue[key_min];
    parent->pchild[idx+1] = right;
    right->parent = parent;
    parent->keyNum++;
}

3. 刪除與平衡

刪除分兩階段：

1. BTree_delete 處理根節點特殊情況（根只有一個關鍵字且孩子也剛好滿足最小度）
2. BTree_deletebalance 遞歸刪除並修復不平衡

修復策略（由易到難）：

• 兄弟節點關鍵字足夠（> key_min）：向父節點借關鍵字，兄弟節點補位
• 雙方都剛好滿足最小度：合併兩兄弟節點及父節點下移的關鍵字

4. 前驅/後繼查找

T getprev(BTnode<T>* node) {  // 左子樹最大值
    while (!node->isleaf) node = node->pchild[node->keyNum];
    return node->keyvalue[--node->keyNum];
}

T getnext(BTnode<T>* node) {  // 右子樹最小值
    while (!node->isleaf) node = node->pchild[0];
    return node->keyvalue[0];
}

完整代碼結構

代碼包含以下核心函數：

使用示例

BTree<int> tree;
tree.BTree_insert(10);
tree.BTree_insert(20);
tree.BTree_insert(5);
tree.printpoint();  // 可視化輸出樹結構

實現難點提示

• 指針操作極其繁瑣，特別是分裂/合併時的父子指針雙向維護
• 刪除時的借鍵/合併邏輯分支多，需仔細處理邊界
• 模板類編譯需注意頭文件與實現文件分離問題