GIN 索引：倒排索引的内部机制与 Fast Update

PG 有四种内置索引类型：B-Tree 是主键和等值查询的默认选择，GiST 为几何和全文搜索提供平衡树的抽象框架，BRIN 为超大表提供极简的范围摘要。而 GIN（Generalized Inverted Index）处理的是这三种都不擅长的问题：一个数据行包含多个索引键。

典型场景随处可见。一个 tsvector 字段从文档中提取出几十个词，每个词都是搜索入口；一个 integer[] 字段包含几十个元素，每个元素都可能出现在 @> 查询中；一个 JSONB 字段的顶层键和值都需要索引。

如果你用 B-Tree 索引数组字段，ANY 查询会把每个元素当成独立的索引查找，效率随元素数量线性退化。GiST 可以做，但 GIN 在”键多而行少”的场景下结构化优势更明显——它的倒排结构把”键到行”的映射直接写死在索引里，搜索时不需要遍历数据行。

本文将逐层拆解 GIN 的内部结构、Fast Update 机制、搜索流程，以及 GIN 和 GiST 的选择权衡。

一、倒排结构：Entry Tree 与 Posting List / Posting Tree

1.1 为什么是倒排

B-Tree 索引的数据模型是”一行 → 一个键”：一行表数据最多对应一个索引条目。GIN 的数据模型是”一个键 → 多行”：一个键值（如一个词、一个数组元素）可能出现在大量行的索引字段中。这是倒排索引（inverted index）的基础模型——不是从行找键，而是从键找行。

GIN 把这种映射拆成两层结构：Entry Tree 负责”键值到键条目”的查找，Posting List / Posting Tree 负责”键条目到行 ID”的映射。

1.2 Entry Tree：B-Tree over Keys

Entry Tree 是 GIN 的顶层结构：一个标准 B-Tree，其键是被索引复合值中提取出的每一个原子元素。对于 tsvector 索引，键是每一个词位（lexeme）；对于 intarray 索引，键是数组中的每个整数。

Entry Tree 的叶子节点存放的不是数据行的指针，而是指向 Posting List 或 Posting Tree 的引用。关键特性：每个键值在 Entry Tree 中只存储一次。如果一个词 “database” 出现在 10000 行中，Entry Tree 中只有一条记录指向包含 10000 个行 ID 的 Posting 结构。这使得 GIN 在键值重复度高的场景（全文搜索是典型）下非常紧凑。

多列 GIN 索引将多列合并到一个 Entry Tree 中，键值被组织为 (column_number, key_value) 复合值，通过列编号区分不同列的同名键。

1.3 Posting List 与 Posting Tree：大小的分界线

GIN 用两种不同的结构存储键对应的行 ID 列表，选择取决于列表的大小：

Posting List：当某个键出现的行数较少，所有行 ID 能放进一个索引页面时，GIN 将它们直接内联存储在 Entry Tree 的叶子元组中。这是一个紧凑的、平铺的 TID 列表。优点是只需要一次 Entry Tree 叶子页的 I/O 就能拿到全部匹配行的位置；缺点是对于高频键，列表可能变得非常大。

Posting Tree：当 Posting List 增长到无法放入单个页面时，GIN 将它扩展为一棵独立的 B-Tree，以行 ID（TID）为键。Posting Tree 也是一个标准 B-Tree，但与 Entry Tree 不同的是，它的节点只存 TID，不存键值。Entry Tree 叶子元组此时存储的是一个指向 Posting Tree 根页的指针。

一条简单的判断规则：建索引时一个键对应的行数决定初始用 Posting List 还是 Posting Tree；后续插入可能将 Posting List 升级为 Posting Tree。

Entry Tree (B-tree over keys)
  |
  ├── key: "database"  ──→  Posting List: [TID1, TID3, TID7]    ← 出现 3 次，内联存储
  ├── key: "postgres"  ──→  Posting Tree (B-tree of TIDs)        ← 出现 10000 次，独立 B-Tree
  │                              ├── 页 1: TID1...TID500
  │                              ├── 页 2: TID501...TID1000
  │                              └── ...
  └── key: "index"     ──→  Posting List: [TID2, TID5, TID9]
