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

查询量增长后，逐页扫描会让读放大和延迟一起上升。数据库需要一种既适合存储页、又能在持续更新中保持有序的索引。

B+ 树用较高扇出降低树高，在叶子页按键序保存记录，并通过分裂维持平衡。本课把点查、范围扫描和更新放进页模型，检查索引省去了哪些读取、又增加了哪些写入。

逻辑结构

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_tasks_customer
ON tasks (customer_id);

SELECT task_id, status, reward_cents
FROM tasks
WHERE customer_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 catalog_items (item_type_id, value_cents DESC, item_id DESC);

SELECT item_id, name, value_cents
FROM catalog_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 map：对应 heap page 的 all-visible 位未设置时，仍需访问 heap 验证行可见性。因此即便索引包含全部查询列，也要在计划中检查 Heap Fetches。PostgreSQL index-only scan 文档 解释了这一条件。

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_tasks_cover
ON tasks (customer_id, status)
INCLUDE (task_id, reward_cents);

这段是 PostgreSQL 11+ 的部分示例，需先在 PostgreSQL 中创建包含这些列的 tasks 表；不能直接粘贴到前面的 SQLite CLI。task_id 也要显式放进 INCLUDE，才能覆盖下方查询的所有输出列；PostgreSQL 不会自动把主键附在每个二级索引中。INCLUDE 是 PostgreSQL 等产品的 feature，MySQL index syntax/leaf payload 不同。included columns 增大 index 并增加 write cost；必须用真实 plan 验证收益。

看计划，不猜计划

PostgreSQL：

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT task_id, status, reward_cents
FROM tasks
WHERE customer_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 catalog_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