17 B-树挑起大梁

大多数慢查询并没有做什么难事。它们只是每次都读取整张表去找少数几行，因为没人告诉 Postgres 应该去哪里找。

这是每当有人打开项目页面时都会运行的一条查询：

explain (analyze, buffers)
select * from events
where project_id = 4242
order by created_at desc
limit 20;

 Limit  ... (actual time=24.828..25.941 rows=20.00 loops=1)
   Buffers: shared hit=358 read=34891
   ...
               ->  Parallel Seq Scan on events  ...
                     Rows Removed by Filter: 666638

它读取了 35,249 个页才返回 20 行：每次打开页面时，都要读取这张表的 35,173 个页中的每一个（events 整整 275 MB），再加上规划和排序所需的几十个页。在我们的笔记本上，表已经在内存中，所以只花了 26 ms，这就是没人注意到它的原因。在缓存是冷的生产机器上，如果同时有 50 个人打开仪表板，这条查询就能让整个数据库停摆。

select lab.prove('with no index, the dashboard query reads the whole table (about 35,249 pages)',
  lab.buffers($$ select * from events where project_id = 4242
                 order by created_at desc limit 20 $$) between 35173 and 35400);

运行正确的 create index 之后，它只读取 23 个页。这是你能买到的最便宜的加速方式，而本章讲的是如何有目的地购买这种收益，同时拒绝那些只会增加成本的索引。在每个计划中，都要看 Buffers: 这一行，它统计的是 8 KB 页。页是证据；毫秒只是天气（Buffers 才是证据）。

B-树是一棵由页组成的浅树

想象一个图书馆的卡片目录：柜子上的标牌告诉你该找哪个抽屉，标签告诉你该找哪张卡片，卡片再告诉你书架在哪里。你不需要读完整个目录。B-树（B-tree）就是用 8 KB 页构成的这类目录，而书架就是堆（heap）：也就是表本身，一堆无序的页（一切都从页说起）。下面是 events 的主键：

叶页按顺序保存每个键，每个键都带有一个元组标识符（TID），也就是该行在堆中的 (page, item) 地址（它的 ctid），并且还链接到相邻叶页，让范围扫描可以横向遍历。上面的页只负责说明下一步该访问哪个子节点。

关键就在这棵树的形状。每个内部页大约指向 300 个子节点，因此三层可以容纳约 3,000 万个键，四层可以容纳约 100 亿个键。让表扩大到原来的 300 倍，查找也只多读取一个页。在 查询就是页和往返中，一个主键查找读取了四个页：树中三个，堆中一个。记住这一点：

一次索引查找的成本，是树的深度加上每个匹配行对应的一个堆页。

查找在树上花费的只有三四个页，而且这个开销几乎不会增长。真正花钱的是堆页，本章剩下的内容都在讲如何少读一些堆页。

select root, level from bt_metap('events_pkey');

select type, count(*) as pages, round(avg(live_items)) as avg_items
from bt_multi_page_stats('events_pkey', 1, -1)
group by type;

 root | level
------+-------
  412 |     2

 type | pages | avg_items
------+-------+-----------
 r    |     1 |        19
 i    |    19 |       289
 l    |  5465 |       367

select lab.prove('5,465 leaves holding about 367 entries of 16 bytes',
  (select count(*) = 5465 and round(avg(live_items)) = 367 and round(avg(avg_item_size)) = 16
   from bt_multi_page_stats('events_pkey', 1, -1) where type = 'l'));

第一个索引：35,249 页降到 91 页

先从最直观的索引开始，在 where 使用的列上建立索引：

create index events_project_id_idx on events (project_id);

 Limit  ... (actual time=0.107..0.109 rows=20.00 loops=1)
   Buffers: shared hit=91
   ->  Sort  ...
         ->  Bitmap Heap Scan on events  ... rows=85.00 ...
               Heap Blocks: exact=85
               ->  Bitmap Index Scan on events_project_id_idx  ...
                     Buffers: shared hit=3

从 35,249 个页降到 91 个页。自下而上读：

• **索引：**读取 3 个页，找到这个项目的全部 85 行。
• **堆：**读取 85 个页，每行一个（Heap Blocks: exact=85）。这些事件在一年中随机到达，因此每一行都落在了不同的页上。
• **排序：**保留最新的 20 行。

读取 3 个页来查找，再读取 85 个页来取数据。这个比例很正常。

create index events_project_id_idx on events (project_id);