```bash

### 1.4 NULL 和空值的处理

GIN 对"索引字段为 NULL 或空数组/空文档"的行会插入一个占位符键。这保证了对于 `NOT EXISTS` 或否定查询（如"所有不包含某关键词的行"），GIN 也能通过这个占位符找到候选行。对于包含 NULL 元素的非空复合值（如一个部分为 NULL 的 JSONB），GIN 将 NULL 键插入 Entry Tree，而 `extractValue` 通过 `nullFlags` 数组标记哪些键值为 NULL。

---

## 二、Fast Update：Pending List 的设计与后台合并

### 2.1 问题：逐键插入的代价

GIN 索引的插入有一个先天劣势：向表中插入一行数据时，如果该行的索引字段提取出 $n$ 个键，GIN 就需要向索引中插入 $n$ 次——Entry Tree 要查找或分裂 $n$ 次，Posting List / Posting Tree 也要各更新 $n$ 次。对于 `tsvector` 索引，一个中等长度的文档可能提取 30-80 个词，每次插入就是 30-80 次 B-Tree 操作。

直接逐键插入的代价太高。GIN 的解决方案是 Fast Update。

### 2.2 Pending List：延迟合并

Fast Update 的核心思路简单：新插入的条目不立即合并到主索引结构（Entry Tree + Posting List/Tree），而是追加到一个临时的、未排序的 pending list 中。这个 pending list 是一个简单的线性页面链表，新条目写入时只需要向链尾追加，不需要查找、不需要分裂、不需要更新 Posting 结构。

插入流程变为：

```text
INSERT 一行 → extractValue() 提取出 n 个键
  → 对每个键, 追加(key, TID)到 pending list 尾部（仅追加，不查找不排序）
  → 完成

O(\(n\)) 次 B-Tree 操作变成了 O(\(n\)) 次线性追加。对大量小插入的场景，这是数量级的提升。

2.3 合并时机

Pending list 不会无限增长。在以下时机，pending list 中的条目被批量合并到主索引结构：

1. VACUUM（手动或 autovacuum）：VACUUM 任务在清理完 dead tuple 后，会自动调用 GIN 的 pending list 清理逻辑。
2. autoanalyze：自动统计信息收集也会触发合并。
3. 显式调用 gin_clean_pending_list() 函数：SELECT gin_clean_pending_list('index_name'::regclass) 强制立即合并。
4. Pending list 超过 gin_pending_list_limit：如果下次插入会让 pending list 超过此阈值，当前插入会在前台触发一次完整的合并清理。

关键洞见在第 4 条：如果日常插入量小于 gin_pending_list_limit，合并工作总是由 VACUUM 在后台完成，用户的 INSERT 永远不会被合并操作阻塞。但一旦某次插入踩线触发了阈值，这次插入就会承担全部合并工作的代价——延迟显著增加。这是 Fast Update 最核心的 trade-off。

合并操作本身使用与建索引相同的批量插入算法（bulk insert），利用 maintenance_work_mem 作为排序缓冲区：先读出 pending list 的所有条目，按键排序后批量写入 Entry Tree 和 Posting 结构。maintenance_work_mem 越大，排序趟数越少，合并越快。

2.4 搜索的代价

Pending list 带来的代价是搜索时必须扫描两块数据：主索引结构 + pending list。Pending list 是线性的、未排序的，扫描它的代价与列表大小成正比。

这个代价可以用 gin_pending_list_limit 来控制： - 调大：合并频率降低，但搜索时 pending list 更大，查询更慢。 - 调小：搜索更快，但合并更频繁，极端情况下可能频繁在前台触发清理。

对于以查询为主的只读/少写表，最佳实践是在批量导入数据后立即调用 gin_clean_pending_list()，清空 pending list，确保后续查询只扫描主索引结构。

