4.2 B+ 树索引：页、键序与执行代价

查询量增长后，档案员不愿再逐页翻找记录；你们要设计一棵既适合磁盘页面又能持续更新的索引。

B+ 树适合 database index，不只是因为查找高度近似 logarithmic，还因为它把高 fan-out、ordered leaves、page split 和 concurrency control 组合成可持续更新的 on-disk structure。

逻辑结构

root/internal pages: separator keys + child pointers
                    /              \
internal pages: ...                  ...
               /                       \
leaf pages: [k, payload] <-> [k, payload] <-> ...

共同性质：

• tree 保持平衡，所有 leaves 位于同一高度；
• internal nodes 用 separator keys 导航；
• leaves 按 key order 保存 entries；
• adjacent leaves 有 sibling linkage 或等价 traversal mechanism，便于 range scan；
• node 通常按 database page 管理。

“B+ tree 只有 leaf 存 value”是概念模型。真实 internal page 除 separator/child 外还包含 header、high key、sibling/link、prefix-compression 或 concurrency metadata；leaf payload 也因 clustered/secondary/heap index 而异。

Fan-out 与高度

fan-out 不是 page_size / key_size：internal entry 还需 child pointer、line pointer、header、alignment，key 也可能 variable-length 或 prefix-compressed。

若 average fan-out 为 f、leaf capacity 为 l、rows 为 N，高度数量级很小：

leaf_pages ≈ ceil(N / l)
internal levels ≈ log_f(leaf_pages)

但“一棵三层树 = 三次磁盘 I/O”仍不成立：root/internal pages 常驻 cache，leaf 也可能命中；另一方面一次 lookup 还可能需要 heap/clustered lookup、visibility check、overflow read 或 lock wait。

Point lookup

node = root
while node is internal:
    choose child range containing search_key
    node = fetch(child_page)
search leaf for matching key entries

non-unique index 可能返回多个 entries。MVCC engine 还需判断对应 row version 是否对当前 snapshot visible。

SQL：

CREATE INDEX idx_quests_adventurer
ON quests (adventurer_id);

SELECT quest_id, status, reward_cents
FROM quests
WHERE adventurer_id = 42;

optimizer 是否选择 index 取决于 table size、selectivity、correlation、statistics、required columns 与 cache/cost model。建了 index 不保证使用。

Range scan

CREATE INDEX idx_items_type_value_id
ON vault_items (item_type_id, value_cents DESC, item_id DESC);

SELECT item_id, name, value_cents
FROM vault_items
WHERE item_type_id = 1
  AND value_cents BETWEEN 50000 AND 200000
ORDER BY value_cents DESC, item_id DESC;

engine 先定位 lower/upper boundary，再沿 leaf order 扫描符合 entries。若 index order 同时满足 ORDER BY，可避免额外 sort；但 name 不在 key/payload 时仍可能访问 base table。

range scan 成本随命中 entries 与 heap locality 增长。返回 table 大部分 rows 时，sequential scan 可能更便宜。

Composite key 顺序

index (a, b, c) 的 order 首先按 a，再在相同 a 中按 b，然后 c。常见有效访问包括：

• a = ?；
• a = ? AND b = ?；
• a = ? AND b BETWEEN ...；
• 某些 engine 可用 skip scan 等扩展处理缺失 leading column，但不能当作通用保证。

“等值 columns 全放前、range column 最后”是常见起点，不是完整法则。还要考虑 ORDER BY、covering、selectivity、write cost、compression 和其他 queries。

Insert 与 page split

1. 定位 target leaf；
2. 在 page 有空间时插入；
3. 空间不足时分配 sibling，并重新分配 entries；
4. 更新 parent separator；
5. parent 也可能 split，root split 会增加高度。

真实实现必须处理 concurrent readers/writers。B-link tree/high-key/sibling-link、latch coupling、optimistic traversal 和 WAL 等机制让 search 在 split 进行时仍能找到正确 page。