select lab.prove('the dashboard query now reads about 91 pages',
  lab.warm_buffers($$ select * from events where project_id = 4242
                  order by created_at desc limit 20 $$) between 85 and 100);

索引能帮多少忙，取决于匹配行有多集中

在索引中找到行很便宜。从堆中取出它们才是账单，而 Postgres 有三种方式来支付这笔账。**索引扫描（Index Scan）会在遍历索引时逐行取出数据，因此行会按顺序返回；上面计划中的位图扫描（bitmap scan）**会先收集所有匹配项，再按物理顺序每个堆页访问一次；**仅索引扫描（index-only scan）**则完全跳过堆。

这里有个不太舒服的事实：匹配行在堆中越集中，索引就越有帮助。 按项目范围请求 events 的 2% 行时，这些行分散在 68% 的页上。超过某个点后，按顺序读取整张表反而更便宜，规划器就会切换到顺序扫描。这不是规划器犯傻，而是规划器在数页。

explain (analyze, buffers)
select * from events where project_id between 4000 and 4400;

 Bitmap Heap Scan on events  ... (actual time=4.074..83.678 rows=39827.00 loops=1)
   Recheck Cond: ((project_id >= 4000) AND (project_id <= 4400))
   Heap Blocks: exact=23913
   ->  Bitmap Index Scan on events_project_id_idx  ...
         Buffers: shared hit=3 read=34

select lab.prove('the index part costs under 50 pages, the heap part about 23,913 pages (68% of the table)',
  (select lab.field(p, 'Bitmap Index Scan', 'Shared Hit Blocks')::int
        + lab.field(p, 'Bitmap Index Scan', 'Shared Read Blocks')::int < 50
      and lab.field(p, 'Bitmap Heap Scan', 'Exact Heap Blocks')::int between 23500 and 24300
   from lab.plan($$ select * from events where project_id between 4000 and 4400 $$) p));

最好的堆页，是你永远不会读到的

统计项目 4242 的事件不需要索引之外的任何信息，因此堆可以完全不打开：

 Aggregate  ...
   Buffers: shared hit=5
   ->  Index Only Scan using events_project_id_idx on events  ... rows=85.00 ...
         Heap Fetches: 0

取出同样的 85 行要付出 91 个页的代价，现在只需 5 个页就能完成计数。

问题在于：索引项不知道它指向的行对你是否可见（更新就是插入）。因此，扫描会检查可见性映射（visibility map）：堆中的每个页都有一位，用来表示“这里的每一行对所有人都可见”（每页两位让扫描和清理跳过工作）。如果这一位没有设置，它仍会读取该行。清理会设置这些位。

多列索引：顺序就是设计

仪表板问的不是“哪些行属于项目 4242？”，而是“项目 4242 最新的 20 个事件是什么？”要为问题建索引，而不是为列建索引。

单列索引能回答第一个问题，却要把排序交给 Postgres：对 85 个事件来说没问题，面对 200,000 个事件就很痛苦。把两列都交给索引：

create index events_project_created_idx on events (project_id, created_at);

 Limit  ... (actual time=0.009..0.023 rows=20.00 loops=1)
   Buffers: shared hit=23
   ->  Index Scan Backward using events_project_created_idx on events  ...

不需要排序。这个项目的条目按时间顺序相邻排列，所以 Postgres 从最新的条目向回走，找到 20 行就停下：3 个索引页加 20 个堆页；无论这个项目有 85 个事件还是 8,500 万个事件，代价都一样。

代价与返回的行数成正比，而不是与存储的行数成正比。这正是你要设计的目标。

create index events_project_created_idx on events (project_id, created_at);

select lab.prove('35,249 pages to 23 is more than 1,000 times less work',
  35249.0 / lab.warm_buffers($$ select * from events where project_id = 4242
                            order by created_at desc limit 20 $$) > 1000);

先等值，再范围或排序

按姓、名排序的电话簿，可以连续找到“姓 Smith、名从 A 到 C”的人。“所有名叫 Alice 的人”则意味着要读完整本电话簿。

下面分别是在 (created_at, project_id) 和 (project_id, created_at) 上查询“这个项目，最近 30 天”的结果：

 Index Scan using events_created_project_idx on events  ... rows=11.00 ...
   Buffers: shared hit=643

 Index Scan using events_project_created_idx on events  ... rows=11.00 ...
   Buffers: shared hit=14

同样是 11 行，前者读取的页数却是后者的 45 倍。把 created_at 放在第一列时，Postgres 会读取最近 30 天内的每一个条目，再逐个检查项目。

