# B-树之外
> 何时该使用 GIN、GiST、SP-GiST、BRIN 或哈希索引，它们各自的代价是什么，以及如何用实测计划证明它确实带来了帮助。
---
LLMS 索引： [llms.txt](/llms.txt)
---
在同一张两百万行的表上，对同一列建两个索引。两个索引都能把 35,000 页的顺序扫描降到几百页甚至更少。其中一个的大小只有另一个的一千八百分之一：
```text
relname | pg_size_pretty
-----------------------+----------------
events_created_brin | 24 kB
events_created_btree | 43 MB
```
小的是 BRIN 索引，而它究竟是绝妙还是毫无用处，完全取决于你的行在磁盘上如何排列。整章都浓缩在这一个例子里。每种索引类型都回答一个问题。问对了，它就是整座楼里最快的东西；问错了，它就是每次写入都要付费的累赘。
[B-树](/17-btree/#basics-chapter-17)回答的是“哪些行具有这个值？按顺序返回这些行？” Postgres 还提供另外五种索引类型：
| 访问方法 | 它回答的问题 |
|---|---|
| GIN | 哪些行*包含*这个元素？（jsonb 键、数组成员、单词、三字符组） |
| GiST | 哪些行与这个形状*重叠*、*接近*或*包含*它？（范围、几何图形、相似度） |
| SP-GiST | GiST 的同类方法，用于能够干净划分的数据（前缀、点、IP 范围） |
| BRIN | 哪些*页范围*可能包含这个值？（自然有序的数据） |
| 哈希 | 哪些行*等于*这个值？只有这个问题。 |
**Table 18-1.** B-树之外
和 B-树一章一样，证据在 `Buffers:` 这一行：8 KB 页（[Buffers 才是证据](/19-explain/#buffers-are-the-evidence)）。
## GIN 搜索很快，更新很贵 {#gin-is-fast-to-search-and-expensive-to-update}
B-树每行只有一个索引项；当你要在一个值的*内部*搜索时，这就没有用了：比如 `jsonb` 文档中的键、数组中的标签、评论中的单词。**GIN**（广义倒排索引，Generalized Inverted iNdex）为每个*不同的元素*存储一个索引项，后面跟着包含它的行，就像书末的索引：
```text
rows GIN index
──────────────────────────── ──────────────────────────────
(0,1) {region: ams, status: ok} "ams" → (0,1) (0,7) ...
(0,2) {region: iad, status: failed} "failed" → (0,2) (0,5) ...
(0,3) {region: iad, status: ok} "iad" → (0,2) (0,3) ...
... "ok" → (0,1) (0,3) ...
"region" → every row
"status" → every row
```
反过来的代价是：一行会产生很多索引项，所以 GIN 搜索很快，更新却很贵。
### 对包含查询，jsonb_path_ops 胜过默认类 {#for-containment-jsonb_path_ops-beats-the-default}
`payload` 保存这样的文档：`{"region": "syd", "status": "failed", "duration_ms": 4242}`。找出一个区域中的某个时长：
```sql
select id from events
where payload @> '{"duration_ms": 4242, "region": "syd"}';
```
`@>` 表示“包含”。GIN 为 jsonb 提供两个操作符类，选择很重要：
| 操作符类 | 索引大小 | 索引部分的页数 | 整个查询的页数 |
|---|---|---|---|
| 无索引 | | | 35,173 |
| `jsonb_ops`（默认） | 20 MB | 987 | 1,068 |
| `jsonb_path_ops` | 14 MB | 121 | 202 |
**Table 18-2.** 对包含查询，jsonb_path_ops 胜过默认类
默认类分别为键和值建索引，因此这个查询要读取 `"region"` 和 `"duration_ms"` 的列表，而它们出现在每一行中。`jsonb_path_ops`（`using gin (payload jsonb_path_ops)`）把每个值连同它的路径一起哈希，因此 `duration_ms = 4242` 是一个稀有元素。
> [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
>
> ```sql
> select lab.prove(
> 'with jsonb_path_ops, the index reads about 121 pages for the same query',
> lab.node_pages($$ select id from events
> where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
> 'Bitmap Index Scan') between 90 and 160);
> ```
>
> [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
代价是：包含查询和 jsonpath（`@>`、`@?`、`@@`）都能使用它，但键存在性查询（`?` 及其同类操作符）不能。只有当你要问“这个键存在吗？”时，才保留默认类。
> [!DETAILS]- 深入阅读：每个 jsonb 操作符类能服务什么，不能服务什么
>
> 没有索引时，包含查询会为 81 行执行并行顺序扫描（`Buffers: shared hit=900 read=34273`）。建立 `events_payload_pathops` 后，jsonpath 查询会使用索引：
>
> ```text
> Bitmap Heap Scan on events
> Recheck Cond: (payload @? '$."duration_ms"?(@ == 4242)'::jsonpath)
> -> Bitmap Index Scan on events_payload_pathops
> ```
>
> 键存在性测试不能使用它，会退回顺序扫描：
>
> ```text
> Gather
> Workers Planned: 2
> -> Parallel Seq Scan on events
> Filter: (payload ? 'seen'::text)
> ```
>
> 已实测的默认类数据：
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'the default jsonb_ops GIN index is about 20 MB',
> > pg_relation_size('events_payload_gin') between 18e6 and 23e6);
> >
> > select lab.prove(
> > 'with jsonb_ops, the index alone reads about 987 pages for 81 rows',
> > lab.node_pages($$ select id from events
> > where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
> > 'Bitmap Index Scan') between 850 and 1150);
> >
> > select lab.prove(
> > 'the jsonb_path_ops index is about 14 MB',
> > pg_relation_size('events_payload_pathops') between 12.5e6 and 16e6);
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
> [!NOTE] GIN 不会为箭头操作符建索引
>
> `payload` 上的 GIN 索引不能服务 `payload->>'status' = 'failed'` 或 `(payload->>'duration_ms')::int > 1000`。先提取再比较，需要在该精确表达式上建立 B-树[表达式索引](/17-btree/#an-index-stores-exactly-what-you-gave-it)。把测试写成包含查询（`payload @> '{"status": "failed"}'`）即可使用 GIN，或者把热点字段提升为真实列（[你还不需要另一个数据库](/15-models/#basics-chapter-15)）。
### GIN 对低选择性的查询没有帮助 {#gin-doesnt-help-unselective-queries}
索引是通往少数行的捷径。`payload @> '{"status": "failed", "region": "syd"}'` 匹配约 100,000 个事件，占表的 5%，而这些行分布在 35,173 个页中的 33,343 个上（`Heap Blocks: exact=33343`）。这次“索引扫描”几乎读取了所有数据，而且比它所替代的顺序扫描还慢。“每个区域的失败数”需要顺序扫描、汇总表，或者在你关心的那部分数据上建部分 B-树索引。
> [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
>
> ```sql
> select lab.prove(
> 'those rows sit on about 33,343 of the 35,173 heap pages (over 90 percent)',
> lab.node_sum($$ select count(*) from events
> where payload @> '{"status": "failed", "region": "syd"}' $$,
> 'Bitmap Heap Scan', 'Exact Heap Blocks')
> > 0.9 * (select relpages from pg_class where relname = 'events'));
> ```
>
> [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
### 数组：把它写成包含查询 {#arrays-spell-it-as-containment}
GIN 对数组的工作方式也一样：对 `tags text[]` 列（位于 `projects` 表中），`tags @> '{gdpr}'` 读取 53 个页，而不是 507 个。陷阱在写法上。`'gdpr' = any (tags)` 不是 GIN 操作符，因此会执行顺序扫描。写成 `tags @> array['gdpr']`（如果要表达“任意一个”，则用 `&&`）。
> [!DETAILS]- 深入阅读：同一个问题，两种写法，两种计划
>
> ```sql
> alter table projects add column tags text[] not null default '{}';
> -- 1 to 4 random tags per project from a list of 20, plus 'gdpr' on 50 projects
> -- (the lab has the exact update)
> create index projects_tags_idx on projects using gin (tags);
> ```
>
> ```text
> Bitmap Heap Scan on projects (actual ... rows=50.00 loops=1)
> Heap Blocks: exact=50
> Buffers: shared hit=53
> -> Bitmap Index Scan on projects_tags_idx (actual ... rows=50.00 loops=1)
> Buffers: shared hit=3
> ```
>
> 先读取 3 个索引页，再为每个带标签的项目读取一个堆页。使用 `= any` 的写法时：
>
> ```text
> Seq Scan on projects
> Filter: ('gdpr'::text = ANY (tags))
> ```
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'with a GIN index on tags, the index reads 3 pages and the heap one page per match: 53 in all',
> > lab.node_pages($$ select id from projects where tags @> '{gdpr}' $$, 'Bitmap Index Scan') <= 4
> > and lab.buffers($$ select id from projects where tags @> '{gdpr}' $$) between 45 and 56);
> >
> > select lab.prove(
> > '''gdpr'' = any (tags) cannot use the GIN index: a sequential scan',
> > lab.nodes($$ select id from projects where 'gdpr' = any (tags) $$) = '{Seq Scan}');
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
### 一次全文 GIN 搜索读取 51 个页，而不是 6,671 个 {#a-full-text-gin-search-read-51-pages-not-6671}
全文搜索会把文本转换为 `tsvector`：一个按顺序排列的规范化词语列表（**词素（lexemes）**，例如 “The deploys failed” 会变成 `'deploy' 'fail'`），然后由 GIN 为这些词素建索引。在一张包含 25 万条短评论的测试表上，搜索“deadlock”读取了 51 个页，而不是全部 6,671 个页。做法是使用一个存储的 `tsvector` 列、一个 GIN 索引，以及用 `@@` 进行匹配。解析用户输入（[websearch_to_tsquery](/23-search/#websearch_to_tsquery-never-raises-a-syntax-error)）和排序评分（[需要读取每个匹配项](/23-search/#ranking-reads-every-match)）属于[不用搜索引擎，也能搜索](/23-search/#basics-chapter-23)一章。
> [!DETAILS]- 深入阅读：五行建立全文索引
>
> ```sql
> create table comments (
> id bigint generated always as identity primary key,
> event_id bigint not null references events (id),
> body text not null,
> search tsvector generated always as (to_tsvector('english', body)) stored
> );
> -- one per comment event: 249,934 comments of 6 to 15 words,
> -- 49 of them mention "deadlock" (the lab has the generator)
>
> create index comments_search_idx on comments using gin (search);
> ```
>
> ```text
> Bitmap Heap Scan on comments (actual ... rows=49.00 loops=1)
> Heap Blocks: exact=49
> Buffers: shared hit=27 read=24
> -> Bitmap Index Scan on comments_search_idx (actual ... rows=49.00 loops=1)
> Buffers: shared hit=2
> ```
>
> 两个索引页；另外 49 个是每条匹配评论对应的一个堆页。对向量和查询都显式传入配置（`'english'`），这样词干提取才能匹配，生成列的表达式也能满足不可变性要求。
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'without an index, a search reads every page of comments (about 6,700)',
> > lab.buffers($$ select id, body from comments
> > where search @@ to_tsquery('english', 'deadlock') $$) between 6400 and 7000);
> >
> > create index comments_search_idx on comments using gin (search);
> >
> > select lab.prove(
> > 'with a GIN index, the search finds all 49 and the index reads under 5 pages',
> > lab.node_sum($$ select id, body from comments where search @@ to_tsquery('english', 'deadlock') $$,
> > 'Bitmap Heap Scan', 'Actual Rows') = 49
> > and lab.node_pages($$ select id, body from comments where search @@ to_tsquery('english', 'deadlock') $$,
> > 'Bitmap Index Scan') < 5);
> >
> > select lab.prove(
> > 'the full-text index is about 2.4 MB for a quarter-million comments',
> > pg_relation_size('comments_search_idx') between 2.0e6 and 3.0e6);
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
### 待处理列表让一次插入承担许多次插入的代价 {#the-pending-list-makes-one-insert-pay-for-many}
GIN 会把新索引项暂存在未排序的**待处理列表（pending list）**中，然后批量合并。默认开启（`fastupdate`），并且会增长到 `gin_pending_list_limit`，也就是 4 MB。哪次插入把它撑爆，哪次就要为合并全部 4 MB 买单。表现是：插入通常很快，偶尔有一次却要花几百毫秒。解决办法是为这个索引设置更小的 `gin_pending_list_limit`，或者设置 `fastupdate = off`，用稳定的代价替代尖峰代价。
> [!DETAILS]- 深入阅读：观察待处理列表增长
>
> 插入 5,000 个事件（复制最新的事件），然后查看 `jsonb_path_ops` 索引：使用 `pgstatginindex`（来自 `pgstattuple`）：
>
> ```text
> version | pending_pages | pending_tuples
> ---------+---------------+----------------
> 2 | 37 | 5000
> ```
>
> 每次搜索现在还要线性扫描那 37 个页：包含查询读取的索引页从 121 个增加到 158 个。清理会合并这个列表，执行 `select gin_clean_pending_list('events_payload_pathops')` 也会合并。
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'after 5,000 inserts the pending list holds 5,000 tuples on a few dozen pages',
> > (select pending_tuples = 5000 and pending_pages between 25 and 60
> > from pgstatginindex('events_payload_pathops')));
> >
> > select lab.prove(
> > 'every search now scans the pending pages too (121 index pages became about 158)',
> > lab.node_pages($$ select id from events
> > where payload @> '{"duration_ms": 4242, "region": "syd"}' $$,
> > 'Bitmap Index Scan')
> > - :pages_before >= (select pending_pages - 2 from pgstatginindex('events_payload_pathops')));
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
## pg_trgm 让前置通配符也能使用索引 {#pg_trgm-makes-a-leading-wildcard-indexable}
B-树从字符串开头开始排序，因此它最多服务类似 `like 'user42%'` 的前缀查询（而且还需要正确的操作符类，下一节会说明），永远不能服务 `like '%r4242@%'`。`pg_trgm` 扩展把字符串拆成**三字符组（trigrams）**，即每三个字符组成的序列（`show_trgm('user4242')`），从而让子串搜索能够使用索引：
```text
{" u"," us",242,"42 ",424,er4,r42,ser,use}
```
包含 `r4242@` 的字符串一定包含这个片段的三字符组，因此索引会求出它们列表的交集，再重新检查少数候选项。没有这个索引时，按 email 片段搜索会读取 `users` 的全部 1,126 个页。有了它：
```sql
create index users_email_trgm_gin on users using gin (email gin_trgm_ops);
```
```text
Bitmap Heap Scan on users (actual time=0.025..0.025 rows=1.00 loops=1)
Recheck Cond: (email ~~* '%R4242@%'::text)
Buffers: shared hit=10
```
一共 10 个页，而且这是 `ilike`（`~~*`）查询：同一个索引也能服务不区分大小写的匹配和正则表达式。模式中至少要有三个固定字符，才会有三字符组可供查找。
### 前缀查询需要正确的操作符类 {#prefix-search-needs-the-right-operator-class}
即使 `like 'user4242@%'` 也不能使用 `email` 上的普通 B-树。在这个数据库的 `en_US.utf8` 这样的非 C [排序规则](/43-glossary/#collation)下，B-树顺序不是字节顺序，因此前缀不一定对应一个连续范围。使用 `text_pattern_ops`（按字节排序）建索引，前缀就变成了一个范围：
```text
Index Scan using users_email_pattern on users (actual ... rows=1.00 loops=1)
Index Cond: ((email ~>=~ 'user4242@'::text) AND (email ~<~ 'user4242A'::text))
```
这个索引不能在数据库排序规则下服务 `<`、`>` 或 `order by`。两种需求都要？那就两个索引都建，或者在列上使用 C 排序规则。
### GIN 过滤三字符组；GiST 按相似度排序 {#gin-filters-trigrams-gist-ranks-by-similarity}
`pg_trgm` 也提供 GiST 操作符类。对于 `like` 和正则表达式，GIN 完胜：GiST 索引大小是三倍（11 MB 对 3,504 KB），却读取了 163 个页，而 GIN 只读 10 个。
但 GiST 有一件 GIN 做不到的事：按**相似度**顺序返回行（`order by email <-> 'usr4242@exmaple.com' limit 5`），也就是“你是不是想找……”查询。这是一次**最近邻**搜索，会按距离顺序遍历树（PostGIS 对 geography 也这样做）。GIN 用于过滤，GiST 用于按最近匹配排序。
> [!DETAILS]- 深入阅读：你是不是想找：用 GiST 按相似度排序
>
> `<->` 是三字符组距离（1 减去相似度）：
>
> ```sql
> select email, round((email <-> 'usr4242@exmaple.com')::numeric, 3) as dist
> from users
> order by email <-> 'usr4242@exmaple.com'
> limit 5;
> ```
>
> ```text
> email | dist
> -----------------------+-------
> user4242@example.com | 0.481
> user42424@example.com | 0.536
> user24242@example.com | 0.536
> ...
> ```
>
> 使用 GiST 索引时，计划是按距离排序的索引扫描：
>
> ```text
> Limit (actual time=14.166..14.184 rows=5.00 loops=1)
> Buffers: shared hit=1427
> -> Index Scan using users_email_trgm_gist on users (actual rows=5.00 loops=1)
> Order By: (email <-> 'usr4242@exmaple.com'::text)
> ```
>
> | `users.email` 上的三字符组索引 | 大小 | 构建时间（我们的机器） | `like '%r4242@%'` 的页数 |
> |---|---|---|---|
> | GIN（`gin_trgm_ops`） | 3,504 KB | 140 ms | 10 |
> | GiST（`gist_trgm_ops`） | 11 MB | 550 ms | 163 |
>
>
>
> **Table 18-3.** GIN 过滤三字符组；GiST 按相似度排序
>
> 没有 GiST 索引时，Postgres 会计算全部 100,000 个距离并排序：在我们的机器上约 90 ms，而有索引时是 15 ms。这个索引访问的页数（1,427）反而多于那张 1,126 页表的顺序扫描，因为这些合成 email 彼此很像；它节省的是 CPU，因为计算相似度才是昂贵的部分。数据越多样，剪枝效果应该越好。
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'trigram GiST on email is about 11 MB, over 2.5 times the GIN',
> > pg_relation_size('users_email_trgm_gist') between 10e6 and 13.5e6
> > and pg_relation_size('users_email_trgm_gist')::numeric
> > / pg_relation_size('users_email_trgm_gin') > 2.5);
> >
> > select lab.prove(
> > 'with GiST, the similarity search is an index scan ordered by distance',
> > lab.nodes($$ select email from users order by email <-> 'usr4242@exmaple.com' limit 5 $$)
> > = '{Limit,Index Scan}');
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
## GiST 为没有顺序的数据建立索引 {#gist-indexes-values-that-have-no-order}
B-树需要全序，而很多类型并没有全序：到底应该把 9:00 到 17:00 放在 12:00 到 13:00 前面，还是反过来？**GiST**（广义搜索树，Generalized Search Tree）仍然可以为它们建立索引。每个内部条目都保存一个覆盖其下所有内容的*边界值*，搜索会进入边界可能匹配的每个子节点。
GiST 最出名的用途，是强制执行“这类对象不能有两个相互重叠”的规则，即[排他约束](/14-relationships/#an-exclusion-constraint-makes-overlaps-impossible)；它会建立 GiST 索引，在每次插入时进行检查。假设项目可以声明部署冻结期，而且每个项目同时最多只能有一个冻结期：
```sql
create extension if not exists btree_gist; -- lets GiST compare plain bigints
create table deploy_freezes (
id bigint generated always as identity primary key,
project_id bigint not null references projects (id),
during tstzrange not null,
reason text not null,
exclude using gist (project_id with =, during with &&)
);
```
这个索引揭示了一个教训。加载 480,000 个冻结期后，查询“此刻哪些项目处于冻结状态？”通过约束索引读取了 7,188 个页，而这个索引的第一列是 `project_id`，所以它比顺序扫描的 4,548 个页还差。只在 `during` 上建立 GiST 索引则需要 460 个页，其中只有 7 个是索引页。**约束背后的索引，不会自动成为适合查询的好索引。**
> [!DETAILS]- 深入阅读：为什么约束索引输给了顺序扫描
>
> ```text
> Bitmap Heap Scan on deploy_freezes (actual time=81.942..84.276 rows=470.00 ...)
> Buffers: shared hit=35 read=7153
> -> Bitmap Index Scan on deploy_freezes_project_id_during_excl (actual ...)
> Index Cond: (during @> (now() - '100 days'::interval))
> Buffers: shared read=6735
> ```
>
> GiST 没有严格意义上的“第一列”，但第一列仍然决定条目如何分组到各个页中，因此只查询 `during` 时，几乎要遍历整个索引。使用 `create index deploy_freezes_during_idx on deploy_freezes using gist (during)` 后：
>
> ```text
> Bitmap Heap Scan on deploy_freezes (actual time=1.418..9.701 rows=470.00 loops=1)
> Buffers: shared read=460
> -> Bitmap Index Scan on deploy_freezes_during_idx (actual rows=470.00 loops=1)
> Buffers: shared read=7
> ```
>
> GiST 的范围操作符包括 `&&`（重叠）、`@>`（包含）、`<@`（被包含），以及相邻和严格左/右操作符。下面的检查还会确认约束确实起作用：新年冻结期落在已有的假期冻结期内时，会因 `exclusion_violation` 被拒绝。
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > do $$
> > begin
> > insert into deploy_freezes (project_id, during, reason)
> > values (4242, tstzrange('2026-12-31', '2027-01-02'), 'new year');
> > raise exception 'NOT PROVED: the overlapping freeze was accepted';
> > exception when exclusion_violation then
> > perform set_config('lab.freeze_rejected', 'yes', false);
> > end $$;
> > select lab.prove(
> > 'an overlapping freeze for the same project is rejected (exclusion_violation)',
> > current_setting('lab.freeze_rejected', true) = 'yes');
> >
> > select lab.prove(
> > 'the constraint''s index, led by project_id, reads more pages than the sequential scan',
> > lab.buffers($$ select project_id, reason from deploy_freezes
> > where during @> now() - interval '100 days' $$) > :seq_pages);
> >
> > create index deploy_freezes_during_idx on deploy_freezes using gist (during);
> >
> > select lab.prove(
> > 'a GiST index on the range alone answers in about 7 index pages',
> > lab.node_pages($$ select project_id, reason from deploy_freezes
> > where during @> now() - interval '100 days' $$, 'Bitmap Index Scan') < 20);
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
## 你很少会需要 SP-GiST {#youll-rarely-need-sp-gist}
SP-GiST 适用的地方，B-树或 GiST 通常也能做得差不多，而它们的行为你已经熟悉了。**SP-GiST**（空间分区广义搜索树，space-partitioned GiST）用于可以拆分成互不重叠区域的数据（前缀、点、IP 网络），因此搜索只需沿一条路径前进。在 `users.email` 上，它用一个 4,672 KB 的索引、5 个页就完成了前缀查询（`email ^@ 'user4242@'`），索引大小与 B-树大致相同。对于 `inet` 的包含和范围查询，它是 GiST 的一种替代方案；两者都要基准测试。
## BRIN 为每个页范围保留一份汇总 {#brin-keeps-one-summary-per-range-of-pages}
回到开头。`events` 是只追加表：行按 `created_at` 顺序到达，而且不会移动。`pg_stats.correlation` 衡量列的顺序与物理行顺序有多一致：`created_at` 和 `id` 为 1，`project_id` 约为 0.003。
**BRIN**（块范围索引，Block Range INdex）利用了这一点。它为每个 `pages_per_range` 页组成的范围保存一份汇总（默认是 128 页）：最小值和最大值。想象搬家箱子上的标签。查询某一天的数据时，它会跳过标签不可能匹配的箱子，打开一两个可能匹配的箱子，再检查其中的每一行。
```text
heap pages 0..127 128..255 256..383 ... 34944..35071 35072..
┌────────┬─────────┬─────────┬─────┬────────────┬──────┐
BRIN entry │ Oct 06 │ Oct 07 │ Oct 08 │ ... │ Oct 04 │Oct 05│
│ -Oct 07│ -Oct 08 │ -Oct 09 │ │ -Oct 05 │-06 │
└────────┴─────────┴─────────┴─────┴────────────┴──────┘
query "May 1": skip, skip, skip, ..., read 2 ranges, ..., skip
```
每个标签覆盖的事件时间跨度约为一天又三分之一。35,000 个页只需要约 275 个标签，所以大小是 24 KB。
### 大小只有千分之一，页数却几乎相同 {#a-thousandth-of-the-size-nearly-the-same-pages}
按事件类型汇总一天的事件：
| `created_at` 上的索引 | 大小 | 查询一天数据的页数 |
|---|---|---|
| 无 | 0 | 35,272 |
| BRIN，每个范围 128 个页 | 24 KB | 261 |
| BRIN，每个范围 32 个页 | 48 KB | 133 |
| BRIN，每个范围 8 个页 | 168 KB | 130 |
| B-树 | 43 MB | 115 |
**Table 18-4.** 大小只有千分之一，页数却几乎相同
B-树在页数上险胜。但它的大小是默认 BRIN 的 1,800 倍，要和数据争夺缓存，而且每次插入都要沿树下行。每个范围 32 页的 BRIN，大小不到 B-树的九百分之一，页数却只相差不超过 20 个。范围再小就不划算了：每个范围 8 页时，索引自身读取了 26 个页，而每个范围 32 页时只读 5 个，几乎抵消了它省下的 24 个堆页。
> [!DETAILS]- 深入阅读：读取 BRIN 计划：有损页，以及并非真实行数的 rows
>
> 这一天是 `created_at >= '2026-05-01' and created_at < '2026-05-02'`，并按 `kind` 分组。使用 `create index events_created_brin on events using brin (created_at)`，并关闭并行：
>
> ```text
> HashAggregate (actual time=2.638..2.640 rows=5.00 loops=1)
> Buffers: shared hit=261
> -> Bitmap Heap Scan on events (actual ... rows=5480.00 loops=1)
> Rows Removed by Index Recheck: 9078
> Heap Blocks: lossy=256
> -> Bitmap Index Scan on events_created_brin (actual rows=2560.00 loops=1)
> Buffers: shared hit=5
> ```
>
> BRIN 位图总是有损的（它们只记录页，从不记录行），因此堆扫描会读取 256 个页中的每一行，再由重新检查丢弃 9,078 行。BRIN 节点上的 `rows=2560` 不是行数：BRIN 会把每个匹配页报告为 10 行的占位值（`totalpages * 10`，见 [brin.c](https://github.com/postgres/postgres/blob/master/src/backend/access/brin/brin.c)）。`pageinspect` 会显示标签本身（`brin_page_items(get_raw_page('events_created_brin', 2), 'events_created_brin')`）：
>
> ```text
> blknum | value
> --------+------------------------------------------------------------
> 0 | {2025-10-06 00:00:15.768+00 .. 2025-10-07 07:52:39.504+00}
> 128 | {2025-10-07 07:52:55.272+00 .. 2025-10-08 15:46:06.312+00}
> ...
> ```
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'with BRIN (128 pages per range), the one-day summary reads about 261 pages',
> > lab.buffers(:'day_query') between 200 and 320);
> >
> > select lab.prove(
> > 'BRIN at 32 pages per range gets within 20 pages of the B-tree',
> > :brin32_pages - :btree_pages <= 20);
> >
> > select lab.prove(
> > 'the B-tree is over 1,000 times larger than the BRIN (about 1,800)',
> > pg_relation_size('events_created_btree')::numeric / pg_relation_size('events_created_brin') > 1000);
> >
> > select lab.prove(
> > 'the BRIN node''s "rows" is ten per matching page, not a row count',
> > lab.node_sum(:'day_query', 'Bitmap Index Scan', 'Actual Rows')
> > = 10 * lab.node_sum(:'day_query', 'Bitmap Heap Scan', 'Lossy Heap Blocks'));
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
### 没有物理顺序，BRIN 就没有用 {#brin-is-useless-without-physical-order}
`project_id` 的相关性为零，每个箱子里几乎都有每个项目，因此每个箱子都“可能匹配”。强制在它上面使用 BRIN，结果仍会读取整张表的每一页（`Buffers: shared hit=50 read=35266`）。
BRIN 应用于跟随插入顺序的列：只追加表上的时间戳、序列 ID、日志偏移量（[为了删除而分区](/39-partitioning/#basics-chapter-39)会把它和按时间分区配合起来）。要保护这种顺序：更新移动的行、回填旧数据，以及重新使用已释放空间的新行，都会让标签覆盖的范围变宽，直到索引不再剪枝。
> [!NOTE] 新页不会立即汇总
>
> VACUUM 或 `brin_summarize_new_values()` 会汇总索引建立后填充的页范围；在此之前，这些范围总会被扫描。在繁忙的只追加表上，创建 BRIN 索引时加上 `with (autosummarize = on)`。
## 哈希索引只有在长键等值查询上才占优 {#a-hash-index-wins-only-on-equality-over-long-keys}
对于 令牌和内容哈希这类较长的随机值，等值查询可以使用哈希索引。除此之外，都使用 B-树。
哈希索引为每个键存储一个 32 位哈希值，并且只支持一个操作符：`=`。它不支持范围、排序、唯一性或仅索引扫描。作为交换，它的大小不取决于键的宽度。对于 128 个字符的 API 密钥，B-树大小为 16 MB，哈希索引为 4,112 KB，一次查找读取 3 个页，而不是 5 个。对于约 20 个字符的 `email`，哈希索引仍是 4,112 KB，B-树则更小。PostgreSQL 10 起哈希索引就能安全应对崩溃；它的坏名声更早。
> [!DETAILS]- 深入阅读：哈希索引的测量方法
>
> ```sql
> alter table users add column api_key text;
> -- 128 hex characters
> update users set api_key = encode(sha512(('key' || id)::bytea), 'hex');
> create index users_api_key_btree on users (api_key);
> create index users_api_key_hash on users using hash (api_key);
> ```
>
> > [!EXAMPLE]- 动手验证 · lab `17-more-indexes`
> >
> > ```sql
> > select lab.prove(
> > 'on the long key, the hash index is about a quarter of the B-tree',
> > pg_relation_size('users_api_key_hash')::numeric / pg_relation_size('users_api_key_btree')
> > between 0.2 and 0.3);
> >
> > select lab.prove(
> > 'the hash index size does not depend on key width: same size on email',
> > pg_relation_size('users_email_hash') = pg_relation_size('users_api_key_hash'));
> >
> > select lab.prove(
> > 'a hash lookup on api_key touches 3 pages (metapage, bucket, heap)',
> > lab.buffers($$ select id from users where api_key = encode(sha512('key4242'::bytea), 'hex') $$) = 3);
> > ```
> >
> > [完整实验脚本](https://www.flagon.io/books/eight-kilobytes/lab/17-more-indexes.sql)
## 操作符决定索引类型 {#the-operator-picks-the-index-type}
| 你的查询使用 | 使用 |
|---|---|
| `=`、`<`、`>`、`order by`、前缀 `like` | B-树（非 C 排序规则中的前缀使用 `text_pattern_ops`） |
| jsonb `@>`、`@?` | GIN `jsonb_path_ops` |
| jsonb 键存在性（`?`） | GIN `jsonb_ops`（默认） |
| jsonb `->>` 配合 `=`、`<`、排序 | B-树表达式索引，或真实列 |
| 数组 `@>`、`&&` | GIN（不是 `x = any (col)`） |
| 全文 `@@` | 在已存储的 `tsvector` 上建 GIN |
| `like '%x%'`、`ilike`、正则表达式 | GIN `gin_trgm_ops` |
| “你是不是想找” | GiST `gist_trgm_ops` |
| 范围重叠、排他约束 | GiST（加上 `btree_gist` 才能混用 `=`） |
| 只追加数据中的时间或 ID | 如果相关性接近 1，则使用 BRIN |
| 长随机键上的 `=` | 哈希索引 |
**Table 18-5.** 操作符决定索引类型
无论选择哪种，都要测量前后的页数。这些索引每一个都会增加写入代价，GIN 尤其如此，因此只保留能带来一个数量级收益的索引。
## 本章要点 {#the-short-version}
- GIN 为值内部的元素建立索引。搜索快，更新贵；插入延迟出现尖峰，通常意味着待处理列表正在起作用。
- 对 jsonb 包含查询使用 `jsonb_path_ops`：索引读取 121 个页，而不是 987 个。GIN 不能服务 `payload->>'key' = 'x'`。
- 对 `like '%x%'` 使用三字符组 GIN 索引；三字符组 GiST 只用于按相似度排序。
- GiST 处理重叠和距离。约束背后的索引不会自动成为适合你查询的好索引。
- 自然有序的列上的 BRIN 很小（24 KB 对 43 MB 的 B-树），范围查询效果却几乎一样；在没有相关性的列上，它会读取整张表。
- 哈希索引只有在长键等值查询上才值得使用。
- 索引只对有选择性的查询有帮助：GIN 查询即使只匹配 5% 的行，也仍然读取了 95% 的页。
## 延伸阅读 {#further-reading}
- [Index Types](https://www.postgresql.org/docs/18/indexes-types.html)，PostgreSQL 文档。所有访问方法及其操作符的官方概览。
- [GIN Indexes](https://www.postgresql.org/docs/18/gin.html)、[GiST Indexes](https://www.postgresql.org/docs/18/gist.html)、[SP-GiST Indexes](https://www.postgresql.org/docs/18/spgist.html)、[BRIN Indexes](https://www.postgresql.org/docs/18/brin.html) 和 [Hash Indexes](https://www.postgresql.org/docs/18/hash-index.html)，PostgreSQL 文档。每种类型各有一页参考文档，包括内置操作符类。
- [src/backend/access/brin/README](https://github.com/postgres/postgres/blob/master/src/backend/access/brin/README)，PostgreSQL 源码。范围映射和汇总的布局方式，以及汇总索引为何可以如此之小。
- [pg_trgm](https://www.postgresql.org/docs/18/pgtrgm.html)，PostgreSQL 文档。三字符组操作符、相似度阈值，以及 GIN 和 GiST 操作符类。
- [jsonb Indexing](https://www.postgresql.org/docs/18/datatype-json.html#JSON-INDEXING)，PostgreSQL 文档。`jsonb_ops` 与 `jsonb_path_ops` 的区别，以及它们各自支持的操作符。
- [Operator Classes and Operator Families](https://www.postgresql.org/docs/18/indexes-opclass.html)，PostgreSQL 文档。`text_pattern_ops` 等操作符类的说明。