PostgreSQL 存储引擎内幕（中）：索引扫描与 MVCC
这篇文章的价值：上一篇我们看到了 Heap Page 的内部布局和 Buffer Pool 如何管理页面缓存。但一个关键问题还没回答：当多个事务同时读写同一张表时，每个事务看到的数据是怎么决定的？这篇文章追踪两条路径——索引扫描如何从 B-Tree 叶节点跳到 Heap Page 取回数据，以及 MVCC 快照如何决定一行数据"对你可见还是不可见"。理解这些，你才能真正理解事务隔离级别不是一个抽象概念，而是一个具体的数据结构。
索引扫描：从 B-Tree 到 Heap
上一篇讲了顺序扫描——逐页遍历整个 Heap。索引扫描是另一条路径：先在索引中定位 TID，再用 TID 去 Heap 取数据。
索引也是表
在 PostgreSQL 中，索引和普通表一样是一个 Relation，有自己的文件、自己的 Page 结构。区别在于索引 Page 里存的不是用户数据，而是索引键 + TID的映射。
CREATE INDEX users_age_idx ON users(age);
索引扫描涉及两个 Relation：
indexRelation (users_age_idx) heapRelation (users)
┌─────────────────────────┐ ┌──────────────────────────┐
│ B-Tree Page │ │ Heap Page │
│ │ │ │
│ ┌───────────────────┐ │ │ ┌────────────────────┐ │
│ │ age=20 → TID(1,3) │ │ ┌────► │ ItemId[3] → Tuple │ │
│ │ age=25 → TID(5,1) │──┼─────┘ │ │ (id=42, name= │ │
│ │ age=25 → TID(8,7) │ │ │ │ 'Alice', age=25) │ │
│ │ age=30 → TID(2,5) │ │ │ └────────────────────┘ │
│ └───────────────────┘ │ │ │
└─────────────────────────┘ └──────────────────────────┘
IndexScanDesc 同时持有两个 Relation 的引用IndexScanDesc 是索引扫描的描述符，核心字段：
heapRelation：被索引的那张表indexRelation：索引本身xs_heaptid：当前找到的 TID，用于下一步回表
ExecIndexScan 的执行流程
ExecIndexScan
│
│ 有 Runtime Key？（如 WHERE id = $1）
│ 是 → 先计算参数值，再开始扫描
│
├── 有 ORDER BY？
│ 是 → IndexNextWithReorder（带排序的索引扫描）
│ 否 → IndexNext（普通索引扫描）
│
▼
IndexNext
│
▼
index_getnext_slot ─────────────────────────────────────┐
│ │
│ ┌─────────────────────────────────┐ │
│ │ 阶段 1: 从索引获取 TID │ │
│ │ │ │
│ │ amgettuple(scan, direction) │ │
│ │ → B-Tree: btgettuple() │ │
│ │ → Hash: hashgettuple() │ │
│ │ → GIN: gingettuple() │ │
│ │ → GiST: gistgettuple() │ │
│ │ │ │
│ │ 结果: scan->xs_heaptid = TID │ │
│ └─────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────┐ │
│ │ 阶段 2: 用 TID 回表取 Tuple │ │
│ │ │ │
│ │ index_fetch_heap() │ │
│ │ → table_index_fetch_tuple() │ │
│ │ → heapam_index_fetch_tuple() │ │
│ │ → heap_hot_search_buffer() │ ← HOT 链遍历 │
│ │ │ │
│ │ 包含 MVCC 可见性检查 │ │
│ └─────────────────────────────────┘ │
│ │
│ 如果 Tuple 不可见 → 回到阶段 1 取下一个 TID │
└────────────────────────────────────────────────────┘Runtime Key 是一个重要的概念：查询规划时无法确定的值。比如 WHERE id = $1 的参数、WHERE id = (SELECT max_id FROM others) 的子查询结果。这些值在 executor 启动时才计算，然后传给索引扫描。
B-Tree 内部：btgettuple
B-Tree 是 PostgreSQL 最常用的索引类型。btgettuple 的逻辑很直接：
- 首次调用：
_bt_first()在 B-Tree 中定位起始位置——从根节点向下遍历到叶节点，找到第一个满足扫描条件的索引条目 - 后续调用：
_bt_next()在叶节点链表上向前/向后移动，取下一个条目 - 找到位置后，
_bt_returnitem()从当前位置提取 TID：scan->xs_heaptid = currItem->heapTid
B-Tree 结构（简化）：
┌──────────────┐
│ Root Page │
│ [20] [50] │
└──┬──────┬────┘
│ │
┌──────▼──┐ ┌▼──────────┐
│ Internal │ │ Internal │
│ [10][20] │ │ [30][50] │
└──┬───┬──┘ └──┬────┬───┘
│ │ │ │
┌────▼┐ ┌▼────┐ ┌─▼──┐ ┌▼────┐
│Leaf │↔│Leaf │↔│Leaf│↔│Leaf │ ← 叶节点双向链表
│5,8 │ │12,18│ │25 │ │35,42│
│TIDs │ │TIDs │ │TIDs│ │TIDs │
└─────┘ └─────┘ └────┘ └─────┘
WHERE age = 25:
1. _bt_first: Root → Internal → 定位到第3个 Leaf
2. 在 Leaf 中找到 age=25 的条目，提取 TID
3. _bt_next: 继续在 Leaf 链表上扫描，直到 age ≠ 25回表：从 TID 到 Tuple
拿到 TID 后，index_fetch_heap 去 Heap 取数据。对于堆表，实际调用 heapam_index_fetch_tuple，核心是 heap_hot_search_buffer：
// 索引回表的完整路径（简化）
// 1. 索引给出 TID = (5, 1)
scan->xs_heaptid = {block: 5, offset: 1};
// 2. 读取 Heap Page 5 到 Buffer Pool
buffer = ReadBuffer(heapRelation, 5);
// 3. 在 Page 5 上搜索 HOT 链
heap_hot_search_buffer(
tid, // 起始 TID (5, 1)
relation, // users 表
buffer, // Page 5 的 buffer
snapshot, // 当前事务的快照 ← MVCC 在这里生效
&found
);
// 4. 沿 HOT 链遍历：
// ItemId[1] → Tuple A (t_ctid 指向 ItemId[2])
// ItemId[2] → Tuple B (t_ctid 指向 ItemId[3])
// ItemId[3] → Tuple C (t_ctid 指向自己 = 链尾)
//
// 对每个版本调用 HeapTupleSatisfiesVisibility(snapshot)
// 返回对当前快照可见的那个版本注意这里出现了 snapshot 参数——这就是 MVCC 的入口。索引本身不存储版本信息，所有版本判断都发生在回表之后。这意味着索引扫描可能从索引拿到一个 TID，回表后发现该行对当前事务不可见，然后继续取下一个 TID。
Lossy 索引与 Recheck
某些索引（如 GIN、GiST）是"有损"的——索引告诉你"这个 Tuple 可能匹配"，但不保证一定匹配。回表后需要用原始条件重新检查：
// IndexNext 中的 recheck 逻辑
while (index_getnext_slot(scandesc, direction, slot)) {
if (scandesc->xs_recheck) {
// 索引是 lossy 的，需要用原始条件重新验证
if (!ExecQualAndReset(node->indexqualorig, econtext))
continue; // 不匹配，跳过
}
return slot; // 匹配，返回
}MVCC：多版本并发控制
现在进入这篇文章的核心。MVCC 的目标是读不阻塞写，写不阻塞读。PG 通过让每行数据同时存在多个版本来实现这一点——每个事务看到的是某个时间点的"快照"。
事务 ID：逻辑时钟
PG 用事务 ID（TransactionId，简称 XID）作为"逻辑时钟"。每个写事务启动时分配一个单调递增的 XID。可见性判断的核心就是比较 XID：
| 行头字段 | 含义 | 可见性判断 |
|---|---|---|
t_xmin | 创建该版本的事务 | 如果 xmin 的事务已提交且在快照之前 → 该版本"出生了" |
t_xmax | 删除/更新该版本的事务 | 如果 xmax = 0 或 xmax 未提交 → 该版本"还活着" |
一个 Tuple 对你可见的条件：它已经出生（xmin 已提交）且还没死（xmax 无效或未提交）。
事务时间线：
XID: 100 101 102 103 104
│ │ │ │ │
│ INSERT │ │ UPDATE │ │
│ xmin=101 │ 新版本 │ │
│ │ │ xmin=103│ │
│ │ │ 旧版本 │ │
│ │ │ xmax=103│ │
事务 104 的快照拍摄于此 ─────────────────►│
对事务 104 来说：
旧版本：xmin=101(已提交✓) xmax=103(已提交✓) → 已死 → 不可见
新版本：xmin=103(已提交✓) xmax=0(还活着✓) → 可见 ✓SnapshotData：快照的数据结构
快照不是一个"时间点"，而是一个具体的数据结构：
typedef struct SnapshotData {
TransactionId xmin; // 所有 XID < xmin 的事务都已提交（确定可见）
TransactionId xmax; // 所有 XID >= xmax 的事务都未开始（确定不可见）
TransactionId *xip; // xmin 和 xmax 之间正在运行的事务列表
uint32 xcnt; // xip 数组的长度
} SnapshotData; 快照的三个区间：
XID: 95 96 97 98 99 100 101 102 103 104 105
────────────┬───────────────────────┬────────────
│ │
snapshot.xmin snapshot.xmax
◄── 确定可见 ──►│◄── 需要查 xip 数组 ──►│◄── 确定不可见 ──►
xip[] = {99, 101} ← 拍快照时仍在运行的事务
判断逻辑：
XID 96: < xmin → 已提交 → 可见 ✓
XID 99: 在 xip 中 → 仍在运行 → 不可见 ✗
XID 100: 不在 xip 中 → 已提交 → 可见 ✓
XID 101: 在 xip 中 → 仍在运行 → 不可见 ✗
XID 104: >= xmax → 未开始 → 不可见 ✗这个设计很精妙：xmin 和 xmax 快速排除大部分事务，只有落在中间区间的才需要查 xip 数组。
隔离级别：快照什么时候拍
事务隔离级别的本质区别不在于"看到什么"，而在于什么时候拍快照：
| 隔离级别 | 快照策略 | 效果 |
|---|---|---|
| Read Committed | 每条语句开始时拍新快照 | 同一事务内，两次 SELECT 可能看到不同数据 |
| Repeatable Read | 事务开始时拍一次快照，整个事务复用 | 同一事务内，多次 SELECT 看到一致的数据 |
| Serializable | 同 Repeatable Read + 额外的冲突检测 | 模拟串行执行，检测到冲突时回滚 |
-- Read Committed：每条语句一个新快照
BEGIN;
SELECT count(*) FROM users; -- 快照 S1 → 看到 100 行
-- 此时另一个事务插入 1 行并提交
SELECT count(*) FROM users; -- 快照 S2（新的！）→ 看到 101 行
COMMIT;
-- Repeatable Read：整个事务复用一个快照
BEGIN;
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM users; -- 快照 S1 → 看到 100 行
-- 此时另一个事务插入 1 行并提交
SELECT count(*) FROM users; -- 还是快照 S1 → 仍然看到 100 行
COMMIT;在代码层面，GetTransactionSnapshot() 负责这个决策：
- Read Committed：每次调用都创建新快照
- Repeatable Read / Serializable：首次调用创建快照并缓存，后续调用返回缓存的快照
什么时候需要快照
不是所有 SQL 都需要快照：
| 语句类型 | 需要快照？ | 原因 |
|---|---|---|
| SELECT / INSERT / UPDATE / DELETE | 是 | 需要访问表数据，必须判断可见性 |
| CREATE TABLE / DROP TABLE / ALTER | 否 | DDL 操作元数据，不涉及行级可见性 |
| EXPLAIN | 可能 | 如果是 EXPLAIN ANALYZE 需要实际执行，则需要 |
PG 通过 analyze_requires_snapshot 函数判断当前语句是否需要快照，避免为不需要的操作创建快照的开销。
可见性判断的完整规则
实际的可见性判断比"xmin 已提交且 xmax 无效"复杂得多。HeapTupleSatisfiesMVCC 需要处理这些情况：
| 场景 | xmin 状态 | xmax 状态 | 结果 |
|---|---|---|---|
| 刚插入，事务未提交 | 进行中 | — | 仅插入者自己可见 |
| 已插入并提交 | 已提交，在快照前 | 无效 (0) | 可见 |
| 已删除，删除事务未提交 | 已提交 | 进行中 | 可见（删除还没生效） |
| 已删除并提交 | 已提交 | 已提交，在快照前 | 不可见（已死） |
| 被更新，新版本存在 | 已提交 | 已提交 | 不可见（看新版本） |
| 插入事务已回滚 | 已回滚 | — | 不可见（从未存在） |
PG 还有一个优化：t_infomask 中的 hint bits。首次检查某行的 xmin/xmax 状态时需要查 CLOG（事务提交日志），确认后在 t_infomask 中设置"已提交"或"已回滚"标记，后续检查直接读标记，跳过 CLOG 查询。
EPQ：并发更新的冲突处理
当扫描发现一个 Tuple 正在被另一个事务修改时，会触发 EvalPlanQual（EPQ）机制：
- 正常扫描中发现目标 Tuple 被并发修改
- 等待修改事务完成（提交或回滚）
- 获取修改后的新版本 Tuple
- 用当前查询的 WHERE 条件重新评估新版本
- 如果新版本仍满足条件 → 返回新版本；否则跳过
这是 Read Committed 隔离级别下 UPDATE 和 DELETE 的必要机制——你不能跳过一个正在被修改的行，也不能基于旧版本做决策。
扫描方式全景
PG 提供多种扫描方式，每种都有不同的 accessMtd 函数指针：
| 扫描方式 | accessMtd | 原理 | 适用场景 |
|---|---|---|---|
| Sequential Scan | SeqNext | 逐页遍历整个 Heap | 全表扫描、无索引 |
| Index Scan | IndexNext | B-Tree 定位 → 回表取 Tuple | 高选择性查询 |
| Index Only Scan | IndexOnlyNext | 只读索引，不回表 | 查询列全在索引中 |
| Bitmap Heap Scan | BitmapHeapNext | 先收集所有 TID 排序，再批量回表 | 中等选择性，减少随机 I/O |
| TID Scan | TidNext | 直接按 TID 定位 | CURRENT OF 游标 |
所有扫描方式最终都通过 ExecScanExtended 统一调度：
// 统一扫描框架
ExecScanExtended(
ScanState *node,
ExecScanAccessMtd accessMtd, // SeqNext / IndexNext / BitmapHeapNext / ...
ExecScanRecheckMtd recheckMtd, // 对应的 recheck 函数
EPQState *epqstate, // 并发控制
ExprState *qual, // WHERE 条件
ProjectionInfo *projInfo // SELECT 投影
);这个设计让存储访问方法完全可插拔——heapam_methods 是默认的堆表实现，但 PG 的 Table Access Method API 允许你替换整个存储引擎：
// heapam_methods：堆表的函数表
static const TableAmRoutine heapam_methods = {
.scan_begin = heap_beginscan,
.scan_getnextslot = heap_getnextslot,
.index_fetch_tuple = heapam_index_fetch_tuple,
.tuple_insert = heapam_tuple_insert,
.tuple_delete = heapam_tuple_delete,
.tuple_update = heapam_tuple_update,
// ... 50+ 个函数指针
};这意味着理论上可以实现列式存储引擎、LSM-Tree 引擎等，插入 PG 的执行框架中。Heap 只是默认选择，不是唯一选择。
索引类型全景
PG 支持多种索引类型，每种都有自己的 IndexAmRoutine：
| 索引类型 | amgettuple | 数据结构 | 适用场景 |
|---|---|---|---|
| B-Tree | btgettuple | 平衡搜索树，叶节点链表 | 等值查询、范围查询、排序（最通用） |
| Hash | hashgettuple | 哈希桶 | 等值查询（比 B-Tree 快，但不支持范围） |
| GIN | gingettuple | 倒排索引 | 全文搜索、数组包含、JSONB |
| GiST | gistgettuple | 广义搜索树 | 几何数据、范围类型、全文搜索 |
| BRIN | — | 块范围索引 | 时序数据等物理有序的大表 |
它们共享同一个 index_getnext_slot 调用框架，通过 rd_indam->amgettuple 函数指针分派到具体实现。
把它们串起来：一次索引查询的完整路径
SELECT name FROM users WHERE age = 25;
┌──────────────────────────────────────────────────────────┐
│ Executor │
│ │
│ ExecIndexScan │
│ │ │
│ ▼ │
│ IndexNext │
│ │ │
│ ▼ │
│ index_getnext_slot │
│ │ │
│ ├─── btgettuple ──────────────────────────┐ │
│ │ B-Tree: Root → Internal → Leaf │ │
│ │ 找到 age=25, TID=(5,1) │ │
│ │ │ │
│ ├─── index_fetch_heap ◄───────────────────┘ │
│ │ 读取 Heap Page 5 到 Buffer Pool │
│ │ │
│ ├─── heap_hot_search_buffer │
│ │ │ │
│ │ │ ItemId[1] → Tuple v1 (xmin=90, xmax=95) │
│ │ │ HeapTupleSatisfiesMVCC(snapshot) → 不可见 │
│ │ │ │
│ │ │ 沿 t_ctid → ItemId[2] │
│ │ │ Tuple v2 (xmin=95, xmax=0) │
│ │ │ HeapTupleSatisfiesMVCC(snapshot) → 可见 ✓ │
│ │ │ │
│ │ └─► 返回 Tuple v2 │
│ │ │
│ ├─── ExecQual(WHERE age=25) → 通过 │
│ │ （B-Tree 是精确的，但 recheck 仍然存在） │
│ │ │
│ └─── ExecProject → 投影出 name 列 → 返回给客户端 │
│ │
└──────────────────────────────────────────────────────────┘总结
几个值得记住的关键直觉：
- 索引不存储版本信息：索引只存 key → TID 映射，所有 MVCC 判断都发生在回表之后。这意味着索引扫描可能取到一个 TID，回表发现不可见，再取下一个。Index Only Scan 是唯一的例外——它通过 Visibility Map 避免回表
- 快照是一个数据结构，不是一个时间点：
SnapshotData的 xmin/xmax 快速排除大部分事务，xip 数组精确判断中间区间。隔离级别的区别仅在于何时拍快照 - 可见性 = xmin 已提交 + xmax 无效：这是最核心的直觉。所有复杂情况（回滚、进行中、HOT 链）都是这个规则的变体
- hint bits 避免重复查 CLOG：首次可见性检查后在行头设置标记，后续检查直接读标记
- 存储引擎是可插拔的：
TableAmRoutine定义了 50+ 个函数指针，heapam 只是默认实现。IndexAmRoutine同理——B-Tree、Hash、GIN、GiST 共享同一个调用框架
下一篇，我们进入 WAL 和 Checkpoint 的世界：一次写入如何变成一条 WAL 记录、WAL Writer 如何将内存中的日志刷到磁盘、Checkpoint 如何创建一致性恢复点、以及这一切如何支撑复制和故障恢复。