數據結構：2-3-4 樹和 B 樹

我們為什么需要 2-3-4 樹？

2-3-4 樹的插入操作

從零推導代碼

B 樹 (B-Tree)

從零推導代碼

我們沿著自平衡樹的演化路徑繼續前進。我們已經學習了 2-3 樹如何通過“分裂與提升”來替代 AVL 樹的“旋轉”，但其修復過程是“自下而上”的。現在，我們來探討一種更主動、更高效的平衡策略，它直接引出了 B 樹的核心思想。

我們為什么需要 2-3-4 樹？

👉 回顧 2-3 樹的插入：我們先向下遍歷到葉子節點，執行插入。如果葉子節點（一個 3-節點）溢出，我們就分裂它，然后將一個 key 向上提升。

這個提升過程可能會引發連鎖反應，導致一路“分裂-提升”回到根節點。這是一個自下而上 (bottom-up) 的修復過程。

數據結構：2-3樹的插入 (Insertion)-CSDN博客

這個過程包含兩個階段：

第一階段：從根向下遍歷，找到插入點。
第二階段：如果發生分裂，再從葉子一路向上返回，進行修復。在最壞的情況下，我們等于把從根到葉的路徑走了兩遍。

? 提出新問題：有沒有辦法只遍歷一次就完成插入和平衡？我們能否在向下遍歷的過程中，就“預處理”好路徑，確保當我們最終到達葉子節點時，它一定有空間？

💡解決方案：“主動分裂”

這個想法非常巧妙：在我們自上而下 (top-down) 的遍歷路徑上，一旦遇到一個“滿”的節點，就立刻主動將它分裂，然后再繼續向下走。

在 2-3 樹里，“滿”的節點是 3-節點。但如果我們分裂一個 3-節點，提升的 key 需要插入到它的父節點中。如果父節點也是一個 3-節點，那不是又回到原點了嗎？

? 為了讓這個策略萬無一失，我們需要引入一種新的節點類型，讓“滿”這個概念更清晰。我們引入 4-節點 (4-node)。

我們用例子：依次插入：10, 20, 25, 30, 40, 50

🌳 對照圖：Bottom-up vs Top-down

插入 10
普通:          [10]             
主動:          [10]             插入 20
普通:          [10 | 20]        
主動:          [10 | 20]        插入 25
普通:   葉子溢出再分裂            主動:   根滿 -> 先分裂[20]                          [20]/   \                        /     \[10]   [25]                  [10]     [25]插入 30
普通:         [20]                  主動:         [20]/   \                                /   \[10]  [25 | 30]                      [10]  [25 | 30]插入 40
普通:   到達右葉溢出后分裂          主動:   下探前發現右葉滿 -> 先分裂[20 | 30]                              [20 | 30]/    |    \                            /    |    \[10]  [25]  [40]                      [10]  [25]  [40]插入 50
普通:         [20 | 30]               主動:         [20 | 30]/    |    \                            /    |    \[10]  [25]  [40 | 50]                 [10]  [25]  [40 | 50]

一眼看出區別

25 插入時：
- 普通插入：先插到 [10|20]，發現滿了，溢出后分裂。
- 主動分裂：走到 [10|20] 時，先分裂再繼續走。
40 插入時：
- 普通插入：一路插到 [25|30]，插入變成 [25|30|40] 后，再分裂。
- 主動分裂：往下走時，看到 [25|30] 已滿，提前分裂，因此不需要回溯。
最終樹：兩者完全相同，但過程不同。

4-節點 (4-node)：包含 3 個 key，有 4 個孩子。

現在，一棵 2-3-4 樹就誕生了。它的節點可以是 2-節點、3-節點或 4-節點。它的“完美平衡”規則（所有葉子在同一層）保持不變。

2-3-4 樹的插入操作

它的插入算法完全體現了“主動分裂”的思想，從而避免了向上的連鎖反應。

算法推導：

