面试官：PostgreSQL 为什么不选择 B+ 树索引？
2026-06-22 17:56:33
PostgreSQL 选择改造后的 B- 树而非传统 B+ 树作为索引结构，主要基于以下设计考量：
一、索引结构的核心差异数据存储方式
B+ 树：非叶子节点仅存储键值和指针，数据全部保存在叶子节点（通过双向链表连接），范围查询效率高（时间复杂度为 O(logmN+K)）。
PostgreSQL 的 B- 树：所有节点（包括内部节点和叶子节点）均存储键值，但叶子节点仅保存指向数据行的 TID（页号+行指针），而非完整数据。这种设计使每个叶子节点能存储更多指针，在相同数据量下树高度更低，从而减少磁盘 I/O 次数。
B+ 树：数据集中在叶子节点，非叶子节点仅作索引
PostgreSQL 的 B- 树：叶子节点存储 TID，内部节点仅存储键值和指针
范围查询优化
传统 B- 树范围查询需中序遍历多个层级，效率较低。
PostgreSQL 的索引中，同一层的数据页通过双向链表连接，范围查询可直接遍历叶子节点链表，无需回溯上层节点，时间复杂度与 B+ 树一致（O(logmN+K)），但实际路径更短。
去重优化（Deduplication）
对重复键值（如状态标志字段）合并存储，仅保留一个键值和多个 TID 列表，节省存储空间并提高缓存命中率。
例如：100 条记录中 status='active'，传统 B+ 树需存储 100 个键值，而 PostgreSQL 仅存储 1 个键值 + 100 个 TID。
索引覆盖扫描（Index Only Scan）
叶子节点除键值和 TID 外，可存储查询所需的非索引列值（类似覆盖索引）。
若查询仅涉及索引列和包含列，可直接从索引获取结果，避免回表查询，显著提升性能。
反向键索引（Reverse Key Index）
对递增字段（如主键、时间戳）创建反向索引（如 CREATE INDEX idx ON table(id REVERSE)），将连续插入转换为随机分布，缓解写入热点问题。
适用于高并发插入场景，如日志系统或订单表。
PostgreSQL 的索引结构虽被称作 B- 树，但通过以下设计实现了 B+ 树的核心优势：
- 叶子节点有序链表：支持高效范围查询。
- 数据与索引分离：叶子节点仅存储 TID，减少节点大小，降低树高度。
- 功能扩展：通过去重、覆盖扫描等优化，超越了传统 B+ 树的性能边界。
PostgreSQL 未选择传统 B+ 树的原因在于：
- 工程优化需求：通过改造 B- 树（如 TID 存储、去重、覆盖扫描），在随机查询和范围查询间取得平衡。
- 堆表存储特性：PostgreSQL 采用堆表结构，数据物理地址无序，B- 树的 TID 指针设计更适配这种场景。
- 功能扩展性：反向键索引等特性需基于改造后的结构实现，传统 B+ 树难以直接支持。
因此，PostgreSQL 的索引本质是功能增强的 B- 树，而非简单的 B+ 树替代品。其设计更注重实际场景中的综合性能，而非理论上的索引类型分类。
热门标签
