多路查找树：从2-3树到B+树

多路查找树，说白了就是让每个节点多存几个键值，少长几层树高。我刚开始学数据结构时，总觉得二叉树已经够用了，直到在项目中处理百万级数据，才发现树高太深，磁盘I/O根本扛不住。嗯，这时候多路查找树就派上用场了。

为什么需要多路查找树？

你想想看，二叉查找树每个节点只存一个键，数据量大时树高就高。比如100万条数据，最坏情况下树高接近20层。每次查找都要做20次磁盘I/O，这谁受得了？

多路查找树的思路很简单：让每个节点多存几个键，多分几个叉。这样树高就降下来了。我记得有一次优化数据库索引，把树高从15层降到4层，查询速度直接提升了3倍多。

2-3树：最基础的多路树

2-3树是多路查找树的入门模型。它有两种节点：

• 2节点：存1个键，有2个子树，跟普通二叉节点一样
• 3节点：存2个键，有3个子树

所有叶子节点都在同一层，这是它最核心的性质。我在项目中用2-3树做过内存中的有序集合，插入和查找都很稳定，没有二叉树的退化问题。

2-3树的插入操作

插入时先找到叶子位置，如果叶子是2节点，直接插入变成3节点。如果叶子是3节点，就需要分裂：

1. 把3节点临时变成4节点（3个键）
2. 把中间键上移到父节点
3. 左右两个键分裂成两个2节点
4. 如果父节点也满了，继续向上分裂

我曾经在实现时踩过一个坑：分裂时忘记处理父节点指针的更新，导致树结构错乱。调试了一下午才发现。

2-3-4树：多一层容量

2-3-4树在2-3树的基础上增加了4节点：存3个键，有4个子树。说白了就是让节点能存更多数据，进一步降低树高。

节点类型	键数量	子树数量
2节点	1	2
3节点	2	3
4节点	3	4

2-3-4树的插入策略和2-3树类似，但有个技巧叫预分裂：在向下查找时，如果遇到4节点就提前分裂。这样能避免回溯分裂的麻烦。我个人习惯用这种方式实现，代码更简洁。

B树：工业级的多路查找树

B树是2-3树和2-3-4树的泛化版本。它把节点能存的键数量从固定值变成了一个范围：

• 每个节点最多存 m-1 个键（m是阶数）
• 每个节点最少存 ⌈m/2⌉ - 1 个键（根节点除外）
• 所有叶子节点在同一层

B树的设计目标很明确：减少磁盘I/O次数。每个节点的大小通常设置为一个磁盘块的大小（比如4KB），这样每次读取一个节点就是一次磁盘I/O。

B树的查找操作

// B树查找的伪代码
BTreeSearch(node, key) {
    i = 0;
    while (i < node.n && key > node.keys[i]) {
        i++;
    }
    if (i < node.n && key == node.keys[i]) {
        return node;  // 找到了
    }
    if (node.isLeaf) {
        return NULL;  // 没找到
    }
    // 递归到子树
    return BTreeSearch(node.children[i], key);
}

这段代码看起来简单，但实际实现时要注意：节点内的键是有序的，可以用二分查找优化。我一般会在节点内部用二分查找定位，比顺序查找快不少。

B+树：B树的改良版

B+树是B树的变种，它做了两个重要改动：

1. 数据只存在叶子节点：内部节点只存索引键，不存数据
2. 叶子节点用链表连接：方便范围查询

这两个改动带来了什么好处？

• 内部节点能存更多键，树高更低
• 范围查询时，找到起始位置后顺着链表走就行，不用回溯
• 所有数据都在叶子层，查询时间更稳定

多路查找树对比

类型	节点容量	数据位置	范围查询	典型应用
2-3树	1-2个键	所有节点	一般	教学、内存结构
2-3-4树	1-3个键	所有节点	一般	红黑树的等价模型
B树	m-1个键	所有节点	一般	文件系统、数据库
B+树	m-1个键	仅叶子节点	优秀	MySQL InnoDB、MongoDB

核心知识体系

下面这张图展示了多路查找树的知识脉络，从基础到应用一目了然：

实际应用中的选择

我在项目中选型时，一般遵循这几个原则：

• 内存中的有序结构：用2-3树或红黑树就够了，没必要上B树
• 磁盘上的索引：首选B+树，MySQL的InnoDB引擎就是用它
• 文件系统目录结构：B树更合适，因为不需要频繁的范围查询
• 嵌入式系统：根据存储介质选择，Flash存储用B+树，RAM够用就用2-3树

多路查找树的核心思想就一句话：用空间换时间，用节点容量换树高。在实际工程中，这个思想无处不在。你想想看，从文件系统到数据库，从内存管理到网络路由，多路查找树的身影随处可见。掌握了它，你就掌握了高效数据组织的精髓。

---

公众号:蓝海资料掘金营，微信deep3321