Appearance
B+ 树
为什么需要B+ 树
B 树虽然已经大幅降低了磁盘 I/O 次数，但在实际数据库系统中仍有两个痛点：范围查询效率低（需要中序遍历整棵树）、数据分散在所有节点（缓存命中率不理想）。
B+ 树正是为解决这些问题而设计的变体。它把所有数据都下沉到叶子节点，并用链表将叶子串联起来，从而天然支持高效的顺序访问和范围查询。这也是几乎所有关系型数据库（MySQL InnoDB、PostgreSQL）选择 B+ 树作为索引结构的根本原因。408 考研中，B+ 树与 B 树的对比是高频考点。
核心思想
B+ 树的核心特点：
- 所有数据存储在叶子节点：内部节点仅保存索引（关键字副本），不存放实际数据记录
- 叶子节点通过指针依次链接：形成一个有序链表，支持顺序遍历
- 查找必须走到叶子：无论目标是否在内部节点出现，都要一路查到叶子才能获取数据
B+ 树的结构示意：
[30 | 60] ← 内部节点（仅索引）
/ | \
[10|20] [30|50] [60|80] ← 内部节点（仅索引）
/ | \ / | \ / | \
[叶] → [叶] → [叶] → [叶] ← 叶子节点（存数据，链表相连）交互可视化
通过下方的交互动画，你可以逐步观察B+ 树的执行过程：
操作详解
B+ 树的结构
一棵 m 阶 B+ 树满足以下性质：
- 每个内部节点最多有 m 棵子树（m 个指针）
- 根节点至少有 2 棵子树（除非整棵树只有一个叶子）
- 除根外的内部节点至少有 ⌈m/2⌉ 棵子树
- 内部节点的关键字个数 = 子树个数（注意：B 树中关键字个数 = 子树个数 - 1）
- 所有叶子节点在同一层，包含全部关键字及指向数据记录的指针
- 叶子节点之间通过顺序指针链接成有序链表
关键步骤（查找过程）：
- 从根节点开始，在当前节点的关键字中确定搜索方向
- 沿指针向下进入子节点，重复比较
- 必须到达叶子节点才能确认关键字是否存在并获取数据
- 若在叶子中找到目标关键字，查找成功；否则查找失败
B 树 vs B+ 树
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 |
| 内部节点作用 | 既是索引又存数据 | 纯索引，不存数据 |
| 关键字个数 | n 个关键字对应 n+1 棵子树 | n 个关键字对应 n 棵子树 |
| 关键字是否重复 | 关键字不重复 | 内部节点的关键字会在叶子中再次出现 |
| 查找路径 | 可能在任意层命中 | 必须查到叶子层 |
| 查找性能 | 不稳定（最好 O(1)，最坏 O(log n)） | 稳定（每次都是 O(log n)） |
| 叶子节点链表 | 无 | 有，叶子按顺序链接 |
| 范围查询 | 需中序遍历，效率低 | 沿叶子链表扫描，效率高 |
| 内部节点扇出 | 较小（节点同时存数据，占空间） | 较大（纯索引，单节点容纳更多关键字） |
数据库索引应用
数据库选择 B+ 树而非 B 树作为索引结构，原因如下：
- 磁盘 I/O 更少：内部节点不存数据，同样大小的磁盘页可以容纳更多关键字，树的高度更低，磁盘读取次数更少
- 范围查询高效：
SELECT * FROM t WHERE id BETWEEN 10 AND 50只需定位到叶子节点 10，然后沿链表顺序扫描到 50 即可 - 查询性能稳定：每次查询都走到叶子，路径长度一致，响应时间可预测
- 全表扫描友好：遍历所有叶子节点的链表即可完成全表顺序扫描，无需遍历整棵树
在 MySQL InnoDB 中，聚簇索引的叶子节点直接存放整行数据，非聚簇索引的叶子节点存放主键值（需要回表查询）。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log n) | 每次都从根到叶，路径长度稳定 |
| 插入 | O(log n) | 找到叶子后插入，可能引发分裂向上传播 |
| 删除 | O(log n) | 找到叶子后删除，可能引发合并向上传播 |
| 范围查询 | O(log n + k) | 定位起点 O(log n)，沿链表扫描 k 个结果 |
空间复杂度：O(n)，所有关键字存储在叶子节点中，内部节点额外存储索引副本。
考研高频考点
- ⭐ B+ 树与 B 树的区别（选择题/简答题必考，重点记忆对比表）
- ⭐ B+ 树查找必须到叶子节点（判断题高频陷阱）
- ⭐ B+ 树中内部节点关键字个数 = 子树个数（与 B 树不同，易混淆）
- ⭐ 为什么数据库索引使用 B+ 树（简答题，从磁盘 I/O、范围查询、稳定性角度回答）
- 叶子节点链表的作用（范围查询、顺序遍历）
- m 阶 B+ 树非根内部节点的关键字数范围：⌈m/2⌉ ~ m