Part II · 第 5 章
05

B+ 树：
在十亿行里，一步命中

如果 SQL 是“我要什么”，B+ 树就是数据库回答“我怎么少翻页”的第一把刀。它不是一棵普通树，而是一台为磁盘页、范围扫描和更新稳定性定制的查找机器。

难度 中等偏硬 用时 60-90 分钟 交互 沙盒 · 范围扫描 · fan-out 计算器 目标 从 invariant 到 I/O cost

5.1问题不是“会不会找”，
而是“翻几页”

数据库系统里，很多看似高级的概念，最后都会落到一个很朴素的问题：为了回答这个查询，我要读多少个 page？如果没有索引，查 WHERE id = 42 只能扫表。表有十亿行，就像在一栋楼里逐间敲门问“你是不是 42”。

B+ 树索引做的事情，是给这栋楼装一套目录：先看楼层，再看门牌区间，最后只敲很少几扇门。它的关键不在“树”这个形状，而在 每个节点正好是一页，节点里塞很多 key，树因此非常矮。

一口气建立直觉

B+ 树把一次查找变成：读 root page → 读几个 internal page → 读目标 leaf page。如果 fan-out 是 250，三四层就能覆盖上亿到十亿量级的记录。它赢的不是算法课里的 O(log n)，而是系统课里的 3 次 I/O，对比 100 万次 I/O。

5.2先记住这 5 条 invariant

你不需要把所有 case 背下来。真正要抓住的是 invariant：只要它们成立，查找、插入、删除都只是为了维护这些约束。

1所有真实记录都在叶子

Internal node 只做导航，不存 RID payload。

2叶子从左到右排序并串起来

范围查询不用回到 root，可以顺着 sibling pointer 扫。

3所有叶子同深度

任何 key 的查找路径长度一样，延迟稳定。

4节点至少半满

除了 root，节点不能太空，否则空间和 fan-out 都会崩。

5separator 是右子树的最小 key

遇到相等 key，向右走，才能命中正确叶子。

图 5.1B+ 树的读法。把 case 全部还原成 invariant，会比死记 split/merge 规则稳定得多。

5.3沙盒：插入、分裂、搜索、
范围扫描、删除

下面这个模型采用 CS186 常用的 order d 记法：非 root 节点最少 d 个 key，最多 2d 个 key。试着连续插入 10, 20, 5, 6, 12, 30, 7, 17，观察第一次 leaf split 如何把 separator 复制到 parent。

B+ 树操作台 live sandbox order d 可调 · 所有叶子相连
图 5.2B+ 树沙盒。这个实现真的维护 split、borrow、merge 与 sibling chain。每一步都把被访问的页高亮出来，方便你把“算法步骤”映射成“页 I/O”。
深潜 为什么 separator 是复制，不是搬走？›

叶子里的 key 是真实索引项的一部分，不能因为提升到 parent 就从 leaf 里删掉。Leaf split 后，右叶子的第一个 key 会被复制到 parent，作为导航边界。Internal split 不一样：中间 separator 本来就是导航 key，可以被推上去。

这就是 B+ tree 和很多教科书里的 B-tree 最容易混的地方：B+ tree 的数据全在 leaf，internal node 是路牌。

5.4查找路径，就是页 I/O

算法课会说 B+ 树查找是 O(log_f N)。数据库系统里，我们更关心这句话的物理版本：一次 point lookup 要读树高这么多页。如果 root 常驻 buffer pool，成本还可以再少一页。

范围查询则多了一个尾巴：先沿树高找到第一个 leaf，再顺着 leaf sibling chain 扫到范围结束。B+ 树非常适合 BETWEEN、排序输出和索引嵌套循环连接，原因就在这条 leaf chain。

cost lens

Point lookup: height 次 page read，常见情况下 root 被缓存，实际更接近 height - 1。

Range scan: height + leaf_pages_touched，如果需要回表取记录，还要加 data page I/O。

Insert/delete: 先 lookup，再修改 leaf。只有节点满/太空时，才触发 split/borrow/merge 向上传播。

5.5Fan-out：为什么十亿行也只有几层

B+ 树真正的系统魔法是 fan-out。一个 4KB page 里，如果每个 separator key 加 child pointer 只占几十字节，一个 internal page 就能指向几百个孩子。高度不是按二叉树的 2 取 log，而是按几百取 log。

Fan-out / Height Calculator cost model 拖动参数，观察树高
图 5.3树高估算器。同样是 B+ 树，page size、key width、RID/pointer width 会直接改变 fan-out，从而改变 I/O 次数。

5.6现代视角：B+ 树不是唯一答案

CS186 先讲 B+ 树，是因为它是传统 OLTP 数据库的核心索引结构。但现代存储系统里，你会经常遇到另一个选择：LSM tree。B+ 树擅长读和范围扫描，更新时原地修改页；LSM 把写入先追加到内存和日志，再批量刷成有序文件，用 compaction 慢慢整理。

Read/Write Trade-off modern angle 调整 workload
图 5.4B+Tree vs LSM。没有绝对赢家。读多、范围扫描、低延迟 point lookup 偏 B+ 树；写多、日志式吞吐、云存储友好偏 LSM。

5.7下一圈螺旋：把索引接回查询执行

学到这里，B+ 树不再是一道数据结构题。它会重新出现在后面的几章里：

  • Join: Index Nested Loop Join 的代价，取决于内表索引 lookup 有多便宜。
  • Optimizer: 选择 seq scan 还是 index scan，本质是估算 selectivity 和 I/O。
  • Transactions: 并发更新 B+ 树，需要 latch coupling 和 predicate/next-key locks。
  • Recovery: split 修改多个 page，必须能被 WAL redo/undo 正确恢复。
  • Modern systems: RocksDB、Bigtable、DynamoDB 背后很多设计都在重分配 B+Tree 和 LSM 的 trade-off。

本章压缩包

  • B+ 树是为了减少 page I/O，不是为了炫耀树结构。
  • Internal node 是导航，leaf 才有真实索引项；leaf chain 让 range scan 便宜。
  • Order d 的 split/borrow/merge 都是在维护“半满、平衡、排序”的 invariant。
  • Fan-out 很大，所以树很矮；树高直接变成 lookup 的 I/O cost。
  • B+ 树和 LSM 是读写 trade-off 的两端，不是新旧优劣关系。