卷 V · 计划CH 21深度 21/24

索引：把顺扫变成一次跳跃

「加个索引快了一千倍」的传说，背后是一个朴素的数据结构：B-tree。它像字典的边缘标签，让你不用一页页翻，几步就跳到目标。这一章讲清它怎么做到，也讲清 PostgreSQL 那些 B-tree 之外的特种索引——以及索引不是免费的。

B-treeGIN/GiST/BRIN部分/表达式索引代价

没有索引：只能一页页翻

一张表在磁盘上是一堆数据页（每页 8KB，装若干行）。要找 customer_id = 2753 的行，没有索引时，数据库只能顺扫——从第一页翻到最后一页，逐行比对。表有多少页，就得读多少页。这是 O(n)。

索引是另建的一个数据结构，专门为「快速定位」服务。最常用的是 B-tree（平衡多叉树）：它把被索引列的值排好序、组织成一棵矮而宽的树，让你从根节点开始，几次比较就能下钻到目标值、拿到它对应的行在堆里的位置。

▶ 动手 · B-tree 下钻 vs 全表顺扫

下面这台真引擎里有一张 4096 行、每页 64 行 = 共 64 页的表。切换「无索引」和「有 B-tree 索引」，看要找一个值时，两种方式各读了多少页。

对比一目了然：顺扫要读整整 64 页（几乎读遍全表才碰到目标）；B-tree 只需 3 层下钻 + 1 页数据 = 4 次读就定位到行。64 对 4，而且表越大差距越夸张——B-tree 的读取次数是 O(log n)，表翻一千倍，读取次数只多几次。这就是「加个索引快一千倍」的真相：把线性的翻页，换成了对数的下钻。

B-tree 不只管等值，还管范围和排序

因为 B-tree 是有序的，它不止能加速 =，还能加速：

  • 范围：WHERE price BETWEEN 20 AND 50——定位到 20，顺着有序叶子扫到 50。
  • 排序：ORDER BY price——索引本身就是排好序的，直接按序读，省掉一次排序。
  • 前缀匹配：WHERE name LIKE 'Ann%'（右边通配）能走索引；但 LIKE '%son'（左边通配）不能——因为 B-tree 按开头排序，不知道「以 son 结尾」的散落在哪。

这也是主键、唯一约束自动建的那种索引。日常九成的索引需求，B-tree 全包了。

让 B-tree 更聪明的三招

PostgreSQL 的索引能玩出花，几个高价值的变体：

  • 多列索引：CREATE INDEX ON orders (customer_id, ordered_at)。列的顺序要紧——它能加速「按 customer_id」和「按 customer_id 再按 ordered_at」的查询，但单独「按 ordered_at」用不上（像电话簿按姓再按名排，只知道名字没法查）。
  • 表达式索引：想让 WHERE lower(email) = '...' 走索引，得给表达式本身建索引：CREATE INDEX ON users (lower(email))。否则列上有索引也没用——因为你查的是 lower(email)，不是 email。
  • 部分索引：只给一部分行建索引：CREATE INDEX ON orders (id) WHERE status = 'pending'。如果你几乎总是查未完成订单，这个索引又小又快，还不用维护那些永远查不到的已完成行。这是 PostgreSQL 一件很趁手的兵器。

还有覆盖索引（INCLUDE）：把查询要的列一并塞进索引，让数据库只读索引就够、不用回堆（Index Only Scan），进一步省 I/O。

◆ B-tree 之外：GIN / GiST / BRIN 各管一摊

PostgreSQL 有一整套特种索引，专治 B-tree 搞不定的场景——这是它相对多数数据库的一大优势：

  • GIN（倒排索引）：一行里有多个可搜索小项时用——全文搜索（一篇文章里的每个词）、JSONB（@> 包含，第 14 章）、数组（第 13 章）。
  • GiST：几何 / 空间数据（PostGIS 靠它）、范围类型的重叠查询、最近邻搜索（「离我最近的 10 家店」）。第 12 章的 EXCLUDE 防重叠也靠它。
  • BRIN（块范围索引）：给超大、且物理上天然有序的表用（比如按时间递增追加的日志表）。它只记「每一段数据块的最小 / 最大值」，索引极小，用一点点空间换范围查询的加速。

选对索引类型，是让某类查询从「跑不动」变「秒回」的关键。

⚠ 索引不是免费的

别见列就加索引。每个索引都有代价：

  • 占空间：索引是额外的数据结构，大表的索引可能和表本身一样大。
  • 拖慢写入：每次 INSERT / UPDATE / DELETE，所有相关索引都要跟着维护。一张表 8 个索引，一次写入就是 9 处改动。
  • 和 MVCC 叠加：回到卷 IV——UPDATE 产生新版本，索引也要指向新版本、给旧的留死条目，于是索引也会膨胀、也要 VACUUM 清理。

所以索引是用「写变慢、占空间」换「读变快」的交易。读多写少的字段值得加；写极频繁、或几乎不按它查的字段，加了是负担。照着真实的慢查询（用 EXPLAIN 确认）去加，别凭感觉。

⇄ 对照 MySQL
  • B-tree、多列索引、覆盖索引：两家都有，基本概念和「最左前缀」规则相通，这份直觉可以直接搬。
  • 特种索引：GIN / GiST / BRIN / SP-GiST 是 PostgreSQL 的显著优势。MySQL 的对应能力零散——全文有 FULLTEXT 索引、空间有 SPATIAL（R-tree），但没有 PG 这样统一、可扩展、覆盖 JSONB / 数组 / 范围的一整套体系。
  • 部分索引：PostgreSQL 原生支持 WHERE 条件的部分索引；MySQL 没有（它的「prefix index」是「只索引字符串前 N 个字符」，是另一回事，别混淆）。
  • 表达式索引：MySQL 8.0.13 起支持函数索引，之前只能靠生成列绕；PostgreSQL 一直有。

这一章的一句话

B-tree 把 O(n) 的顺扫（64 页）变成 O(log n) 的下钻（3 层 + 1 页），还顺带管范围和排序；部分 / 表达式 / 覆盖索引让它更聪明，GIN/GiST/BRIN 覆盖 B-tree 管不了的全文、JSONB、空间、超大有序表——但索引拖慢写入、占空间，要照着真实慢查询去加。

索引、统计、选择性——这些拼图凑齐了。卷 V 的最后一章，我们把它们串成实战：怎么让规划器持续做对选择，怎么读懂「它为什么不听我的」，以及几个真实世界的性能陷阱。