2.5 关闭 Fast Update

当插入性能不是瓶颈，更关心查询延迟的可预测性时，可以通过存储参数关闭 Fast Update：

CREATE INDEX idx_name ON table_name USING gin (column)
    WITH (fastupdate = off);
```text

关闭后每次插入直接写主索引结构，没有任何延迟的 pending list 扫描。适用于插入频率低、查询延迟要求严格的场景。

---

## 三、搜索流程：gingetbitmap() 的 Bitmap AND/OR

### 3.1 整体架构

GIN 的搜索入口是 `gingetbitmap()`（`src/backend/access/gin/ginget.c`）。GIN 没有 `gettuple` 方法——它只支持 bitmap index scan，不支持传统的逐行 index scan。这是因为 GIN 的倒排结构天然适合"给定 N 个键，找出所有包含它们的行并集/交集"，而不是"给定一个起点，遍历所有索引行"。

搜索分四个阶段：

```mermaid
flowchart TD
  Q["查询条件<br/>(如 to_tsquery('a & b'))"] --> EX["extractQuery()<br/>提取查询键"]
  EX --> K1["key[0]='a'<br/>key[1]='b'"]
  K1 --> SCAN["启动扫描<br/>对每个 key"]
  SCAN --> MAIN["扫描 Entry Tree<br/>+ Posting List/Tree"]
  SCAN --> PENDING["扫描 Pending List"]
  MAIN --> BM["构建 TID Bitmap<br/>per-key"]
  PENDING --> BM
  BM --> MERGE["Bitmap AND/OR<br/>按查询语义合并"]
  MERGE --> CON{"consistent(check[])"}
  CON -- "true" --> RESULT["Bitmap Heap Scan<br/>返回匹配行"]
  CON -- "recheck=true" --> RECHECK["对 heap tuple<br/>重检查原始值"]
  CON -- "false" --> DROP["丢弃"]
  RECHECK --> RESULT

3.2 阶段一：提取查询键

extractQuery() 是 GIN 操作符类提供的回调函数。它接收查询条件（如 to_tsquery('database & postgres')），返回一组查询键（"database"、"postgres"）和键之间的逻辑关系（AND）。对于 @@ 全文搜索，extractQuery 将 tsquery 的解析树展平为键列表；对于 @> 数组包含查询，将数组元素展平为键列表。

如果查询支持部分匹配（prefix search，如 'data:*'），extractQuery 只返回一个下界键并设置 pmatch 标志，后续扫描由 comparePartial 函数控制范围。

3.3 阶段二：扫描主索引和 Pending List

对每个查询键，GIN 同时扫描两个来源：

主索引扫描：在 Entry Tree 中查找该键，找到后读取其 Posting List 或遍历其 Posting Tree，将找到的所有 TID 收集到一个 per-key 的 bitmap 中。

Pending List 扫描：线性遍历整个 pending list 的页面链表，把其中匹配该键的所有 TID 也加入同一个 per-key bitmap。

每个查询键得到一个 bitmap。如果有 3 个查询键，就得到 3 个 bitmap。

3.4 阶段三：Bitmap 合并

根据查询的语义（AND/OR），将这组 per-key bitmap 合并：

• AND（如 'a & b'）：对两个 bitmap 做交集，只保留在两个 bitmap 中都出现的 TID。
• OR（如 'a | b'）：对两个 bitmap 做并集，保留出现在任意一个 bitmap 中的 TID。
• NOT（如 '!a'）：需要知道”不包含键 a 的所有行”，这需要全表扫描——这也是为什么 PG 的全文搜索不原生支持纯否定查询的高效索引扫描。

合并后的 bitmap 是候选行 TID 的集合。此时还没有读取任何 heap tuple。

3.5 阶段四：consistent 过滤

Candidate bitmap 中的 TID 只是”所有查询键在其中出现的行”的集合。但在 AND 查询中，GIN 可能还需要确认这些键是否出现在同一行中（而不是同一行的不同索引字段），或者需要确认更多细节（如匹配的位置信息）。

