Ryu

large picture of the cover

索引内核篇 —— 寻找的艺术

索引内核篇 —— 寻找的艺术

摘要

如果数据库是一本厚书，表空间是纸张，那么索引就是目录。但这个目录的设计极其考究——它必须在数据量达到千万级时，依然保证只需要 2-3 次磁盘 I/O 就能定位到任意一行。

很多开发者背诵了“索引失效的 10 种场景”，却依然写不出高性能 SQL。本章我们将抛弃死记硬背，从 B+ 树的物理形态、磁盘 I/O 的特性以及优化器的成本模型出发，推导出索引设计的所有“潜规则”。

3.1 核心矛盾：I/O 的降维打击

1. 16KB 的物理限制

在第二章中我们剖析过，InnoDB 与磁盘交互的最小单位是 Page（页），默认 16KB。

  • 没有索引时：查找 WHERE id = 1000w，数据库必须从头扫描所有页（Full Table Scan）。如果是 1000 万行数据（约 10GB），机械硬盘可能需要读取几分钟。
  • 目标：我们需要一种数据结构，能将这“几分钟”的随机搜索，降低到“几毫秒”的精确打击。

2. 演进哲学：为什么是 B+ 树？

在计算机科学中，查找算法有很多，为什么 MySQL 独宠 B+ 树？

  • Hash 表：查找 O(1)，极快。但它不支持范围查询（> 100）和排序。只有在精确等值查询（如 Redis）中才是王者。
  • 二叉平衡树 / 红黑树：查找 O(\log N)。
    • 痛点：红黑树每个节点只存一个数。1000 万数据，树高可能达到 20 层以上。
    • 物理代价：每一层都可能是一次磁盘 I/O。20 次随机 I/O 意味着查询延迟高达 200ms，这是不可接受的。

B+ 树的胜利：矮胖的艺术
B+ 树是为了适应磁盘特性而生的。它的核心思想是：把树压扁，让每个节点变得很宽（存很多索引键），从而减少 I/O 次数。

  • 非叶子节点：只存索引键（Key）和指针，不存数据。一个 16KB 的页，如果主键是 BIGINT (8字节) 加指针 (6字节)，大概能存 1170 个索引项。
  • 叶子节点：存所有数据，且通过双向链表连接（这是范围查询的神器）。

🔢 硬核推算：3 层能存多少数据？

  • Layer 1：1 个节点，1170 个指针。
  • Layer 2：1170 个节点，约 137 万个指针。
  • Layer 3（叶子）：137 万个节点。假设每行数据 1KB，每页存 16 行。
  • 总容量：137万 \times 16 \approx 2190 万行。
  • 结论：2000 万行数据，B+ 树的高度只有 3。 这意味着只需要 3 次 I/O（如果根节点在内存，甚至只需 2 次）就能找到目标。

3.2 数据的物理位置：聚簇与二级索引

理解索引，必须理解数据真正“住”在哪里。

1. 聚簇索引（Clustered Index）—— “我就是数据”

在 InnoDB 中，表即索引，索引即表。

  • 主键索引的叶子节点，存储的是完整的行数据。
  • 这解释了为什么主键查询最快——找到索引就找到了数据。

2. 二级索引（Secondary Index）—— “我是路标”

  • 普通索引（如 name）的叶子节点，存储的是 name 的值 + 主键 ID。

3. 致命的回表（Key Lookup）

当你执行 SELECT * FROM user WHERE name = 'Alice'：

  1. Index Seek：在 name B+ 树中找到 id = 5。
  2. Row Lookup：跳回 聚簇索引树，用 id = 5 找到完整数据。
  • 代价：步骤 2 往往是随机 I/O。如果匹配的数据量很大，磁头会在磁盘上疯狂跳跃。这是慢查询的万恶之源。

3.3 压榨极限：MySQL 的黑科技优化

为了减少 I/O 和层级间交互，MySQL 引入了多种机制来压榨硬件性能。

1. 覆盖索引（Covering Index）—— 消灭回表

如果业务只需要 SELECT id, name FROM user WHERE name = 'Alice'。
因为 name 索引树的叶子节点里已经有了 name 和 id，MySQL 会直接返回结果，不再去查聚簇索引。

  • 实战原则：永远不要无脑 SELECT *，只查需要的列，能利用覆盖索引是性能飞跃的关键。

2. MRR (Multi-Range Read) —— 随机转顺序

场景：SELECT * FROM user WHERE age BETWEEN 20 AND 30; 查出一堆 ID：10, 500, 3, 8...

  • 未优化：直接回表，磁头乱跳（随机读）。
  • MRR 优化：
    1. 先在内存（Read_rnd_buffer）中把 ID 排序（3, 8, 10, 500...）。
    2. 然后按顺序去聚簇索引查。
  • 哲学：利用内存的排序成本（CPU 快），换取磁盘的顺序 I/O 收益（I/O 慢）。

3. ICP (Index Condition Pushdown) —— 门卫拦截