随机 key 不等于“每次都 split”，sequential key 也不等于无代价：右侧热点、page latch contention、append pattern 和 replication 都需测量。随机 UUID 可能降低 locality、增加 working set 与 split，但影响依赖 key encoding、fill factor、engine 和 workload。不要脱离产品与数据规模给出绝对结论。

Delete、merge 与 bloat

delete 通常先标记/移除 leaf entry；立即 merge 每个低 occupancy page 会导致结构抖动，因此 engine 可能延迟 cleanup、reuse space 或只在 maintenance/rebuild 时紧缩。

MVCC 使旧 row/index version 在不再被任何 snapshot 需要前不能回收。PostgreSQL 依靠 VACUUM 等清理 dead tuples；InnoDB 有自己的 purge 机制。长期 transaction 会延迟回收并放大 storage/cache 压力。

Clustered 与 heap-organized

InnoDB

InnoDB table 的 clustered index 通常由 primary key 组织，leaf 包含 row data。secondary index leaf 保存 secondary key 与 primary-key columns，因此：

• primary key 宽度会复制进 secondary indexes；
• secondary lookup 取得 primary key 后，常需再查 clustered index；
• 若所需 columns 已由 secondary entry 覆盖，可能避免额外 lookup。

没有显式 primary key 时的 clustered-key selection 有产品规则，应以目标 MySQL 版本官方文档为准，不应依赖隐藏 ID 作为应用契约。

PostgreSQL

PostgreSQL 普通 table 是 heap-organized，B-tree leaf 指向 heap tuple identifier。index-only scan 还需 visibility information；即便 index 包含所有查询 columns，也不保证完全不访问 heap。

PostgreSQL CLUSTER 可以按某 index 一次性重排 table，但不会像 InnoDB clustered index 那样持续维护物理顺序。

Covering/index-only

“覆盖”是 query 与 index 的关系，不是 index 固有标签。某 query 所需 predicate、join、output columns 都能从 index 获取时，engine 才可能采用 index-only strategy。

CREATE INDEX idx_quests_cover
ON quests (adventurer_id, status)
INCLUDE (reward_cents);

INCLUDE 是 PostgreSQL 等产品的 feature，MySQL index syntax/leaf payload 不同。included columns 增大 index 并增加 write cost；必须用真实 plan 验证收益。

看计划，不猜计划

PostgreSQL：

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT quest_id, status, reward_cents
FROM quests
WHERE adventurer_id = 42;

ANALYZE 会实际执行 query。对 write statement、昂贵查询和 production 数据使用前必须确认副作用和负载。重点比较 estimated vs actual rows、loops、heap fetches、buffers 与 execution time。

SQLite：

EXPLAIN QUERY PLAN
SELECT item_id, name, value_cents
FROM vault_items
WHERE item_type_id = 1
ORDER BY value_cents DESC, item_id DESC;

不同系统的 plan vocabulary 和 cost units 不可直接横比。

Index review 清单

• query 的 predicate、join、order 与 output 是什么；
• leading key order 是否匹配重要 access pattern；
• selectivity/cardinality estimate 是否可靠；
• 是否与现有 index 冗余；
• row write 会维护多少 indexes；
• index size、cache residency 与 bloat；
• unique constraint 是否属于 correctness，而非仅 performance；
• range/pagination 是否有稳定 tie-breaker；
• representative parameters 下实际 plan 是否稳定。

本课小结

B+ tree 把 ordered keys 映射到 page hierarchy，但查询代价不只等于树高。leaf payload、heap locality、MVCC visibility、cache 和 result cardinality 都会决定实际 I/O。下一课解释 WAL 如何让 dirty page 延迟写回，同时仍能在 crash 后恢复一致状态。

官方资料入口

• PostgreSQL B-Tree Indexes
• PostgreSQL Index-Only Scans
• MySQL InnoDB Clustered and Secondary Indexes