跳转到内容
← 返回核心概念
系统与架构计算机科学 · 数据库约 16 分钟阅读

数据库索引与查询优化

Database Indexing and Query Optimization

一张存储了 10 亿行用户数据的表，每行包含用户 ID、姓名、邮箱、注册时间等字段。你执行一条查询： sql

数据库索引查询优化B树

一张存储了 10 亿行用户数据的表，每行包含用户 ID、姓名、邮箱、注册时间等字段。你执行一条查询：

sql
SELECT * FROM users WHERE email = 'alice@example.com';
```

没有索引：数据库必须逐行扫描所有 10 亿行，找出匹配的记录——这需要几十分钟甚至几个小时。有了合适的索引：查询在几毫秒内完成。

这就是索引的作用。索引是数据库性能工程的核心，也是理解大规模数据系统的关键。

破除误解：索引越多越好

初学者往往认为索引只有好处没有坏处——查询快了，何乐而不为？实际上，索引有明确的代价：

  • 写操作变慢：插入、更新、删除时，所有相关索引都要同步更新
  • 存储空间：索引本身需要额外磁盘空间（有时与原表相当甚至更大）
  • 内存占用：频繁使用的索引被缓存在内存中

读多写少的场景（如数据分析、搜索）：索引收益大，应该建。写多读少的场景（如日志写入、事件流）：索引代价大，应该谨慎。索引设计是权衡，不是多多益善。

B 树：数据库索引的主力

B+ 树（B-Plus Tree）是关系数据库（MySQL InnoDB、PostgreSQL）索引的标准数据结构。

它的来历比多数人想象的要早。B 树由 Rudolf Bayer 与 Edward McCreight 在 1972 年的论文《Organization and Maintenance of Large Ordered Indexes》中提出，发表于《Acta Informatica》创刊卷。半个多世纪过去，它和它的变体 B+ 树仍是几乎所有关系数据库索引的默认结构。

B+ 树是一种平衡多路搜索树： - 所有叶子节点在同一层（平衡） - 所有实际数据只存在叶子节点（B+ 树特点，B 树内节点也存数据） - 叶子节点之间用链表串联（支持范围查询） - 每个节点可以有多个子节点（减少树的高度，适合磁盘块存储）

对于 10 亿行数据，4 阶 B+ 树高度约为 log⁡4109≈15\log_4 10^9 \approx 15。最坏情况下，查询只需要 15 次磁盘 I/O——而全表扫描需要读取所有磁盘块。

为什么不用红黑树（每个节点 2 个子节点）？

红黑树对 10 亿行数据深度约 log⁡2109≈30\log_2 10^9 \approx 30，与 B+ 树相比没有决定性差距。但 B+ 树每个节点可以存储一个磁盘页（通常 4KB 或 16KB）的数据——一次磁盘读取可以加载几百个键。磁盘 I/O 的时间（毫秒级）远超 CPU 计算（纳秒级），所以减少 I/O 次数才是关键。

上面用 4 阶只是为了和红黑树对比，真实的 B+ 树扇出（fanout，一个节点的子节点数）要大得多。InnoDB 默认页 16KB、PostgreSQL 默认页 8KB，一个内部节点能放下几百个键（PostgreSQL 一个 8KB 页常容纳约 200 到 400 个索引项）。

扇出几百，意味着 10 亿行的 B+ 树通常只有 3 到 4 层。所以一次点查只要 3 到 4 次页访问，而且最上面一两层几乎总是常驻内存缓存，真正落到磁盘的往往只剩一两次——这才是 B+ 树相对二叉树的真正威力。

索引类型

聚集索引（Clustered Index）：数据行按索引键顺序物理存储。一张表只能有一个聚集索引（MySQL InnoDB 的主键即聚集索引）。范围查询极快，因为相邻键的数据物理相邻。

非聚集索引（Non-Clustered Index / Secondary Index）：索引与数据分开存储，索引叶子节点存储的是指向实际数据行的指针（或主键值）。查询时先查索引，再"回表"查实际数据。

覆盖索引（Covering Index）：查询所需的所有列都在索引中，不需要回表。显著减少 I/O。

示例：

sql
-- 查询只需 email 和 name
SELECT name FROM users WHERE email = 'alice@example.com';

-- 在 (email, name) 上建覆盖索引，避免回表 CREATE INDEX idxemailname ON users(email, name); ```

复合索引（Composite Index）：多列组合的索引，遵循最左前缀原则：