场景：联合索引 (name, age)，查询 WHERE name LIKE 'Li%' AND age = 10。

  • 未优化（5.6前）：引擎层只负责找 Li% 的人，全把数据拿回 Server 层，Server 层再检查 age=10。这导致大量无用回表。
  • ICP 优化：Server 层把 age = 10 这个条件下推给引擎。引擎在遍历索引时，如果发现 age 不对，直接跳过，连表都不回。
  • 效果：Explain 的 Extra 字段显示 Using index condition。

3.4 索引的代价：维护与写损耗

索引不是免费的午餐，它是读的蜜糖，写的砒霜。

1. 写缓冲（Change Buffer）—— 写性能的救星

当 INSERT/UPDATE 一个非唯一二级索引时，如果目标页不在内存中：

  • 常规：读入页 -> 修改（1次随机读 + 1次内存写）。
  • 优化：直接在内存的 Change Buffer 记录修改，不读磁盘。等下次该页被读取时，再合并（Merge）。
  • 为什么唯一索引不行？ 因为必须把页读进来校验唯一性，无法“盲写”。

2. 页分裂（Page Split）—— UUID 的诅咒

为什么严禁使用随机 UUID 做主键？

  • 自增 ID：数据是追加写入，页写满了开新页（顺序写）。
  • UUID：数据是乱序插入。新数据可能插入到已经满的页中间。
    • 后果：InnoDB 必须把页分裂成两个，产生大量磁盘碎片，且导致 IOPS 飙升。

3. 统计信息（Cardinality）—— 优化器的直觉

MySQL 为什么有时候不走索引？因为它觉得走索引更慢。它是怎么知道的？

  • 采样：InnoDB 随机抽取少量页，统计不同值的数量（Cardinality）。
  • 陷阱：因为是采样，所以可能不准。如果发现选错索引，试着执行 ANALYZE TABLE 修正统计信息。

3.5 崩塌的瞬间：索引失效的物理本质

别再死记硬背“失效口诀”。所有的失效，本质上只有两个物理原因。

原因一：有序性被破坏 (Broken Order)

B+ 树依赖二分查找，前提是数据严格有序。

  1. 函数与计算
    • WHERE YEAR(create_time) = 2024。B+ 树按时间排序，不按年份排序。计算导致变成“黑盒”。
  2. 隐式类型转换
    • phone 是 VARCHAR，查询 WHERE phone = 138000。
    • MySQL 会把字符串转数字：CAST(phone AS UNSIGNED)。这是隐式函数运算，破坏有序性。
  3. 最左前缀的“断桥”
    • 索引 (a, b, c)，查询 WHERE b = 1。
    • 联合索引就像“省-市-区”。跳过省直接找市，在全局上是无序的。

原因二：回表成本过高 (Cost Model)

场景：SELECT * FROM order WHERE price > 10。
即使 price 有索引，如果表中 50% 的数据都大于 10，MySQL 依然会选择全表扫描。

  • 为什么？
    • 全表扫描 = 顺序 I/O（快）。
    • 走索引 + 回表 = 索引 I/O + 大量随机 I/O（慢）。
  • 临界点：通常当访问数据量超过总量的 20%-30% 时，优化器会放弃二级索引。

3.6 决胜 SQL：实战优化手册

1. 硬核技能：key_len 精确计算

面试必杀技：如何确定联合索引 (a, b, c) 到底用到了哪几列？看 Explain 的 key_len。

公式（utf8mb4）：INT=4, VARCHAR(n)=n \times 4 + 2, NULL=+1。

案例：索引 idx_a_b (a INT, b INT NULL)。

  • WHERE a=1 \rightarrow key_len = 4。
  • WHERE a=1 AND b=1 \rightarrow key_len = 4 + (4+1) = 9。
  • 结论：通过字节数，你可以像手术刀一样精准判断索引覆盖范围。

2. 场景化优化：深分页 (Deep Paging)

痛点：LIMIT 1000000, 10。MySQL 会查出 1000010 条记录的主键，回表 1000010 次，丢弃前 100 万条。

优化：延迟关联 (Late Row Lookup)
利用覆盖索引先把 ID 查出来，再回表。

SELECT t1.* FROM table t1
JOIN (
    SELECT id FROM table WHERE type=1 LIMIT 1000000, 10
) t2 ON t1.id = t2.id;
  • 原理：子查询只查 ID（走覆盖索引，不回表，极快），外层只回表 10 次。

3. 场景化优化：前缀索引

痛点：给 email (VARCHAR 255) 建索引太占空间。 优化：CREATE INDEX idx_email ON user(email(10));

  • 技巧：计算 COUNT(DISTINCT LEFT(email, N)) / COUNT(*)，找到区分度接近 1 的最小 N 值。

3.7 未来的索引：MySQL 8.0 新特性

  • 函数索引 (Functional Index)：

    • 真正解决 YEAR(create_time) 失效问题。MySQL 底层自动维护虚拟列索引。

  • 降序索引 (Descending Index)：

    • ORDER BY a DESC, b ASC 不再需要文件排序（Filesort），真正利用物理降序结构。

site logo

Hi,Ryu

© 2026 Ryu