4.1 B 树内幕：页面分裂与扫描路径
4.1 B 树内幕：页面分裂与扫描路径
本节摘要：默认索引 B 树是一套自平衡的有序页面树：叶层按键有序存"键值指向堆元组 ctid"的条目，上层页存分界键。一次等值查询的代价等于树高（通常三到四页）；范围查询在叶层横向走。插入时页满则分裂成两页并向父层递归，随机键插入的持续分裂是索引膨胀的来源。
从根到叶：一次查找走几步
CREATE TABLE orders (id bigint PRIMARY KEY, amount int); -- 主键即是一棵 B 树索引 SELECT * FROM orders WHERE id = 424242;
查找路径：根页（缓存常驻）→ 中间层页 → 叶页。每个节点页内用二分定位到下一跳。一亿行的表，树高通常不过四层——前三层几乎总在共享缓冲区里，真正的代价往往是叶页命中后的随机堆表取行。
叶页之间有横向指针，这是范围查询能"顺藤摸瓜"的原因：
-- 范围扫描：定位到起点后沿叶层向右走 SELECT * FROM orders WHERE id BETWEEN 100 AND 500;
图：B 树层次与两种扫描路径
页面分裂：树的成长阵痛
叶页写满后再插入，把该页对半分成两页、新分界键上传给父页；父页也满则继续分裂并再上传，极端时树长高一层。分裂本身不打断读写，但留下两个后果：
- 随机键插入的膨胀：UUID 主键让每个新键随机落点，页利用率约一分裂就停在一半，索引体积远大于自增键
- 写放大：一次插入可能引发多页修改，且全部要进 WAL（第 3 章）
-- 对比两类键的索引体积 CREATE TABLE t_uuid (id uuid PRIMARY KEY DEFAULT gen_random_uuid(), v int); CREATE TABLE t_bigint (id bigint PRIMARY KEY GENERATED ALWAYS AS IDENTITY, v int); -- 各插入千万行后： SELECT relname, pg_size_pretty(pg_relation_size(oid)) FROM pg_class WHERE relname IN ('t_uuid_pkey', 't_bigint_pkey');
同样的行数，UUID 版索引常常大出一半以上，且缓存命中率更低——因为叶层访问模式从"热点集中"变成"全域随机"。
fillfactor 的用法与堆表相反：索引预留空间不是为了 HOT 更新，而是为了让后续插入在同页内排序落位、减少分裂。默认 90，单调递增键可以调回 100。
⚠️ 常见坑：以为删除大量行后索引会自动变小。与堆表一样，索引页的空洞也只做内部复用，索引膨胀严重时同样需要 REINDEX 重建。
用 bt_page_items 看一次分裂
B 树的内部同样可以拆开看。bt_page_items 列出索引页内的键与下行指针：
CREATE EXTENSION IF NOT EXISTS btree_gist; -- 演示环境备好扩展 CREATE EXTENSION IF NOT EXISTS pageinspect; -- 叶层第 1 页的前几条：itemoffset 顺序即键序 SELECT itemoffset, data FROM bt_page_items('customer_pkey', 1) LIMIT 4;
itemoffset | data ------------+------------ 1 | 1 2 | 2 3 | 3 4 | 5
itemoffset 五不见了——第四条直接从 4 跳到 5 之类的情况是删除留下的空洞；而观察到某页的键范围与相邻页重叠收窄，则可能是分裂刚发生。更有说服力的实验是对比两棵树的空间利用率：
-- 看某索引叶页的"实住率"：live_items 与 max_avail SELECT live_items, dead_items, max_avail, btpo_flags FROM bt_page_stats('customer_pkey', 1);
随机键表反复插入后，多数叶页的填充率徘徊在六七成（一分裂各半），自增键表的叶页接近满页向左推进——这就是同规模下 UUID 索引大一截的微观解释。
膨胀度量与在线重建
索引膨胀不该靠感觉，pgstattuple 扩展给出直接数字：
CREATE EXTENSION IF NOT EXISTS pgstattuple; SELECT avg_leaf_density, leaf_fragmentation FROM pgstatindex('customer_pkey');
avg_leaf_density | leaf_fragmentation ------------------+-------------------- 67.2 | 12.4
avg_leaf_density 是叶页实际填充率（健康线 90 上下，低于 60 即明显膨胀），fragmentation 是逻辑相邻页物理不相邻的比例（影响范围扫描的预读效率）。两个数一起看，重建与否不再是玄学。
重建手段两代同堂。REINDEX CONCURRENTLY 是在线版：建影子索引、追平增量、原子切换，期间读写不阻断，代价是过程需要约两倍的临时空间与更长时间。停机窗口内的普通 REINDEX 更快更省。选择逻辑简单：有窗口用普通版，没有就用在线版，但要在低峰跑——在线重建依然要消耗大量 IO。
变式：单调递增键的"右缘生长"
自增与时间戳键的插入永远发生在 B 树最右侧叶页，这带来一个微妙现象：最右页持续写满、分裂、把上一半让出来，树像传送带一样向右生长。它的好处是页填充率高、缓存局部性极好；坏处是"最右热点页"成为唯一写入点，极高并发插入时所有会话争抢同一个页的锁——这是自增键在极端写入并发下反而出现等待的机制根源。经典解法是给键掺入少量分片位（比如按会话或机器取模的前缀），让写入分散到若干个"右缘"，代价是牺牲全局单调。绝大多数业务到不了需要分片的并发量，但知道这个边界在哪里，比撞上它再排查省一天时间。
本节要点回顾
- 树高即等值查询页数：上亿行不过三四层，且上层页常年缓存
- 叶层横向链：范围查询顺叶行走，代价正比于命中条数
- 分裂制造膨胀：随机键插入门 worse，自增或时序键最友好
- 索引不自动收缩：膨胀靠 REINDEX 或在线重建工具解决