如何设计 B+Tree 索引
从 MiniDB 的全表扫描失败开始，逐步长出有序叶子页、内部节点、分裂、范围扫描、回表和维护成本
阅读定位: 这页只讲数据库索引里最经典的一条线：B+Tree 为什么会从“按 key 查太慢”这个问题里长出来。它不讲全文索引、向量索引、LSM Tree 和复杂优化器，只把 MiniDB 的主键索引设计透。
一句话原则: B+Tree 不是“树结构知识点”，而是一条磁盘友好的访问路径：用少量页跳转找到目标叶子页，并且让叶子页保持有序，方便范围查询。
MiniDB 已经有 heap file 和 RID 了。现在执行 WHERE id = 10086，如果没有索引，只能从第一页扫到最后一页。
select * from entries where id = 10086
SeqScan:
for each page in entries.heap:
for each slot in page:
if row.id == 10086:
return row
| 它能工作 | 为什么不够 | 下一步需要什么 |
|---|
| 小表能查到正确结果 | 表越大越慢，查询时间和数据量线性相关 | 从 key 直接找到 RID 的访问路径 |
| 不需要额外维护结构 | 每次查询都重复做无用扫描 | 用空间和写入成本换读取速度 |
阶段验收: 你能说清：索引不是为了让数据库“更高级”，而是为了避免每次查询都重新发现数据在哪。
最直觉的索引是 Map<id, RID>。插入一行时，把 id 和 RID 记进 Map；查询时直接查 Map。
index:
1 -> RID(page=42, slot=0)
10086 -> RID(page=811, slot=4)
| 解决了什么 | 马上撞上的问题 | 为什么会引出磁盘索引 |
|---|
| 按 id 查非常快 | 重启后 Map 没了，必须重扫表重建 | 索引本身也要持久化 |
| 实现简单 | 数据多了，Map 可能放不进内存 | 索引不能假设全在内存 |
| 等值查询好用 | 按时间范围查不方便 | 索引最好保持 key 有序 |
如果把索引项按 key 排序，范围查询就很自然：找到起点后一路往后扫。但数组插入中间位置要搬动大量元素。
| 操作 | 有序数组表现 | 问题 |
|---|
| 等值查找 | 二分查找很快 | 如果数组在磁盘上，随机访问很多页仍然麻烦 |
| 范围查询 | 找到起点后顺序扫描 | 这点很好，应保留 |
| 插入新 key | 可能要移动后面大量索引项 | 写入成本太高，不适合频繁插入 |
| 页满 | 数组没有天然页分裂机制 | 需要可局部分裂的数据结构 |
这一步的教训: 一个数据库索引不能只服务查询，也要承受持续插入、删除和更新。
现在我们不维护一整条巨大数组，而是维护很多有序的 leaf page。每个 leaf page 里有一段连续 key，叶子页之间用 next 指针连起来。
Leaf Page 10:
keys: 1, 2, 5, 8
values: RID...
next: page 11
Leaf Page 11:
keys: 13, 21, 34, 55
values: RID...
next: page 12
| 设计变化 | 解决什么 | 新的问题 |
|---|
| 叶子页内部有序 | 页内可二分查找 | 要先知道应该去哪个叶子页 |
| 叶子页之间有 next 指针 | 范围扫描可以跨页向右走 | 插入分裂时要维护链表 |
| 页满时分裂 | 不用搬动整棵索引 | 分裂后父节点也要更新 |
现在问题变成：给定 key=10086，怎么知道该去哪个 leaf page？于是 B+Tree 长出 internal page。内部节点不存行地址，只存“key 范围 → 子页”。
Root:
key < 100 -> page 10
100..999 -> page 24
1000..9999 -> page 81
key >= 10000 -> page 130
Leaf page 130:
10001 -> RID(...)
10086 -> RID(page=811, slot=4)
| 为什么内部节点只做路由 | 为什么所有数据都放叶子 | 验收问题 |
|---|
| 内部节点越小，能容纳越多 key，树越矮 | 叶子页顺序连接，范围扫描更自然 | 查找 key 是否总能走到唯一叶子页 |
| 内部节点不直接返回业务记录 | 索引结构和表记录位置分离 | 更新 RID 时，叶子值是否同步变化 |
阶段验收: 你应该能画出一条查询路径：root page → internal page → leaf page → RID → heap page。
持续插入后，某个 leaf page 会满。不能整棵树重建，B+Tree 的关键动作是局部分裂。
| 分裂步骤 | 为什么这样做 | 容易错在哪里 |
|---|
| 把满叶子页分成左右两个页 | 让两个页都留出空间给未来插入 | 左右页 key 范围必须保持有序 |
| 维护 leaf next 指针 | 范围扫描不能断链 | 忘记更新 next 会让范围查询漏数据 |
| 把分裂边界 key 推给父节点 | 父节点需要知道新叶子页的路由范围 | 父节点也可能满，于是继续向上分裂 |
| 根节点满时新建根 | 树高度增加 | root page id 必须更新到 catalog / metadata |
before leaf:
[10, 20, 30, 40] insert 25
after split:
left: [10, 20, 25]
right: [30, 40]
promote separator key: 30 to parent
删除 key 后，叶子页可能太空。如果完全不管，索引会越来越稀疏；如果每次都合并，又会频繁调整树结构。
| 选择 | 适合什么 | 代价 |
|---|
| 先只标记删除 | 第一版 MiniDB，简化实现 | 空间膨胀，需要后续 vacuum / rebuild |
| 向兄弟页借 key | 兄弟页较满时 | 要更新父节点边界 key |
| 和兄弟页合并 | 两个页都较空时 | 父节点也要删除指针，可能级联调整 |
| 后台整理 | 减少前台删除成本 | 实现复杂，需要和并发控制配合 |
设计取舍: 第一版可以先不追求删除后的完美平衡，但必须承认这会带来空间膨胀和扫描成本。
插入一条记录时，存储引擎先拿到 RID，再把 key → RID 写进索引。这里最危险的是表和索引只成功一边。
| 失败场景 | 后果 | 需要谁解决 |
|---|
| 表页写了，索引页没写 | 全表扫能找到，按索引查不到 | 事务与 WAL |
| 索引页写了，表页没写 | 索引指向不存在 RID | 事务与 WAL |
| 叶子分裂写了一半宕机 | 树结构可能断裂 | 页日志、恢复和一致性检查 |
| 并发插入同一范围 | 两个事务可能同时分裂同一页 | Latch / Lock 协议 |
阶段验收: 这页不要求完整实现事务，但要求你能指出：B+Tree 不是孤立结构，它的每次修改都要和表页、Buffer Pool、WAL 协同。
叶子页里只存 key → RID 时，查到 RID 后还要回表读 heap page。如果查询只需要索引里已有的字段，就可以不回表。
| 索引叶子值 | 查询表现 | 代价 |
|---|
id -> RID | 主键查到 RID 后回表 | 索引小，但多一次 heap page 读取 |
id -> amount | 查 amount 可直接从索引返回 | 索引更大，更新 amount 要维护索引 |
(category, occurred_on) -> RID | 支持分类 + 日期范围查询 | 联合 key 的顺序会影响可用查询 |
不要误读: 覆盖索引不是“索引越多越好”。它是在读性能、写入成本、空间成本、维护复杂度之间做选择。
| 阶段 | 遇到的问题 | 长出的设计 | 真正吸收点 |
|---|
| SeqScan | 按 key 查太慢 | key → RID | 索引是访问路径 |
| 内存 Map | 重启丢失，放不下，范围查弱 | 持久有序索引 | 索引本身也要落盘 |
| 有序数组 | 插入搬动太多 | 有序叶子页 | 局部修改比全局移动更适合数据库 |
| 叶子页 | 不知道去哪个叶子 | 内部节点 | 树高换查询跳转次数 |
| 页满 | 插不进去 | 分裂和提升 separator key | B+Tree 的生命在于维护平衡 |
| 索引更新 | 表和索引可能不一致 | 事务 / WAL / Latch | 索引正确性不是单页问题 |
| 练习 | 故意制造什么失败 | 通过标准 |
|---|
| 实现单 leaf page | 随机插入 key，检查页内顺序 | 页内始终有序，查找能二分 |
| 实现 leaf split | 插满后继续插入 | 左右页有序，next 指针不断，范围扫描不漏 |
| 实现两层树 | 多个 leaf split 后查随机 key | root 能路由到正确 leaf |
| 实现根分裂 | 持续插入直到 root 满 | 树高增加，所有旧 key 仍可查 |
| 实现删除简化版 | 删除大量 key 后范围扫描 | 不返回已删除 key，并能说明空间膨胀问题 |
| 实现索引一致性测试 | 插入时模拟表写成功、索引写失败 | 能指出必须交给事务 / WAL 修复 |
如何设计存储引擎
如果你还没理解 RID、Heap File、Page、Buffer Pool 和脏页刷盘，先回到
如何设计存储引擎。
如何设计 WAL 和崩溃恢复
当 B+Tree 分裂、表页插入和索引页更新需要一起成功时，下一步看
如何设计 WAL 和崩溃恢复，把跨页一致性、commit、Redo 和 Undo 讲清楚。
总结: B+Tree 索引不是树的名词解释，而是从失败里长出来的访问路径：全表扫描太慢，于是需要 key → RID；内存 Map 不持久，于是索引要落盘；有序数组插入太贵，于是切成叶子页；叶子页太多找不到，于是长出内部节点；页满了，于是分裂；表和索引可能不一致，于是必须接事务和 WAL。