B+树的概念
B+树（B+ Tree） 是一种多路平衡搜索树，也是 B树（B-Tree）的变体。它最大的特点是所有数据都存储在叶子节点，非叶子节点仅用于索引。这种结构使其在数据库和文件系统等需要大量磁盘 I/O 的场景中表现极其优异，是 MySQL InnoDB 等主流关系型数据库的默认索引结构。
核心特性
- 数据全在叶子节点：非叶子节点只存储索引键（Key）和指向子节点的指针，不存储实际数据（Data/Record）。
- 叶子节点形成链表：所有叶子节点通过指针（通常是双向链表）连接在一起，极大地优化了范围查询和排序操作。
- 高度平衡：从根节点到每个叶子节点的路径长度相同，保证了查询的时间复杂度稳定为 O(logN) 。
- 高扇出（High Fan-out）：非叶子节点可以包含成百上千个子节点指针，这使得 B+树非常“矮胖”。例如，一个 3 层的 B+树就能索引上千万条数据。
B+树 vs B树：为什么数据库偏爱 B+树？
表格
| 特性 | B树 (B-Tree) | B+树 (B+ Tree) | B+树的优势 |
|---|---|---|---|
| 数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 | 非叶子节点能容纳更多索引，树更矮，减少磁盘 I/O 次数。 |
| 范围查询 | 需要中序遍历整棵树 | 只需遍历叶子节点的链表 | 范围查询效率极高，无需回溯父节点。 |
| 查询稳定性 | 最好查根节点，最差查叶子 | 每次都必须查到叶子节点 | 查询性能极其稳定，没有忽快忽慢的情况。 |
| 磁盘预读与局部性 | 数据分散在各层 | 连续数据集中在叶子层 | 完美契合操作系统的页缓存（Page Cache）和磁盘顺序读取机制。 |
时间复杂度
- 查找、插入、删除：O(logN)
- 范围查询： O(logN+M) ，其中 M 是结果集大小。由于叶子节点是链表，找到起点后直接顺序扫描即可。
实际应用场景
- 关系型数据库索引：MySQL (InnoDB), PostgreSQL, Oracle 等底层几乎全部使用 B+树。
- 聚簇索引：叶子节点直接存放完整的行数据。
- 非聚簇索引（二级索引）：叶子节点存放主键值，查询需要“回表”。
- 文件系统：NTFS, ext4, ZFS 等使用 B+树或其变体来管理文件目录和元数据。
- NoSQL 数据库：MongoDB, Cassandra 等也广泛采用类似结构。
一个简单的 B+树示意 (阶数 m=3)
[ 10 | 20 ] <-- 根节点 (仅索引)/ | \[5|8] [12|15] [22|25] <-- 内部节点 (仅索引)/ | \ / | \ / | \[5][8] [12][15] ... [22][25] <-- 叶子节点 (存真实数据)\_____/ \_____/ \_____/<-> <-> <-> <-- 双向链表连接