-- Leave only the wrong-order index, so the planner has to use it.
begin;
drop index events_project_created_idx;
drop index events_project_id_idx;
select lab.prove('with (created_at, project_id), "this project, last 30 days" reads about 643 pages',
  lab.warm_buffers($$ select * from events where project_id = 4242
                  and created_at >= '2026-09-06' $$) between 500 and 800);
select lab.prove('and the dashboard query reads about 1,399 pages walking the time range backward',
  lab.warm_buffers($$ select * from events where project_id = 4242
                  order by created_at desc limit 20 $$) between 1200 and 1600);
rollback;

这条规则可以写在便签上：

1. 用 =（或 in）比较的列放在前面。
2. 然后最多放一列用于范围查询或 order by。
3. 再往后的列只会被检查，不会缩小读取范围。

在等值列中，把你还会单独查询的那一列放在前面：(a, b) 也能单独服务于 a。PostgreSQL 18 的**跳跃扫描（skip scan）**可以挽救一个查询跳过第一列的索引，但只有在第一列的不同取值很少时才行。不要把希望寄托在它身上。

Buffers: shared hit=44
->  Index Only Scan using events_kind_created_idx on events  ... rows=5480.00 ...
      Index Cond: (created_at >= '2026-10-05 ...'::timestamp with time zone)
      Index Searches: 6

select lab.prove('with 6 index searches for the 5 kinds',
  (select lab.field(p, 'Index Only Scan', 'Index Searches')::int = 6
   from lab.plan($$ select count(*) from events where created_at >= '2026-10-05' $$) p));

select lab.prove('a lookup by email alone does not skip-scan users (account_id, email): 1,000 accounts is too many',
  'Seq Scan' = any(lab.nodes($$ select id from users where email = 'user4242@example.com' $$)));

覆盖索引：覆盖热点查询，而不是每个查询

假设仪表板只显示 created_at 和 kind。最新的 50 行仍然要付出 53 个页的代价，其中几乎全是为了读取 kind 而访问的堆页。把它作为附带列放进索引：

drop index events_project_created_idx;
create index events_project_created_idx
  on events (project_id, created_at) include (kind);

现在它是一个 Index Only Scan，只读取 6 个页。INCLUDE（PostgreSQL 11+）只把额外列存储在叶页中。代价是：索引从 60 MB 增长到 77 MB，每次插入都要写入这些字节。只覆盖每秒运行数千次的两三个查询，其他的都不要覆盖。因为 INCLUDE 列不参与唯一性判断，所以它也是在不改变“唯一”的含义时，给唯一索引增加列的唯一方式。

   Buffers: shared hit=180
         Heap Fetches: 99

   Buffers: shared hit=5
         Heap Fetches: 0

update events set payload = payload || '{"seen": true}' where project_id = 4242;

create temp table ios as
  select lab.plan($$ select created_at, kind from events where project_id = 4242
                     order by created_at desc limit 50 $$) as p;

select lab.prove('after updating the project''s 85 rows, the first index-only scan fetches heap tuples (about 99)',
  (select lab.field(p, 'Index Only Scan', 'Heap Fetches')::int between 50 and 120 from ios));

vacuum events;

select lab.prove('and the same plan reads 5 pages',
  lab.warm_buffers($$ select created_at, kind from events where project_id = 4242
                  order by created_at desc limit 50 $$) <= 6);

只为要查询的行建索引，而不是整张表

值班页面只需要表中的一部分数据。它列出最近失败的部署，大约占事件的 6%，却要为此读取整张表。**部分索引（partial index）**只保存符合其 where 子句的行：

create index events_failed_deploys_idx on events (created_at)
  where kind = 'deploy' and payload->>'status' = 'failed';

现在只需读取 11 个页。这个索引只有 2,768 KB，而覆盖所有行的 (created_at) 索引有 43 MB，因此它能常驻缓存，不符合条件的插入也完全不会触碰它。队列和软删除是典型用途。

有一个陷阱：规划器必须在规划时证明，你的 where 条件能推出索引的条件。把谓词中的常量写成字面量。 如果 ORM 把它们变成参数，通用计划（generic plan）就可能忽略这个索引。

set plan_cache_mode = force_generic_plan;
prepare q(text) as
  select id from events
  where kind = 'deploy' and payload->>'status' = $1
  order by created_at desc limit 20;
explain (costs off) execute q('failed');

 Limit
   ->  Index Scan Backward using events_created_at_idx on events
         Filter: ((kind = 'deploy'::text) AND ((payload ->> 'status'::text) = $1))

