Radim Marek：B-tree 页——有序而稀疏
内容提要
本文讲解PostgreSQL B-tree索引的存储与膨胀机制。B-tree页与堆页同为8KB，但页内有序且同级页相互链接，每页含高键标记上界。VACUUM只删除死条目，不合并半空页、不截断文件，仅能删除完全空的页。顺序递增的键总落在最右叶，导致左侧空隙无法复用，索引持续膨胀；随机键则能填补空隙。回收空间需用REINDEX CONCURRENTLY或VACUUM FULL重建索引。
延伸解读
VACUUM 为何无法消除索引膨胀
VACUUM 对 B-tree 索引只做一件事：删除指向死元组的条目。它不会合并半空页，因为合并需要移动条目、重写父页下行链接并重新链接兄弟链，nbtree 并未实现这些操作。索引文件也从不截断，只有完全空的页才会被解除链接。因此，删除大量行后，索引页数不变，只是页内密度下降。
顺序键与随机键的膨胀差异
新键只能进入其排序范围所属的叶子页。顺序递增的键（如序列 ID 或时间戳）总落在最右叶，左侧页的空隙永远无法被填补，导致索引持续向右扩展。随机键（如 UUID 或邮箱）则可能落入任意页，空隙会随时间被重新填充。文章示例中，插入 4 万个高于现有最大值的新键后，索引从 276 页增至 385 页，而左侧半空页毫无帮助。
删除整段键范围后的页状态
删除一个连续的键范围并 VACUUM 后，中间页可能完全变空。VACUUM 会将这些空页从兄弟链和父页中解除链接，但页仍留在文件中，类型标记为 deleted，且暂不可复用。文章示例中，54 个空页在第一次 VACUUM 后仍不可复用，需再经过一个事务才被释放。这解释了为何删除后索引文件大小不变。
重建索引的代价与选择
回收空间需重建索引：REINDEX CONCURRENTLY 在线构建新索引后交换，不阻塞读写，但需要额外磁盘空间存放新索引和临时排序数据。普通 REINDEX 更快，但会取 ACCESS EXCLUSIVE 锁，阻塞相关查询和写入。VACUUM FULL 会同时重建堆和所有索引，在仅单个索引膨胀时通常不是合适工具。
Q&A
PostgreSQL 的 B-tree 索引页和堆页在结构上有什么主要区别？
B-tree 页与堆页一样使用 8KB 页面（24 字节头、行指针、元组从底部向上填充），但堆页是无序的行版本集合，而 B-tree 页内条目有序，并且同级页之间通过链接相互连接。每个 B-tree 页还有一个高键（high key）标记该页键值的上界。
VACUUM 能回收 B-tree 索引中的空间并解决索引膨胀吗？
不能。VACUUM 只删除指向死元组的索引条目，不会合并半空的页，也不会截断索引文件。它只能删除完全变空的页（将其标记为 deleted 并从兄弟链和父节点中移除），但页本身仍留在文件中，且要等没有扫描可能再访问它时才可重用。因此 VACUUM 无法消除索引膨胀。
为什么顺序递增的键（如自增 ID 或时间戳）会导致 B-tree 索引持续膨胀？
因为顺序递增的键总是落在最右侧的叶子页上，而其他叶子页即使因删除而变空，也无法接收这些新键。新键不断插入最右叶，导致其分裂，而左侧的空隙永远无法被复用，索引因此持续增长。随机分布的键则能填补各处空隙，膨胀较慢。
B-tree 索引中的高键（high key）是什么？它有什么作用？
高键是每个 B-tree 页（最右页除外）的第一个条目，它不指向堆中的行，而是标记该页键值的上界。高键是右侧相邻页第一个键的副本，用于界定页的键范围，并帮助构建上层节点（父节点通过高键确定每个叶子页的起始键）。
如何真正回收 B-tree 索引膨胀占用的空间？
需要重建索引。可以使用 REINDEX CONCURRENTLY（PostgreSQL 12+，在线重建，不阻塞读写，但需要额外磁盘空间存放新旧索引及排序临时空间），或者 VACUUM FULL（会重建表上的所有索引，但持有排他锁）。这些方法都是根据活条目写入新索引，而不是原地压缩旧索引。
删除大量行后执行 VACUUM，为什么索引大小没有变小？
因为 VACUUM 只从索引页中移除死条目，但保留页本身。即使页内大部分空间空闲，页也不会被合并或从文件中移除（除非页完全变空）。索引文件大小不变，只是页内平均密度下降。例如删除 80% 行后 VACUUM，索引仍为 276 页，但平均叶子密度从 89.78% 降至 18.15%。