consistent(check[], query, ...) 是 GIN 操作符类提供的回调。它接收一个布尔数组 check[]，第 i 个元素表示第 i 个查询键是否出现在当前候选行中。consistent 返回三种可能的结果：

recheck = true 的场景：GIN 索引不存储原始的索引值，consistent 只能根据键的存在/缺失做判断。当判断需要更多的上下文（如词典中词的位置关系）时，GIN 无法仅从索引做出确定性判断，必须标记 recheck = true，由执行器在读取 heap tuple 后用原始数据重新计算。

PG 9.4 引入的 triConsistent 回调进一步优化了这个流程：triConsistent 可以让 GIN 在还没读完某个键的全部 TID 时就能提前判断某些候选行是否可能匹配。如果 triConsistent 返回 GIN_FALSE，GIN 可以跳过对该行剩余键的扫描。

四、全文搜索 tsvector 与数组 _int4 的实现

4.1 tsvector 的 GIN 操作符类

全文搜索是 GIN 最典型的应用场景。PG 内置的 tsvector_ops 操作符类支持 @@（匹配）、@@@（短语匹配）等操作符。

extractValue 从 tsvector 中提取所有词位（lexeme），并附带每个词位的位置信息（position）。位置信息存储在 Posting List/Tree 的 TID 条目中，用于短语搜索（“A 紧邻 B”）的 recheck 阶段。具体来说，Posting Tree 中每个 TID 条目除了存储 heap 行指针外，还存储该键在该行中出现的位置列表（positions）。

extractQuery 从 tsquery（如 to_tsquery('database & postgres')）中提取查询键及其逻辑关系。两个词的 AND 产生 2 个键，查询逻辑为 nkeys == 2 且 consistent 要求 check[0] && check[1]。

consistent 对基本关键词匹配做简单的键存在性判断（AND = 所有键都存在），对短语搜索（'<->' 操作符）则需要检查位置信息，这个检查发生在 recheck = true 路径上——heap tuple 被读回后，用 tsvector 中存储的完整位置列表验证邻接关系。

4.2 intarray 的 GIN 操作符类

intarray 扩展提供 gin__int_ops 操作符类，支持数组比较操作符：

• @>（包含）：左边的数组是否包含右边的所有元素。extractQuery 将右边数组的元素展平为查询键，consistent 要求 check[i] 全为 true（AND 语义）。
• &&（重叠）：两边是否有交集。extractQuery 将右边数组元素展平，consistent 要求至少一个 check[i] 为 true（OR 语义）。
• =（相等）：两边是否完全相同。使用 AND 语义 + 需要计数验证（recheck = true），因为索引只记录”该键在行中是否存在”，而不是”该键在行中出现几次”。

对于 _int4 这样元素类型固定的数组，GIN 索引的 extractValue 很简单：遍历数组的每个元素，将其作为一个独立的键插入索引。

4.3 JSONB 的 GIN 索引

JSONB 的 GIN 支持通过不同的操作符类实现：

• jsonb_ops（默认）：将每个 JSON 键和值的组合提取为索引键（如 {"a": 1} 提取键 "a" 和 "1" 作为两个独立条目）。支持 @>、?、?|、?& 操作符。
• jsonb_path_ops：只索引 JSON 路径（键的序列），不索引值。更紧凑，只支持 @> 操作符，但不支持 ? 键存在查询。

jsonb_path_ops 比 jsonb_ops 更小更快的原因是它不索引值，从而大幅减少键的总数——对于有大量不同 JSON 值的场景尤其显著。

五、GIN vs GiST：三角权衡与选择建议

5.1 结构差异带来的性能差异

GIN 和 GiST 的差异源于索引结构的设计哲学不同：

GIN 在本质上是”为搜索优化”的索引。它把写操作的复杂度通过 pending list 延迟分摊了。

5.2 全文搜索：GIN vs GiST

对于 tsvector 全文搜索，GIN 和 GiST 都可以用，但表现有显著差异：