定義“滿”節點：在 2-3-4 樹中，只有 4-節點是“滿”的。
向下遍歷：從根節點開始，尋找 key 的插入路徑。
主動分裂：在遍歷路徑上，只要遇到一個 4-節點，就立即執行分裂。
- 將 4-節點的中間 key 向上提升到其父節點。
- 剩下的兩個 key 分裂成兩個 2-節點，并接收原來 4-節點的 4 個孩子。

🔍分裂的優雅之處：

當我們分裂一個 4-節點時，它的父節點是什么狀態？因為我們是自上而下分裂的，所以父節點一定不是一個 4-節點（如果是，它早被分裂了）。
這意味著，父節點必然是 2-節點或 3-節點，它保證有空間來接收從下面提升上來的 key！
因此，分裂操作永遠不會向上傳播。它是一個局部的、常數時間的操作。

?? 當我們最終到達葉子節點時，由于我們一路掃清了所有 4-節點，這個葉子節點必然不是 4-節點。它必定有空間。

最終直接將 key 插入這個有空間的葉子節點即可。

2-3-4 樹的插入操作通過“自上而下”的主動分裂，將一個可能需要向上回溯的復雜過程，變成了一個單次向下遍歷的簡單過程，效率更高。

從零推導代碼

步驟 1: 節點結構

我們需要一個能容納 3 個 key 和 4 個 children 的結構。

// 2-3-4 樹的節點結構
struct Node {int numKeys;int keys[3];Node* children[4];Node* parent; // 仍然有用，尤其是在分裂時Node(int key, Node* p = nullptr) {numKeys = 1;keys[0] = key;parent = p;for (int i = 0; i < 4; ++i) children[i] = nullptr;}// ... 其他輔助函數 ...bool isLeaf() const { return children[0] == nullptr; }void sort() { std::sort(keys, keys + numKeys); }
};

這個結構和我們之前為 2-3 樹設計的“溢出”結構幾乎一樣，但在 2-3-4 樹中，這是它的標準形態。

步驟 2: 插入入口和分裂邏輯

