PostgreSQL默认使用B-tree索引，基于8KB页组织，采用多层树结构，包含根、内部和叶节点，叶子节点同层且双向链接。页由页头、元组数组、空闲空间和特殊区域组成，页头含LSN、校验和等信息，元组存储键值与TID，支持压缩。插入删除触发分裂或清理，WAL保障一致性，结构统一支持多种索引类型。
PostgreSQL 使用 B-tree 作为默认索引类型，其索引文件结构基于磁盘页（Page）组织，每个页大小通常为 8KB。整个索引结构以多层级的树形方式存储，支持高效查找、插入和删除操作。
B-tree 索引整体结构
PostgreSQL 的 B-tree 索引由多个逻辑层级组成：根节点（Root）、中间节点（Internal Nodes）和叶节点（Leaf Nodes）。数据按键值有序排列，所有叶子节点位于同一层，并通过双向链表连接，便于范围扫描。
- 根节点是查询入口，可能直接是叶子节点（当表很小）
- 内部节点只存键值和子页指针，用于导航
- 叶子节点包含实际的索引项：键值 + TID（指向表中行的物理位置）
索引页（Index Page）格式
每个索引页遵循统一的底层结构，由页头、元数据、元组数组和空闲空间组成。
- pd_lsn：记录最后一次修改该页的日志序列号（LSN）
- pd_checksum：可选校验和，用于检测页损坏
- pd_flags：标记页属性，如是否为叶子节点、根节点、删除状态等
- pd_lower：指向页内数据起始位置（从下往上增长）
- pd_upper：指向空闲空间起始位置
- pd_special：指向特殊区域起始位置（B-tree 中为 IndexTupleData 结构数组）
- pd_pagesize_version：页大小与版本号
- pd_prune_xid：用于清理过期事务信息的最老 XID
- 从页底部向上存放 IndexTuple 结构
- 每个 IndexTuple 包含：
- 索引键值（Key Attributes）
- TID（Table Page ID + Offset），指向堆表中的具体行
- 额外标志位（如是否 NULL、是否压缩等）
- t_info 字段记录长度和属性标志
- 位于页中部，由 pd_lower 和 pd_upper 界定
- 新插入的索引项在此分配空间
- 使用“反向填充”策略，提高空间利用率
- B-tree 特有，位于页顶部，包含 BTreePageOpaqueData
- 存储：
- 左兄弟/右兄弟指针（用于叶子层遍历）
- 父节点指针（非必须）
- 层级编号（level，根为0，逐层递增）
- 标志位（LEAF、ROOT、HALF_DEAD 等）
索引项（IndexTuple）结构细节
在 B-tree 中，IndexTuple 是基本存储单元，定义在 itup.h 中。
- t_tid：指向表中行的 TID（BlockNumber + OffsetNumber）
- t_info：包含长度、是否有NULL、是否有前缀压缩等标志
- 键值部分：按索引定义顺序排列的 Datum 值，可能经过对齐或压缩
- 支持前缀压缩（仅存与前一项不同的部分）和尾部压缩（去除重复后缀）
构建与维护机制
索引不是实时完全平衡的，而是通过写时复制（Copy-on-Write）和 WAL 日志保证一致性。
- 插入时若页满，则触发分裂（Split）：创建新页，重分布键值，更新父节点
- 删除后标记为 DEAD，后续由 VACUUM 或 B-tree 内部清理机制回收空间
- WAL 记录所有页变更，确保崩溃恢复后索引一致
- 支持高级特性如部分索引、表达式索引、多列索引，其结构统一适配于上述框架