-- 场景：10GB 的文档表，100 万行，每行平均 50 个词
CREATE INDEX idx_gist ON docs USING gist (content_tsv);
CREATE INDEX idx_gin  ON docs USING gin  (content_tsv);

-- 查询
SELECT * FROM docs WHERE content_tsv @@ to_tsquery('database & postgres');
```text

**读性能**：GIN 领先。因为词 "database" 和 "postgres" 在 Entry Tree 中只有各一条记录，搜索时只需要两次 B-Tree 查找 + 扫描 Posting 结构拿到 TID bitmap + AND 操作。GiST 需要遍历树，在每个内部节点调用 Consistent 判断该节点的 bounding region 是否可能包含匹配行。

**写性能**：GiST 原始写入更快（单次插入无需分解为多次键操作），但 GIN 通过 Fast Update 在批量导入中反超。对于持续写入的 OLTP 场景，GiST 的写延迟更可预测（没有 pending list 时大时小的问题）；对于以读为主的报表/搜索场景，GIN 的读性能优势明显。

**存储**：GIN 索引通常比同场景的 GiST 索引大 2-3 倍。因为 GIN 为每个 Posting Tree 维护完整的 B-Tree 页面结构，而 GiST 的节点密度更高。

一句话总结：GIN 是为读优化的倒排索引，适用于"写一次、读很多次"的全文搜索；GiST 是通用平衡树，适用于"读写均衡"或"写频繁"的全文搜索。

### 5.3 数组和 JSONB：GIN 几乎总是更优

对于 `intarray` 和 JSONB 索引，GIN 是事实标准。GiST 也有对应的操作符类（`gist__int_ops`、`gist_jsonb_ops`），但在这些场景下 GIN 的倒排模型是天然匹配的——数组的元素和 JSON 的键天然就是倒排索引的"键"。

唯一值得用 GiST 的场景是：数组很短（如 2-3 个元素）且写入频率高。在这种情况下 GIN 的 O(N_keys) 逐键插入开销与 GiST 的 O(1) 插入差距不大，但 GiST 的更低存储开销和更快构建速度可能有优势。

### 5.4 选择建议

| 场景 | 推荐 | 原因 |
|------|------|------|
| 全文搜索、读多写少 | GIN | 搜索性能最优，通过 VACUUM 后台清理 pending list |
| 全文搜索、写多读少 | GiST | 写延迟可预测，不需要维护 pending list |
| 全文搜索、写入量大但有批量写窗口 | GIN + 定期 `gin_clean_pending_list()` | 批量写完后清理，之后查询跑得飞快 |
| 数组包含查询 (`@>`, `&&`) | GIN | 倒排模型天然匹配，`intarray` 的 GIN 操作符类成熟 |
| JSONB 键存在查询 (`?`, `?|`, `?&`) | GIN (`jsonb_ops`) | GiST 不支持这些操作符 |
| JSONB 路径包含 (`@>`) 且对索引大小敏感 | GIN (`jsonb_path_ops`) | 比 `jsonb_ops` 小很多，因为不索引值 |
| 几何类型、KNN 最近邻搜索 | GiST | GIN 不支持距离排序，GiST 有内置的 `sortsupport` |
| 小数组（< 5 元素）+ 高频写入 | GiST | 倒排优势不明显，GiST 更低存储开销 |

---

## 六、关键参数与运维考量

### 6.1 构建期间的 work_mem

GIN 索引构建使用 `maintenance_work_mem`（不是 `work_mem`）作为排序缓冲区。构建时的工作流程是：扫描全表 → 对每一行调用 `extractValue` 提取键 → 收集所有 (key, TID) 对 → 按键排序 → 批量构建 Entry Tree 和 Posting 结构。`maintenance_work_mem` 决定了排序时可以同时处理多少条目。官方文档明确指出："don't skimp on work memory during index creation"。

### 6.2 gin_pending_list_limit 的调优

默认值为 4MB。调优思路：

- **读多写少的搜索表**：调小（如 1MB），降低 pending list 扫描代价。
- **高频小写入的 OLTP 表**：调大（如 16MB），减少前台触发合并的概率。
- **批量写后读的表**：保持默认，写入完成后显式调用 `gin_clean_pending_list()`。

### 6.3 监控 Pending List 大小

```sql
-- 查看 GIN 索引的 pending list 页面数
SELECT indexrelname,
       pg_relation_size(indexrelid) AS total_size,
       -- pending list 页面可以通过 pgstatginindex() 查看（需要 pgstattuple 扩展）
       pgstatginindex(indexrelid)