select lab.prove('(created_at) on all rows is 43 MB; the partial one 2,768 kB',
  pg_size_pretty(pg_relation_size('events_created_at_idx')) = '43 MB'
  and pg_size_pretty(pg_relation_size('events_failed_deploys_idx')) = '2768 kB');

索引只存储你交给它的值

索引保存的是被索引的值，而不是函数处理后的结果。给列套上一层函数，索引就看不见它了：where lower(email) = 'user4242@example.com' 读取了 users 的全部 1,126 个页。给这个表达式建索引：

create index users_lower_email_idx on users (lower(email));

现在只读取 4 个页。查询必须使用相同的表达式，写法也要相同；之后运行 analyze users，让规划器取得这个表达式的统计信息。

把它设为唯一索引，就能强制执行普通约束无法表达的规则：

create unique index users_lower_email_key on users (lower(email));

现在，USER4242@example.com 会因与 user4242@example.com 重复而被拒绝。唯一索引本来就能服务查询，所以绝不要“为了性能”，在同一组列上再建一个非唯一索引。

select lab.prove('USER4242@example.com is rejected: duplicate key value violates unique constraint "users_lower_email_key"',
  (select state = '23505'
      and msg = 'duplicate key value violates unique constraint "users_lower_email_key"'
   from caught where k = 'unique'));

select lab.prove('created_at::date on a timestamptz cannot be indexed: functions in index expression must be marked IMMUTABLE',
  (select state = '42P17' and msg = 'functions in index expression must be marked IMMUTABLE'
   from caught where k = 'immutable'));

去重：重复的键只存一次（PostgreSQL 13+）

project_id 上的索引是 14 MB。主键索引同样针对这些行、同样使用 bigint，却有 43 MB。区别在于去重（deduplication）：Postgres 只把重复的键存一次，后面跟上具有这个键的行的列表，这能把外键和状态列上的索引缩小到原来的三分之一左右。

更小不代表有用。kind 的五个值，每个都至少匹配表中八分之一的行，所以这些行几乎散布在每一页上。仅在 kind 上建索引后，查询 kind = 'alert' 读取的页甚至比顺序扫描更多。只有少数几个取值的列，应该放在多列索引或部分索引中，绝不要单独建索引。

           index           | avg_items | avg_item_bytes
---------------------------+-----------+----------------
 events_project_id_idx     |        13 |            571
 events_project_id_nodedup |       367 |             16

select lab.prove('deduplication makes low-cardinality indexes about three times smaller',
  pg_relation_size('events_project_id_nodedup')::numeric / pg_relation_size('events_project_id_idx') between 2.8 and 3.4
  and pg_relation_size('events_kind_nodedup')::numeric / pg_relation_size('events_kind_idx') between 2.8 and 3.6);

select lab.prove('so it reads more pages than a sequential scan would',
  lab.buffers($$ select * from events where kind = 'alert' $$) > 35173);

每个索引都在向写入收税

每个索引都会让某些读取更快，让每次写入更慢，而且一直如此。我们把同样的 200,000 个事件插入了三次，每次增加一些索引：

四个普通二级索引让同一次插入的缓冲区访问次数变成约四倍，WAL 量超过两倍（先记日志，再写数据）。

更新也要付费：不改变任何索引列、且新版本能放在原页上的更新是 HOT 更新，会跳过所有索引；其他更新都会向每个索引添加一个条目（冷更新会为每个索引付出代价）。

create table events_w (like events including defaults);
explain (analyze, buffers, wal, costs off)
insert into events_w select * from events where id <= 200000;
-- run 2: alter table events_w add primary key (id);
-- run 3: plus (project_id, created_at), (account_id, created_at),
--        (user_id), (created_at)

-- tax holds (k, buffers, wal) from lab.plan() of each insert
select lab.prove('four secondary indexes made the insert touch about four times as many buffers',
  (select a.buffers::numeric / b.buffers between 3.5 and 5 from tax a, tax b where a.k = 'pk+4' and b.k = 'pk'));

select lab.prove('and more than doubled its WAL',
  (select a.wal / b.wal > 2 from tax a, tax b where a.k = 'pk+4' and b.k = 'pk'));

idx_scan 为零只是疑点，不能据此定案

添加索引只需一行代码，却从来没人删除索引。pg_stat_user_indexes 统计每个索引的扫描次数，因此 idx_scan 为零的索引值得怀疑。在删除它之前：