sql
CREATE INDEX idx_city_age ON users(city, age);

-- 这些查询可以使用索引： SELECT * FROM users WHERE city = 'Beijing'; SELECT * FROM users WHERE city = 'Beijing' AND age > 18;

-- 这个查询不能用上面的索引（跳过了 city）： SELECT * FROM users WHERE age > 18; ```

哈希索引：基于哈希表，等值查询极快 $O(1)$，但不支持范围查询。MySQL Memory 引擎使用哈希索引，InnoDB 有自适应哈希索引（自动对频繁访问的 B+ 树节点建哈希缓存）。

查询优化器：决策者

你写 SQL 只是说"我想要什么"，查询优化器（Query Optimizer）决定"怎么去取"。这是数据库中最复杂的组件之一。

现代基于代价的优化器源自 IBM 的 System R 项目。Patricia Selinger 等人 1979 年的论文《Access Path Selection in a Relational Database Management System》首次系统地提出：用一个代价模型为每条查询挑选访问路径，并用动态规划把 JOIN 顺序的枚举规模从 $n!$ 压到可接受的范围。今天 MySQL、PostgreSQL、Oracle 的优化器骨架，仍沿用这套四十多年前的思路。

优化器的主要工作：

1. 解析与重写：把 SQL 转化为逻辑查询计划（关系代数表达式），应用等价变换规则（如谓词下推、列裁剪）。

2. 代价估算：估计不同执行方案的代价（CPU 时间 + I/O 次数）。代价估算依赖统计信息（Statistics）：表行数、列值分布（直方图）、索引选择性。统计信息不准确会导致优化器做出错误决策。

3. 计划选择：搜索执行计划空间，找到代价最低的计划。对于涉及多个表的 JOIN，可能的执行顺序有 $n!$ 种（$n$ 是表的数量），枚举所有组合代价不可接受，实际使用启发式搜索（贪心、动态规划）。

常见执行算子：

算子适用场景
全表扫描（Seq Scan）无合适索引，或表很小
索引扫描（Index Scan）选择性高的条件（返回少量行）
索引范围扫描范围条件（BETWEEN、>、<）
位图堆扫描（Bitmap Heap Scan）多个索引组合（PostgreSQL）
嵌套循环连接（Nested Loop Join）小表驱动大表，有索引
哈希连接（Hash Join）大表连接，无排序
归并连接（Sort-Merge Join）已排序数据

EXPLAIN：理解执行计划

在 SQL 前加 EXPLAIN，查看查询优化器选择的执行计划：

sql
EXPLAIN SELECT * FROM users WHERE email = 'alice@example.com';
```

输出会显示每一步用了什么索引、预计扫描多少行、各步骤代价。EXPLAIN ANALYZE 实际执行查询，显示真实的执行统计，是性能调优的最重要工具。

慢查询的常见原因

  • 未使用索引：条件列没有索引，或索引被函数/表达式使该列失效（如 WHERE YEAR(created_at) = 2024 无法用 created_at 上的 B+ 树索引）
  • 隐式类型转换：列是字符串类型却用数字去比较（如 phone 是 VARCHAR，却写 WHERE phone = 13800138000），数据库会对整列做类型转换，等同于给列套了函数，索引照样失效——这是最隐蔽、也最常被忽视的一种
  • 索引选择性低：性别字段（只有"男"/"女"）上的索引几乎没用，优化器可能选择全表扫描
  • 回表代价高：非聚集索引查询返回大量行时，大量随机 I/O 回表比全表扫描更慢
  • JOIN 笛卡尔积：忘记 JOIN 条件导致结果集爆炸
  • N+1 查询问题：对 N 个对象各发一次查询，应该用一次 JOIN 或 IN 子句

代价与争议

统计信息与实际分布的偏差：优化器依赖统计信息，但统计信息更新有延迟，数据分布倾斜（Skew）时直方图可能失效。错误的代价估计导致次优的执行计划，而 DBA 往往很难诊断原因。

这不只是工程上的抱怨，而有实证支撑。2015 年 Viktor Leis 等人的论文《How Good Are Query Optimizers, Really?》用一套专门设计的连接顺序基准（Join Order Benchmark）做了拆解实验，结论相当尖锐：基数估计（cardinality estimation，即预测每一步中间结果有多少行）才是糟糕计划的主因，代价模型和计划枚举的影响相对小得多；而且基数估计的误差会随参与连接的表增多而成倍放大。换句话说，优化器最薄弱的环节不是"怎么搜"，而是"估得准不准"。

