B+ 树
B+ 树把有序键分装在页中。内部节点用分隔键指路，叶节点保存记录键。所有叶节点深度相同，叶节点还按键序相连。点查询沿树下降；范围查询找到起点后沿叶链扫描。等值、范围查询及与索引顺序兼容的 ORDER BY 都能利用这种结构。
B+ 树如何工作
本课的阶数 m 指内部节点最多有 m 个孩子，因此稳定节点最多有 m−1 个键。三阶节点最多存两个键，第三个键触发分裂。
内部节点 [15,30] 的三个孩子分别负责 <15、15≤key<30、≥30。等于分隔键时走右侧，因为记录副本在右侧叶节点中。内部键只用于路由，不算另一条记录。
叶节点溢出时，分成左右两页，把右页的首键复制到父节点。该键仍留在右叶中。内部节点分裂时，把中间分隔键移入父节点，不在分裂后的两个内部节点中保留它。复制与移入承担不同职责，不能混用。
叶链也要改。先让新右叶的 next 指向旧后继，再让旧叶的 next 指向新右叶，否则可能丢失原来的后继。内部页分裂则要连同孩子指针一起划分。父节点收到分隔键后也可能溢出，分裂可逐层传播。根分裂会建立新根，所有叶节点的深度一起增加。
逐步演示
默认使用三阶树，操作如下：
insert 10, insert 20, insert 5, insert 15, insert 25, insert 30, search 25, range 9 27
- 插入 10、20，根叶为
[10,20]。 - 插入 5，
[5,10,20]溢出。分成[5,10]、[20]，复制 20 建立新根。 - 插入 15，左叶变成
[5,10,15]，分成[5,10]、[15]。新叶[15]先接住原后继[20]，再接到[5,10]后面。把 15 复制到根。 - 插入 25，右叶成为
[20,25]。 - 插入 30，右叶分成
[20,25]、[30]，复制 30 到根。根的[15,20,30]溢出，把中间键 20 移入新根，两侧内部节点分别只保留 15、30。
最终结构为：
[20]
/ \
[15] [30]
/ \ / \
[5,10] [15] [20,25] [30]
└────→────→────→
叶链为 [5,10] -> [15] -> [20,25] -> [30]。每个记录键只在叶层出现一次；内部的 15、20、30 是分隔键。
查找 25：在根 20 处走右侧，在内部键 30 处走左侧，在叶 [20,25] 中二分查找，共访问三页。
查询闭区间 [9,27]：先下降到左叶，以 lower bound 找到 10。输出 10，沿链输出 15，再输出 20、25，最后到达 [30]。30 超过上界，停止。结果为 [10,15,20,25]，叶间跳转三次。每个结果都重新从根查找，会失去叶链的连续扫描收益。
何时使用
B+ 树同时支持等值与有序范围查询。哈希索引适合等值查找，但不能靠哈希桶完成键序扫描。B+ 树的高扇出减少树高；真实数据库页通常能容纳远多于本课的孩子数，因此大量记录也可能只需几层。
复杂度
设记录数为 n，阶数为 m，返回记录数为 k。点查询访问 O(log_m n) 层页。不发生分裂的插入沿同一路径下降；分裂最多每层一次，页层级工作仍为 O(log_m n)。范围查询为 O(log_m n+k)：定位起点，再输出结果。
这些界限以固定阶数的教学模型或页层级访问计数为前提。页内二分查找、键和指针搬移另有 CPU 成本；把 m 当变量时不能忽略它们。访问一页也不等于一次物理磁盘读取，页可能在缓存中。界面的阶数 3–5 用于展示分裂，不是生产配置建议。
边界情况
- 空树只有根叶。查找返回未找到，范围结果为空。
- 第一次叶分裂建立新根，从一层变成两层。
- 模型只存唯一键。重复插入不改变树；真实索引可以借助记录标识等方式支持重复键。
- 缺失键只需检查路由选中的候选叶，无须遍历全部叶。
- 范围起点的 lower bound 已超过上界时，立即结束，不必沿链。
- 范围超过最大键时，在叶链尾部的空 next 处结束。
- 宽范围
range 1 99返回默认插入的全部键。输出规模仍须计入 k，不能只计算树高。 - 画布最多展示 12 条记录。达到上限后，插入按钮仍可点击并说明限制；这是绘图上限，不是算法容量。
常见错误
- 把叶分隔键移走，导致记录消失。叶分裂必须复制右叶首键。
- 在内部节点中保留已上移的中间键，破坏孩子区间划分。
- 等于分隔键时走左侧，错过右叶中的记录。
- 先覆盖旧 next，再试图读取旧后继，断开叶链。
- 对范围内每个键都从根开始查找，丢掉一次下降后顺序扫描的优势。
- 把示意页当成 PostgreSQL 或 MySQL 的字节布局。
模型范围
本课使用内存中的唯一整数键、固定阶数与溢出后立即分裂，未实现删除。它不模拟缓冲池、物理 I/O、填充率、压缩、重复键、并发锁闩、WAL、MVCC、恢复和磁盘格式。真实叶节点还可能保存记录内容或记录地址，扇出也更大。画布展示路由、分裂和叶链的约束。