本篇继续探讨索引相关的知识，上一篇用了大量篇幅和 sql 案例描述元组隐藏字段的变化，xmax、xmin、ctid，这些是 pg 的事务基础。很多场景都是在此基础上延伸出来的。本文计划分四部分进一步展开讲解索引底层的知识。

一、索引到底存了什么？

      对比 mysql，它的二级索引存储的是索引值和主键 ID。按 key-value 做类比，索引值是 key，主键 ID 是 value。pg 是堆表存储的，仍然用索引值走 key，而 value 是 TID，即 tuple ID。对比其他存储就类似行 id。

      TID 包含两部分：页面号和行偏移。页面号就是底层磁盘存储的 page，一个表有多个 page 组成，每个 page 默认 8KB，page 内存储了多个 tuple。以顺序扫描为例，一个表中的 page 是通过链表串联起来的，通过页面号可以快速定位到具体的 page，否则需要顺序扫描来遍历：

顺序扫描的工作方式┌──────┐   ┌──────┐   ┌──────┐    ┌──────┐   ┌──────┐│ 页面0 │ → │ 页面1 │ → │ 页面2 │ → │ 页面3 │ → │ 页面4 │ → ...│ 检查✗ │   │ 检查✗ │   │ 找到✓ │   │ 检查✗ │   │ 检查✗ │└──────┘   └──────┘    └──────┘   └──────┘   └──────┘                                                         ↓                                                    继续扫到最后一页                                                    （因为可能还有其他匹配）

索引的存储结构示意图：

索引条目的逻辑结构┌───────────────────────────────────┐│  索引键值        │  TID (页面,偏移)  │├───────────────────────────────────┤│  'abc@mail.com' │  (42, 3)        ││  'def@mail.com' │  (17, 8)        ││  'xyz@mail.com' │  (103, 1)       ││  ...            │  ...            │└───────────────────────────────────┘

偏移量作为 page 内部寻址用的，可以快速定位到具体的数据，计划后续在 page 存储结构中展开讨论。

二、B-Tree默认索引的结构

    在 pg 中按如下方式创建一个索引：

CREATE INDEX idx_users_email ON users(email);

如果不指定索引类型，pg 默认创建的就是 B-Tree（平衡树）索引。B-Tree 是数据库领域使用最广泛的索引结构——不仅 PostgreSQL，MySQL（InnoDB）、Oracle、SQL Server 的默认索引都是 B-Tree 的变体。其特点如下：

• 磁盘读写以"页面"为单位：

•       一次读 8KB 比读 1 个字节并不会慢多少。B-Tree 的节点大小正好对齐页面大小，一次 I/O 读一整个节点。

• B-Tree 是"矮胖"的：

        不像二叉树那样又高又瘦，B-Tree 每个节点可以有几百个子节点，树的高度极低（通常 3~4 层就能索引上亿行数据）。树高就是查找一次需要读磁盘的次数。

下面用一个简化的例子，展示 B-Tree 索引的三层结构。假设我们对 users 表的 id 列建了 B-Tree 索引，表中有 1~24 这些 ID 值：

B-Tree 索引结构可视化                    （简化示意，实际节点容纳更多键值）
层级 0 ── 根节点（Root）                    ┌──────────────────┐                    │  [8]    [16]     │                    └───┬──────┬───────┘                        │      │              ┌─────────┘      └──────────┐              ▼                           ▼
层级 1 ── 内部节点（Internal）   ┌──────────────┐              ┌──────────────┐   │  [4]    [8]  │              │ [12]   [16]  │   └──┬──────┬────┘              └──┬──────┬────┘      │      │                      │      │   ┌──┘   ┌──┘                   ┌──┘   ┌──┘   ▼      ▼                      ▼      ▼
层级 2 ── 叶子节点（Leaf）── 存储实际的索引条目
┌─────────────┐  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐│ 1→(0,1)     │→ │ 5→(1,2)     │→ │ 9→(2,3)     │→ │13→(3,1)     ││ 2→(0,2)     │  │ 6→(1,3)     │  │10→(2,4)     │  │14→(3,2)     ││ 3→(0,3)     │  │ 7→(2,1)     │  │11→(3,0)     │  │15→(3,3)     ││ 4→(1,1)     │  │ 8→(2,2)     │  │12→(3,0)     │  │16→(4,1)     │└──────┬──────┘  └──────┬──────┘  └──────┬──────┘  └──────┬──────┘       └────→───────────┘→───────────────┘→───────────────┘              叶子节点之间用"双向链表"串联

三层节点各自的职责：

层级	名称	职责	存储内容
0	根节点（Root）	查找的起点	分界键 + 子节点指针
1	内部节点（Internal）	引导查找方向	分界键 + 子节点指针
2	叶子节点（Leaf）	存储实际索引数据	索引键值 + TID（行指针）

三、查找过程

      我们以查 id = 11 的数据为例，先读取根节点，按照“从左到右，从小到大”的规则，读取相应的 id 范围。

查找 id = 11 的过程
步骤 1：读取根节点┌──────────────────┐│  [8]    [16]     │    11 ≥ 8 且 11 < 16 → 走中间指针└───────┬──────────┘        ▼
步骤 2：读取内部节点┌──────────────┐│ [12]   [16]  │    11 < 12 → 走最左指针└──┬───────────┘   ▼
步骤 3：读取叶子节点┌─────────────┐│ 9→(2,3)     ││10→(2,4)     ││11→(3,0)  ←── 找到了！TID = (3,0)│12→(3,0)     │└─────────────┘
步骤 4：用 TID (3,0) 去堆表取完整行数据（回表）
总共读取：3 个索引页面 + 1 个堆表页面 = 4 次 I/O

四、索引与表数据的关系

      当 pg通过索引找到了目标行的 TID 后，还需要一步额外操作——拿着这个 TID 去堆表中读取完整的行数据。这个过程叫做回表（Heap Fetch），在执行计划中体现为 Index Scan。

索引扫描（Index Scan）的完整过程
┌─────────────────────────────────────────────┐│                B-Tree 索引                   ││                                             ││  找到 email='zhang@example.com' → TID(42,3)  │└──────────────────────┬──────────────────────┘                       │                       │  "回表"：拿 TID 去堆表取数据                       ▼┌─────────────────────────────────────────────┐│                堆表（Heap）                  ││                                             ││  读取页面 42，取出第 3 条记录                   ││  → { id: 100, email: 'zhang@example.com',   ││      name: '张三', created_at: '2024-01-15'} │└─────────────────────────────────────────────┘

      回表的代价是随机 I/O，索引中相邻的键值，在堆表中可能分散在完全不同的页面上。比如 email 按字母排序的索引中，'aaa@mail.com' 在堆表的第 500 页，'aab@mail.com' 在第 3 页，'aac@mail.com' 在第 12000 页……每次回表都是一次随机跳转。这就是为什么当索引扫描返回大量行时，优化器可能反而选择顺序扫描——大量随机 I/O 不如一次顺序 I/O。

随机 I/O vs 顺序 I/O 的直觉
顺序 I/O（Seq Scan）          随机 I/O（Index Scan 的回表）📖 从头到尾翻一本书            📖 翻到第3页 → 第500页 → 第12000页 → 第7页→ 预读友好，磁盘吞吐量高        → 每次都要重新定位，延迟高→ SSD 上 ~500 MB/s              → SSD 上 ~50-200 MB/s（随机 IOPS 有限）→ HDD 上 ~100 MB/s              → HDD 上 ~1-5 MB/s（磁头寻道是瓶颈）

原文链接：https://mp.weixin.qq.com/s/HmDmZdIk2uBQJjLYuuewBw