学习型查询优化器：传统优化器是基于规则和统计模型的——用机器学习代替传统统计估计，预测更准确的代价。这是活跃的研究方向（Neo、Bao 等系统），但生产部署仍以传统方法为主。

云原生数据库的变化：Aurora、Spanner 等云数据库将存储与计算分离、多副本、Serverless——这些架构变化使传统的 B+ 树假设（磁盘 I/O 是瓶颈）不再完全适用，新的索引结构（LSM 树、ALEX 学习型索引）正在崛起。

写优化结构的崛起：B+ 树是为"就地更新"设计的，随机写较多。日志结构合并树（LSM-Tree，由 O'Neil 等人 1996 年提出）换了个思路：写入先攒在内存的有序结构里，再批量顺序刷到磁盘，后台逐层合并，把昂贵的随机写变成廉价的顺序写。代价是一次读取可能要查多个层级（读放大），后台合并又带来写放大。RocksDB、Cassandra、HBase 以及 MySQL 的 MyRocks 引擎都建立在 LSM 之上，专门服务写密集场景。这恰好印证了开头那条权衡：没有"最好的索引"，只有"对这种读写比例最好的索引"。

跨域连接

  • 存储引擎：索引结构的选择先于优化器。就地更新的树读路径短而可预测，追加合并的结构写吞吐高却要查多层，于是同一条查询在两种引擎上的最优计划并不相同——"最好的索引"只对某个读写比例成立。推论是：换引擎等于换掉整套代价假设，原来的索引设计不一定还成立。
  • 统计学：基数估计是用直方图与抽样去猜中间结果有多少行，而多表连接时误差会相乘而非相加。可检验推论：优化器最薄弱的一环是估计而非搜索，改进枚举算法收益有限，误差会随参与连接的表增多成倍放大。这也意味着统计信息过期造成的伤害，往往比少建一个索引更严重。
  • 集合预报与决策：气象学早已放弃单一点估计，改用一组成员刻画不确定性再据分布决策。查询优化器却仍靠一个点估计选定计划，估错就满盘皆输——这正是运行时反馈与自适应执行成为当前方向的原因。
  • 语义学：声明式查询要求语义与求值策略解耦：说清"要什么"，把"怎么取"留给引擎。可检验推论：一旦某个构造的结果依赖求值顺序，优化器就失去重写自由——所谓"这条语句优化不了"，往往是语义先出了问题。同理，把逻辑塞进标量函数或触发器，等于亲手取消了优化器的重写空间。
  • 临床诊断：执行计划相当于检查报告：先看引擎实际选了什么路径、估了多少行，再判断是估计偏了、索引失效还是回表太贵。不看计划直接加索引，与不做检查直接开药同理——指标或许改善，病因并未触及。推论是：性能问题的第一手证据是实际执行统计，而不是预估行数。

参考文献

  • Bayer, R. & McCreight, E. "Organization and Maintenance of Large Ordered Indexes." Acta Informatica, vol. 1, no. 3 (1972): 173–189.
  • Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A. & Price, T. G. "Access Path Selection in a Relational Database Management System." Proc. ACM SIGMOD, 1979: 23–34.
  • O'Neil, P., Cheng, E., Gawlick, D. & O'Neil, E. "The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica, vol. 33, no. 4 (1996): 351–385.
  • Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A. & Neumann, T. "How Good Are Query Optimizers, Really?" Proc. VLDB Endowment (PVLDB), vol. 9, no. 3 (2015): 204–215.
  • Kraska, T., Beutel, A., Chi, E. H., Dean, J. & Polyzotis, N. "The Case for Learned Index Structures." Proc. ACM SIGMOD, 2018.
  • Marcus, R., Negi, P., Mao, H., Tatbul, N., Alizadeh, M. & Kraska, T. "Bao: Making Learned Query Optimization Practical." Proc. ACM SIGMOD, 2021: 1275–1288.
  • Ramakrishnan, R. & Gehrke, J. Database Management Systems. 3rd ed. McGraw-Hill, 2002.
  • Mohan, C. et al. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS, 1992.
  • Graefe, G. Modern B-tree Techniques. Foundations and Trends in Databases, 2011.

延伸阅读

  • Use The Index, Luke. use-the-index-luke.com （实用数据库索引指南，免费在线）

正文中引用本条 · 4