\title{PostgreSQL B-Tree 索引原理与优化}
\author{叶家炜}
\date{Jul 08, 2026}
\maketitle
B-Tree 索引是 PostgreSQL 关系型数据库中最核心、最常用的索引实现，它承担着绝大部分 OLTP 查询的索引加速任务。理解其内部结构与行为模式，不仅有助于排查性能瓶颈，更能在索引设计阶段做出符合硬件特性的决策，从而带来可量化的响应时间缩短与吞吐量提升。本文面向已掌握基本 SQL 与索引概念的读者，沿着「原理—存储—构建—查询—维护—设计—案例」的路线，系统剖析 PostgreSQL B-Tree 的实现细节与优化实践。\par
\chapter{B-Tree 基础概念}
磁盘与内存的访问代价差异是理解索引设计的出发点。一次内存随机访问通常只需几十纳秒，而一次磁盘随机 I/O 则可能消耗毫秒级时间，二者相差四个数量级。因此，索引结构必须把「减少磁盘 I/O」作为首要目标。\par
多路平衡查找树（B-Tree）通过「有序性、平衡性、最小度」三项核心特性实现了这一目标：所有键在节点内有序排列，任意节点的子树高度差不超过 1，且每个非根节点至少包含 \texttt{order/2} 个键，保证树高在百万级记录时仍可控制在 3-4 层以内。PostgreSQL 实际采用的是 B+Tree 变体，其内部节点仅存放索引键与下行指针，叶子节点才携带完整的元组标识符（TID），这一设计使得范围扫描时可以沿着叶子层双向链表顺序读取，避免反复回溯到根节点，从而降低随机 I/O。\par
\chapter{PostgreSQL B-Tree 物理存储结构}
PostgreSQL 把数据文件划分为等大小的页面（Page），默认 8 KB，对应磁盘块。索引页面同样遵循这一布局，由页面头部（PageHeaderData）、元组指针数组（ItemId）和实际元组（Tuple）三部分组成。页面头部中的 \texttt{pd\_{}lower} 与 \texttt{pd\_{}upper} 分别指向空闲空间的起始与结束地址，\texttt{pd\_{}special} 用于存放 B-Tree 特有的元信息（如 \texttt{btpo\_{}next}、\texttt{btpo\_{}prev}），\texttt{pd\_{}flags} 则标记页面是否为右边界页或已删除。\par
在 B-Tree 内部，非叶子节点保存「高位键」（High Key）与「下行指针」（Down Link）。高位键表示子树中所有键的上界，下行指针指向下一层页面；叶子节点则不再存储高位键，而是通过 \texttt{btpo\_{}next} 与 \texttt{btpo\_{}prev} 形成双向链表，支持高效的范围扫描。变长键与 TOAST（The Oversized-Attribute Storage Technique）机制配合：当索引键长度超过页面剩余空间时，PostgreSQL 会把溢出部分存入 TOAST 表，并在原页面仅保留引用指针，确保页面分裂逻辑不受变长数据影响。\par
\chapter{索引构建流程}
初始空树仅有一个根页面，首次插入时直接写入该页面。当页面满时触发分裂：叶子分裂把原页面中 \texttt{order/2} 个键移至新页面，并把分裂键上移至父节点；非叶子分裂同样遵循「中位上移」原则，但需同时复制高位键以维护搜索语义。整个插入过程由 \texttt{\_{}bt\_{}doinsert} 函数驱动，它采用自顶向下的递归策略，先定位目标叶子，再在回溯时执行分裂。\par
并发控制通过「缓冲锁 + 锁耦合」实现：读取时持共享缓冲锁，写入时升级为排他锁；锁耦合保证在释放父节点锁之前已获得子节点锁，避免死锁。崩溃恢复依赖 WAL（Write-Ahead Logging）：每次页面分裂、键插入都记录 XLog，恢复时按 LSN（Log Sequence Number）顺序重放，保证索引物理一致性。\par
\chapter{查询执行中的 B-Tree 行为}
PostgreSQL 支持三种 Index Scan 形态：Index Only Scan 仅访问索引页面即可返回结果，Index Scan 需要回表获取可见元组，Bitmap Index Scan 则先把 TID 收集到内存位图，再按物理顺序回表。搜索路径从根节点开始，借助二分查找定位目标键，再沿下行指针递归直至叶子；叶子层链表支持顺序扫描，而 Bitmap Scan 更适合离散的随机访问，二者在代价模型中分别对应顺序 I/O 与随机 I/O 的权重系数。\par
MVCC 机制对索引的影响体现在「死元组」处理上。更新或删除操作仅在元组头部打上 xmax，旧版本仍留在索引中，导致索引膨胀。只有 VACUUM 回收这些死元组后，对应的索引项才可被重用或删除。\par
\chapter{索引维护与碎片}
VACUUM 过程调用 \texttt{btvacuumscan} 扫描索引，识别可删除的死元组并把页面标记为可再利用。\texttt{pgstattuple} 与 \texttt{pgstatindex} 视图分别提供页面级与索引级的统计信息：\texttt{pgstatindex} 返回 \texttt{leaf\_{}fragmentation}、\texttt{avg\_{}leaf\_{}density} 等指标，可量化索引膨胀程度。膨胀率计算公式为\par
[
\textbackslash{}text\{{}bloat\_{}ratio\}{} = 1 - \textbackslash{}frac\{{}\textbackslash{}text\{{}logical\_{}size\}{}\}{}\{{}\textbackslash{}text\{{}physical\_{}size\}{}\}{}
]\par
当该值超过 30\%{} 时，查询性能开始明显下降，需要考虑 REINDEX 或 pg\_{}repack。\par
\chapter{索引设计与优化策略}
选择索引列时应优先考虑区分度（Cardinality）与选择率（Selectivity），即列值分布越均匀、重复度越低，索引过滤效果越好。复合索引的列顺序需与查询谓词匹配：等值条件放前，范围条件放后，可最大化利用前缀匹配特性。覆盖索引（Covering Index）通过 INCLUDE 子句把查询所需列直接放入索引叶节点，避免回表，从而把 Index Only Scan 的比例从 40\%{} 提升至 85\%{} 以上。\par
部分索引（Partial Index）与表达式索引（Expression Index）适用于「 WHERE 条件固定」或「需对表达式建索引」的场景，可显著缩小索引体积。BRIN 索引适合时间序列等线性相关数据，其存储开销仅为 B-Tree 的 1/100，但仅在数据物理有序时有效；Hash 索引则仅支持等值查询且不支持 WAL，在 PostgreSQL 10 之后已较少使用。\par
索引大小与写入放大存在权衡：过多索引会增加 INSERT/UPDATE 的 WAL 量与页面分裂频率，因此需结合 \texttt{pg\_{}stat\_{}user\_{}indexes}.\texttt{idx\_{}scan} 与 \texttt{idx\_{}tup\_{}read} 指标，定期清理低效索引。\par
\chapter{典型场景案例与 Benchmark}
在 5000 万行时间戳表上，BRIN 索引大小仅 2.3 MB，而等价 B-Tree 索引达 1.1 GB；范围查询 \texttt{WHERE ts BETWEEN '2023-01-01' AND '2023-01-31'} 时，BRIN 的执行时间为 87 ms，B-Tree 为 42 ms，差距主要来自 BRIN 的顺序 I/O 特性。高并发写入测试显示，当 32 个客户端同时插入单调递增主键时，页面分裂导致的锁等待时间占比从 3\%{} 上升至 18\%{}，通过调大 \texttt{fillfactor} 至 70 可把分裂频率降低 40\%{}。\par
复合索引列顺序调换实验中，原索引 \texttt{(user\_{}id, created\_{}at)} 在 \texttt{WHERE user\_{}id = 100 AND created\_{}at > '2023-01-01'} 查询下 QPS 为 1200；调整为 \texttt{(created\_{}at, user\_{}id)} 后，相同查询 QPS 提升至 3600，主要因为前缀匹配能直接定位到范围起点。使用 \texttt{pg\_{}hint\_{}plan} 强制 \texttt{Index Only Scan} 后，执行计划中 \texttt{Heap Fetches} 从 1.2 M 降至 0，查询延迟从 3.8 ms 降至 1.1 ms。\par
监控脚本通过 \texttt{pg\_{}stat\_{}statements} 与 \texttt{pgstatindex} 联合查询，当 \texttt{bloat\_{}ratio > 0.3} 且 \texttt{last\_{}vacuum < now() - interval '7 days'} 时触发告警，并自动执行 \texttt{REINDEX CONCURRENTLY} 以避免锁表。\par
本文系统梳理了 PostgreSQL B-Tree 的存储布局、构建算法、查询路径、维护机制与设计策略，核心在于把磁盘 I/O 最小化与 MVCC 可见性相结合。进一步学习可阅读源码文件 \texttt{nbtree.c}、\texttt{nbtsearch.c} 与 \texttt{nbtinsert.c}，以及《Database System Concepts》与论文「The B-tree, LSM-Tree and Other Weird Trees」。在生产环境中，持续监控 \texttt{pg\_{}stat\_{}user\_{}indexes} 与定期执行 \texttt{REINDEX CONCURRENTLY} 是保持索引健康的关键。\par