• 检查计数器已运行多久（stats_reset，见 pg_stat_database）。月末报表用的索引，有 29 天看起来都没人用。PostgreSQL 16+ 的 last_idx_scan 会显示每个索引上次使用的时间，比重置日期更容易判断。
• 检查每个副本。 计数器按服务器独立统计；主库上闲置的索引，可能在每个副本上都承担着重任。
• 不要动唯一索引和主键索引。 它们负责强制执行约束。
• 用 drop index concurrently 删除（变更模式，服务照常），并把 create index 语句留在手边。

重复索引就没那么难判断了。有人为外键添加 (project_id)，后来又有人为仪表板添加 (project_id, created_at)，第一个索引现在就只剩写入成本了：较长索引可以服务较短索引所能服务的每一种查找。

select s.relname as table_name, s.indexrelname as index_name, s.idx_scan,
       pg_size_pretty(pg_relation_size(s.indexrelid)) as size
from pg_stat_user_indexes s
join pg_index i on i.indexrelid = s.indexrelid
where s.idx_scan = 0 and not i.indisunique and not i.indisprimary
order by pg_relation_size(s.indexrelid) desc;

 table_name |       index_name       | idx_scan | size
------------+------------------------+----------+-------
 events     | events_created_at_idx  |        0 | 43 MB
 events     | events_project_id_idx2 |        0 | 14 MB

select a.indrelid::regclass   as table_name,
       a.indexrelid::regclass as redundant,
       b.indexrelid::regclass as covered_by
from pg_index a
join pg_index b
  on b.indrelid = a.indrelid
 and b.indexrelid <> a.indexrelid
 and b.indnkeyatts >= a.indnkeyatts
 and (b.indkey::text || ' ') like (a.indkey::text || ' %')
where not a.indisunique
  and a.indnatts = a.indnkeyatts
  and a.indpred is null and b.indpred is null
  and a.indexprs is null and b.indexprs is null
  and (a.indkey::text <> b.indkey::text or a.indexrelid > b.indexrelid)
order by 2, 3;

 table_name |       redundant        |         covered_by
------------+------------------------+----------------------------
 events     | events_project_id_idx  | events_project_created_idx
 events     | events_project_id_idx2 | events_project_id_idx
 events     | events_project_id_idx2 | events_project_created_idx

select lab.prove('events_created_at_idx shows up too: EXPLAIN without ANALYZE never counts as a scan',
  (select idx_scan = 0 from pg_stat_user_indexes where indexrelname = 'events_created_at_idx'));

从查询出发设计索引，而不是从列出发

1. 从查询出发，而不是从列出发。 从 pg_stat_statements 获取真实 SQL（从 pg_stat_statements 开始），记下它的计划访问了多少页。
2. 等值列放在前面，然后放一列用于范围查询或 order by，让索引完成排序。
3. 针对固定的数据子集，考虑部分索引；只有非常热门的查询才考虑 INCLUDE。
4. 检查已有索引中，哪些会因新索引而变得冗余。
5. 用 create index concurrently 建立索引（根据表的流量选择索引构建方式），并比较页数。没有减少一个数量级？决定保留它之前，先弄清原因。

本章要点

• 一次查找的成本，是树的深度（3 或 4 个页），加上每个匹配行对应的一个堆页。
• 为问题建索引：先等值列，再放一个范围或排序列。错误的顺序会把 14 个页变成 643 个页。
• 仅索引扫描需要及时更新的可见性映射。关注 Heap Fetches。
• 部分索引小而便宜；把它的谓词写成字面量。
• 绝不要为只有少数几个取值的列单独建索引。
• 每个索引都向每次写入收税：多加四个索引，插入的缓冲区访问次数就变成四倍。
• 在足够长的时间窗口内，在每个副本上审查 idx_scan = 0。

延伸阅读

• Indexes，PostgreSQL 文档。官方章节，涵盖多列索引、仅索引扫描、部分索引和表达式索引。
• B-Tree Indexes: implementation，PostgreSQL 文档。结构、去重和自底向上删除。
• src/backend/access/nbtree/README，PostgreSQL 源码。由实现者介绍右向链接、高键和页删除。
• Efficient Locking for Concurrent Operations on B-Trees，Philip L. Lehman 和 S. Bing Yao，ACM TODS，1981。Postgres 兄弟节点链接背后的 B-link 树。
• PostgreSQL 18 release notes，PostgreSQL。跳跃扫描和新增的 Index Searches 行。
• Anatomy of an SQL Index，Markus Winand。对叶页链和树深度最清晰的思维模型。