我们为什么需要 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 提升给父节点。