PostgreSQL的B-Tree索引基于改进的B+树结构，支持等值、范围查询和排序；其多路平衡树结构确保3~4层可支撑亿级数据，所有数据存于叶子节点且通过双向链表连接，提升范围扫描效率；索引页面分根、内部和叶子三种类型，大小默认8KB，插入时通过页分裂维持平衡，并借助WAL保障一致性；在MVCC机制下，索引条目不存事务信息，查询需结合堆表元组头判断可见性，利用visibility map和hint bits优化检查开销；删除数据后空间不自动回收，需手动REINDEX或VACUUM FULL；查询时从根节点逐层定位至叶子页，使用二分查找匹配键值并获取TID，再回表读取可见行。
PostgreSQL 的 B-Tree 索引是其最常用、最核心的索引类型，主要用于支持等值查询、范围查询和排序操作。它的底层实现基于经典的 B+ 树结构，并针对数据库系统的特性做了大量优化。
基本结构：B+ 树变种
PostgreSQL 的 B-Tree 实际上是一种 B+ 树的改进版本，具有以下特征：
- 多路平衡搜索树：每个节点可以有多个子节点（通常为数百个），树的高度较低，一般 3~4 层即可支持亿级数据。
- 所有数据存储在叶子节点：内部节点仅用于导航，只保存键值和指向子节点的指针，不存实际行数据。
- 叶子节点双向链表连接：便于高效地进行范围扫描（如 WHERE age BETWEEN 20 AND 30）。
这种设计使得查找、插入、删除的时间复杂度都保持在 O(log n)，同时支持高效的顺序访问与随机访问。
页面结构与存储机制
PostgreSQL 将 B-Tree 索引划分为固定大小的“页面”（默认 8KB），每个页面对应一个磁盘块。主要类型的页面包括：
- 根节点（Root）：树的入口，可能位于任意层级。
- 内部节点（Internal Page）：包含索引键和指向子页的 TID（块号 + 项编号）。
- 叶子节点（Leaf Page）：存储完整的键值对以及指向表中行的 TID（即 heap tuple 的位置）。
每个索引条目由键值和一个指向目标行或子页的指针组成。对于复合索引，键值由多个字段拼接而成。
页面之间通过左右兄弟指针相连，形成双向链表，这极大提升了范围查询的效率——无需反复回溯父节点。
插入与分裂机制
当向索引插入新键时，系统从根开始逐层定位到合适的叶子页。如果目标页已满，则触发页分裂：
- 原页被分成两个逻辑上相邻的新页。
- 部分条目迁移至新页，保持键有序。
- 父节点更新以反映新的分支结构；若父节点也满，则递归向上分裂，必要时创建新的根节点。
PostgreSQL 使用“快速路径插入”优化热点页的写入性能，并采用 WAL（Write-Ahead Logging）保证崩溃恢复时索引一致性。
高并发控制与可见性判断
作为 MVCC（多版本并发控制）系统的一部分，PostgreSQL 的 B-Tree 索引必须处理事务可见性问题：
- 索引条目本身不存储事务信息，但查询时会结合堆表中的元组头信息判断某行是否对该事务可见。
- 使用“Hot Standby Index Scans”技术，在只读事务中跳过不可见项。
- 通过visibility map 和hint bits 减少不必要的可见性检查开销。
这也导致一个问题：即使删除了大量数据，索引体积不会立即缩小，需要手动执行 REINDEX 或 VACUUM FULL 来回收空间。
查询执行过程示例
假设执行 SQL：
SELECT * FROM users WHERE age = 25;
流程如下：
- 从根页开始，根据比较结果逐层下探到对应的叶子页。
- 在叶子页中使用二分查找定位第一个 age=25 的键。
- 遍历后续连续匹配项（利用有序性）。
- 取出每项对应的 TID，去堆表中获取实际数据行并验证可见性。
如果是范围查询，比如 age > 20 AND age
基本上就这些。PostgreSQL 的 B-Tree 不仅实现了标准的高效检索能力，还深度集成于其 MVCC、WAL 和并发控制体系之中，是高性能查询的基础支撑。理解其原理有助于合理设计索引、优化查询性能。不复杂但容易忽略细节。