class Tree234 {
private:Node* root;// 分裂函數是核心void splitChild(Node* parent, int childIndex);public:Tree234() : root(nullptr) {}void insert(int key);
};void Tree234::insert(int key) {if (root == nullptr) {root = new Node(key);return;}Node* current = root;while (true) {// ----------------------------------------------------// 第一步：主動分裂滿節點// ----------------------------------------------------if (current->numKeys == 3) {// 如果根節點是 4-節點，特殊處理if (current == root) {Node* newRoot = new Node(current->keys[1]);splitChild(newRoot, 0); // 偽代碼，實際更復雜root = newRoot;} else {// 分裂內部節點// (這需要找到 current 在其父節點中的索引，然后分裂)}// 分裂后，需要從父節點重新開始判斷往哪走，邏輯復雜// 讓我們換一種更優雅的實現方式}// 如果是葉子節點，插入并結束if (current->isLeaf()) {current->keys[current->numKeys] = key;current->numKeys++;current->sort();return;}// ----------------------------------------------------// 第二步：繼續向下遍歷// ----------------------------------------------------// (找到正確的孩子，current = child)}
}

面的實現思路暴露了一個問題：在循環中分裂當前節點 current 后，需要重新調整 current 指針，代碼會變得混亂。B 樹的實現給出了一個更優雅的解決方案，我們馬上會看到。

2-3-4 樹的關鍵思想：它是 B 樹的一個具體實例，并且它與另一種著名的自平衡樹——紅黑樹（Red-Black Tree）是等價的，可以相互轉換。它最重要的貢獻是引入了自上而下的主動修復思想。

B 樹 (B-Tree)

我們從 BST 開始，為了平衡引入了 AVL 樹（旋轉），然后探索了 2-3 樹（分裂），再到 2-3-4 樹（主動分裂）。這些結構都假設數據存儲在內存 (RAM) 中。在內存中，指針跳轉和 key 的比較速度都很快。

當數據量巨大，無法全部放入內存，必須存儲在磁盤 (Hard Disk Drive, HDD) 或 固態硬盤 (Solid State Drive, SSD) 上時，游戲規則徹底改變了。

根本矛盾：CPU 訪問內存的速度，比訪問磁盤的速度要快數萬倍甚至百萬倍。
瓶頸分析：在對樹進行操作時，從磁盤讀取一個節點（Node）到內存中，是一次磁盤 I/O。這個 I/O 操作的時間開銷，遠遠超過節點加載到內存后，我們對它進行的所有 key 的比較操作。

?? 既然磁盤 I/O 是最昂貴的操作，那么我們的算法設計的核心目標必須是：盡可能地減少磁盤 I/O 的次數。

💡?如何減少 I/O 次數？

在樹的查找過程中，I/O 的次數正比于樹的高度。
因此，我們必須不惜一切代價降低樹的高度。
思想飛躍：如何極限地壓縮樹的高度？讓樹變得極度地“矮胖”。怎么實現？讓每個節點都變得巨大，可以容納海量的 key！

? B 樹的誕生 B 樹就是這個思想的直接產物。它是一個廣義的 2-3-4 樹。我們不再局限于 2、3、4 這幾個數字，而是定義一個度 (degree) t。

每個節點最少有 t-1 個 key，最多有 2t-1 個 key。
每個節點最少有 t 個孩子，最多有 2t 個孩子（根節點除外）。
關鍵設計：t 的選擇，通常使得一個大小為 2t-1 的 B 樹節點，其總體積正好等于一個磁盤頁（Page）的大小（例如 4KB, 8KB, 16KB）。

📌我們每次執行一次磁盤 I/O，就能將成百上千個 key 加載到內存中。這使得樹的分支因子（branching factor）極大，樹的高度被極度壓縮。一個存儲了上億個條目的 B 樹，其高度可能只有 3 或 4 層！這意味著最多只需要 3-4 次磁盤讀取就能找到任何數據。

B 樹是為外部存儲而生的終極平衡查找樹。它通過讓節點大小與磁盤塊大小相匹配，將樹高壓縮到極致，從而最小化昂貴的磁盤 I/O 操作。

從零推導代碼

步驟 1: 節點結構

key 和 children 的數量不再固定，必須是動態分配的。

// B 樹的節點
class BTreeNode {
public:int t;            // 最小度 (Minimum degree)int numKeys;      // 當前 key 的數量int* keys;        // key 數組 (大小為 2t-1)BTreeNode** children; // 孩子指針數組 (大小為 2t)bool isLeaf;      // 是否是葉子節點BTreeNode(int degree, bool leaf) {t = degree;isLeaf = leaf;// 根據度 t 動態分配內存keys = new int[2 * t - 1];children = new BTreeNode*[2 * t];numKeys = 0;}// ... 需要析構函數來釋放內存 ...
};

代碼解釋：

t (通常稱為最小度) 是 B 樹最重要的參數。
keys 和 children 都是動態分配的指針，它們的大小由 t 決定。
isLeaf 標志非常重要。B 樹明確區分葉子和內部節點，這能簡化很多操作。

步驟 2: 插入操作的整體框架

B 樹的插入完美地運用了 2-3-4 樹的“自上而下主動分裂”思想。

class BTree {
private:BTreeNode* root;int t;// 私有輔助函數void insertNonFull(BTreeNode* node, int key);void splitChild(BTreeNode* parent, int childIndex);public:BTree(int degree) {root = nullptr;t = degree;}void insert(int key);
};void BTree::insert(int key) {// ----------------------------------------------------// 第一步：處理根節點// ----------------------------------------------------if (root == nullptr) {root = new BTreeNode(t, true);root->keys[0] = key;root->numKeys = 1;return;}// ----------------------------------------------------// 第二步：如果根節點滿了，必須先分裂根// 這是保證“父節點必有空間”的前提// ----------------------------------------------------if (root->numKeys == 2 * t - 1) {// 創建一個新的根節點BTreeNode* newRoot = new BTreeNode(t, false); // 新根不是葉子newRoot->children[0] = root;// 分裂舊的根splitChild(newRoot, 0);// 更新樹的根root = newRoot;// 現在從新根開始，為 key 找到正確的插入路徑insertNonFull(root, key);} else {// 如果根沒滿，直接從根開始尋找插入位置insertNonFull(root, key);}
}

步驟 3: 核心輔助函數 splitChild 和 insertNonFull

// 分裂父節點的第 i 個孩子（這個孩子必須是滿的）
void BTree::splitChild(BTreeNode* parent, int i) {BTreeNode* fullChild = parent->children[i];// 1. 創建新的兄弟節點BTreeNode* newSibling = new BTreeNode(t, fullChild->isLeaf);newSibling->numKeys = t - 1; // B樹分裂后，每個新節點有 t-1 個 key// 2. 將滿孩子節點的后 t-1 個 key 復制到新兄弟節點for (int j = 0; j < t - 1; j++) {newSibling->keys[j] = fullChild->keys[j + t];}// 3. 如果滿孩子不是葉子，將其后 t 個孩子指針復制到新兄弟if (!fullChild->isLeaf) {for (int j = 0; j < t; j++) {newSibling->children[j] = fullChild->children[j + t];}}// 4. 更新滿孩子節點的 key 數量fullChild->numKeys = t - 1;// 5. 將父節點中，i 位置之后的孩子指針向后移動一位for (int j = parent->numKeys; j >= i + 1; j--) {parent->children[j + 1] = parent->children[j];}// 6. 將新兄弟節點連接到父節點parent->children[i + 1] = newSibling;// 7. 將父節點中，i 位置之后的 key 向后移動一位for (int j = parent->numKeys - 1; j >= i; j--) {parent->keys[j + 1] = parent->keys[j];}// 8. 將滿孩子節點的中間 key 提升到父節點parent->keys[i] = fullChild->keys[t - 1];parent->numKeys++;
}// 在一個“保證不滿”的節點中插入 key
void BTree::insertNonFull(BTreeNode* node, int key) {int i = node->numKeys - 1;// ----------------------------------------------------// 情況一：當前節點是葉子節點// ----------------------------------------------------if (node->isLeaf) {// 從后往前找到 key 的插入位置，并移動元素while (i >= 0 && node->keys[i] > key) {node->keys[i + 1] = node->keys[i];i--;}node->keys[i + 1] = key;node->numKeys++;return;}// ----------------------------------------------------// 情況二：當前節點是內部節點// ----------------------------------------------------// 找到 key 應該插入的子樹while (i >= 0 && node->keys[i] > key) {i--;}i++; // i 現在是目標子樹的索引// 檢查目標子樹是否已滿if (node->children[i]->numKeys == 2 * t - 1) {// 如果滿了，就地分裂splitChild(node, i);// 分裂后，父節點增加了一個key，需要重新判斷應該去哪個子樹if (key > node->keys[i]) {i++;}}// 遞歸地向“保證不滿”的子樹插入insertNonFull(node->children[i], key);
}

代碼解釋：

insert: 它的唯一職責是確保根節點在調用 insertNonFull 之前不是滿的。它通過預先分裂根節點來做到這一點，這是整個算法優雅的關鍵。
insertNonFull: 這是遞歸的主體。它只處理不滿的節點。在向下遞歸之前，它會“偵察”下一層的節點。如果目標子節點是滿的，它會調用 splitChild 來處理，然后再安全地遞歸下去。
splitChild: 這是 B 樹的核心操作。它精確地執行“分裂-提升”的邏輯，涉及到大量的數組操作，將一個滿的節點分裂成兩個半滿的節點，并將一個 key 提升給父節點。