FROM pg_stat_user_indexes
WHERE indexrelname LIKE '%gin%';

pgstattuple 扩展提供 pgstatginindex() 函数，返回 pending_pages 和 pending_tuples 两个字段，直接监控 pending list 的实际大小。

七、关键要点

1. GIN 是倒排索引——从键映射到行，而不是从行映射到键。Entry Tree 是 B-Tree over keys，每个键只存一次；Posting List（紧凑，单页内）和 Posting Tree（独立 B-Tree）存储该键出现的所有行 ID。
2. Fast Update 通过 pending list 延迟合并——插入时只做线性追加，合并留给 VACUUM 或 gin_clean_pending_list()。代价是搜索时必须额外扫描 pending list。
3. gingetbitmap() 是 GIN 唯一的搜索路径——对每个查询键收集 TID bitmap，按 AND/OR 语义合并，通过 consistent() 回调做最终过滤。recheck = true 时从 heap 重读原始数据。
4. tsvector 和 intarray 是 GIN 的最优场景——键的重复度高、查询为包含/匹配语义，与倒排模型天然吻合。
5. GIN 为读优化，GiST 为写均衡——GIN 搜索快、存储大、原始写入慢但 Fast Update 弥补；GiST 搜索较慢、存储小、写入延迟可预测。全文搜索读多选 GIN，写多选 GiST；数组和 JSONB 几乎总是 GIN。

上一章：GiST 索引 下一章：BRIN 与其他索引，拆解 BRIN 的范围摘要哲学、revmap 结构、超大表 IO 优化，以及 Hash 和 Bloom 索引的使用边界。

参考资料

源码（PG 17）

• src/backend/access/gin/gininsert.c：gininsert()、ginInsertCleanup() 插入与 pending list 清理
• src/backend/access/gin/ginget.c：gingetbitmap() bitmap scan 搜索路径
• src/backend/access/gin/ginbtree.c：Entry Tree 和 Posting Tree 的 B-Tree 操作
• src/backend/access/gin/gindatapage.c：Posting List/Tree 的数据页操作
• src/backend/access/gin/ginentrypage.c：Entry Tree 叶子页操作
• src/backend/access/gin/ginvacuum.c：VACUUM 触发的 pending list 清理与页面回收
• src/backend/access/gin/ginutil.c：通用工具函数与回调
• src/include/access/gin.h：GIN 核心数据结构定义
• src/include/access/gin_private.h：GIN 内部数据结构（GinBtreeData、GinPostingTreeScan 等）
• src/backend/access/gin/ginxlog.c：GIN 的 WAL 记录类型

官方文档

• PostgreSQL 17 Documentation, Chapter 66: GIN Indexes
• PostgreSQL 17 Documentation, Section 66.3: GIN Extensibility（extractValue、extractQuery、consistent 回调接口）

扩展模块

• contrib/intarray/：intarray GIN 操作符类的实现
• contrib/pg_trgm/：三元组 GIN 索引（LIKE/ILIKE 模糊搜索）
• contrib/btree_gin/：为普通标量类型提供 GIN 操作符

相关文章

• Oleg Bartunov, Teodor Sigaev. “GIN — A Generalized Inverted iNdex for PostgreSQL.” PGCon 2006. — GIN 的原始设计论文
• Egor Rogov. PostgreSQL 16 Internals, Part V, Chapter: GIN.