面试题：MySQL 为什么用 B+ 树而不是 B 树或跳表？联合索引的最左前缀怎么生效、回表与覆盖索引的代价怎么算、limit 100000, 20 这种深分页为什么慢、怎么优化到 O(1)？

这是「每日一题」专栏的第二十二篇。每天一道面试题，后端 + AI 混合路线，从原理到代码一次讲清。上一篇是 长上下文与 RoPE 长度外推，今天按轮换回到后端/分布式方向，兑现上一篇的预告：MySQL 索引与深分页。这题的面试杀伤力在于它「人人都会、人人答不满」——绝大多数人能说出「B+ 树矮、叶子有链表」，但一追问「三层的容量账怎么算」「最左前缀为什么断在范围列就没了」「延迟关联为什么还是 O(offset)」，就露馅了。

一、题目与考点拆解

面试官的原话通常是这样：

你们线上表几千万行，查一条按主键的记录很快。为什么 MySQL 的索引要用 B+ 树？用 B 树、跳表或者哈希行不行？联合索引 (a, b, c)，为什么 where b = ? 就用不上索引？我让它走索引了，EXPLAIN 里为什么还是慢？还有——分页翻到第一万页，limit 100000, 20 卡住好几秒，怎么优化？

这一题真正考的是五层，缺一层都算没答透：

1. 数据结构选型：哈希 / 跳表 / B 树 / B+ 树，各自的能力边界与为什么 B+ 树胜出。
2. 磁盘与页的物理约束：为什么树必须「矮胖」、一次 IO 的账怎么算、Buffer Pool 扮演什么角色。
3. InnoDB 的两棵树：聚簇索引与二级索引、回表的真实代价、自增主键背后的页分裂问题。
4. 联合索引的排序本质：最左前缀不是「规则」而是 B+ 树有序性的直接推论，等值列 / 范围列 / 排序列的排列原则。
5. 工程落地：覆盖索引、索引下推 ICP、索引失效清单，以及深分页从 O(offset) 到 O(1) 的三条路。

二、为什么是 B+ 树：四种结构的对决

2.1 哈希索引：只擅长一件事

哈希表等值查找是 O(1)，但它把 key 打散成无序的桶，于是：

• 不支持范围查询：where id > 1000、between ... and ... 全都退化成全表扫描。
• 不支持排序：order by 无法从哈希结构里直接得到有序输出。
• 不支持最左前缀：联合索引的「有序性红利」荡然无存。

所以 InnoDB 不允许用户显式创建哈希索引，只在内部提供了一个「自适应哈希索引（AHI）」：当它发现某些等值查询被高频访问时，自动为主键或二级索引的热点前缀建一份内存哈希，加速点查。这是优化器自己开的挂，不是你能拿来解决范围查询的工具。真正把哈希用于索引的是 Memory 引擎和 NDB——场景本来就是「等值点查」。

2.2 跳表：Redis 的宠儿，磁盘的敌人

跳表（skip list）用多级索引链表把查找压到 O(log n)，实现简单、并发友好，Redis 的 ZSet、LevelDB/RocksDB 的内存 MemTable 都靠它。那 MySQL 为什么不用？

关键在存储介质。跳表是「链表」，节点是散落在内存堆上的独立小块，靠指针跳转。在内存里这没问题（紧随其后的 memtable 都在 RAM 中），但放到磁盘上：

• 随机访问、没有局部性：每跳到下一个节点都是一次可能的随机 IO，磁盘最怕的就是随机读。
• 无法批量预读：一个 B+ 树节点是一整页 16KB，一次 IO 能把几百个 key 装进内存慢慢二分；而跳表一次只能拿一个节点。
• 层级靠概率（每层 1/2 概率上升），树高不稳定，最坏退化不可控。

一句话：跳表赢在内存里的实现复杂度，输在磁盘上的局部性。

2.3 B 树 vs B+ 树：差在「数据放哪」和「叶子连不连」

B 树每个节点都同时存 key 和 data。B+ 树做了两个关键改动：

对比点	B 树	B+ 树
数据存放	所有节点都存 key + data	只有叶子存数据，内部节点只存 key + 指针
单节点扇出	小（data 挤占了空间）	大（内部节点纯 key，能塞下多得多的指针）
树高	更高，IO 更多	更矮，通常 3 到 4 层
范围查询	要在树内中序回溯、跨层跳跃，不连续	叶子节点用双向链表串起来，顺序扫一段即可
查询稳定性	命中不同层，路径长度不一	所有查询都从根走到叶，路径等长，延迟稳定
增删影响	中间节点分裂要搬移 data	只在叶子层分裂，内部节点只改指针

两个改动带来的连锁好处：

1. 扇出大 → 树矮 → IO 少。内部节点不存 data，同样一页能放更多 key，于是树高压到 3 层左右，一次查询最多 3 到 4 次 IO。
2. 叶子有序且相连 → 范围与排序免费。order by id 只要顺着叶子链表走，天然有序；between 只要定位到起点再顺序扫。这是 B 树做不到的。

所以 B+ 树在「磁盘 + 范围查询 + 排序」这三个约束下是压倒性的最优解——它不是理论上最快的树，而是最贴合磁盘块 IO 和关系型查询模式的树。

三、磁盘与页：为什么树必须「矮胖」

理解 B+ 树，先算一笔 IO 的账。数量级要背下来：

机械硬盘 随机读：  约 8 ~ 10 ms   （寻道 4ms + 旋转 4ms + 传输）
SSD      随机读：  约 0.1 ms
内存访问：         约 100 ns

也就是说，一次磁盘随机 IO 比一次内存访问慢约 10 万倍。既然 IO 是瓶颈，索引结构优化的唯一目标就是：把一次查询所需的随机 IO 次数压到常数级（通常 3 次以内）。

对比一下同样存 1000 万个 key：

• 红黑树：二叉树高约 2·log₂(10⁷) ≈ 47 层 → 最坏 47 次随机 IO。每次 IO 只换回 1 个 key，性价比极低。
• B+ 树：三层，也就是 3 次 IO。

三层 B+ 树到底能装多少行？把 InnoDB 的页大小 16KB 代入算一遍（这是面试最爱的白板题）：

页大小              = 16 KB = 16384 B
扣掉页头/页尾/槽位  ≈ 剩 ~16250 B 可用

内部节点：
  key  = bigint 主键 8 B
  指针 = 页号 6 B
  单条  14 B  →  16250 / 14 ≈ 1160 个指针（扇出 ≈ 1160）

叶子节点（假设一行约 1KB）：
  16250 / 1024 ≈ 16 行

三层总容量 ≈ 1160 × 1160 × 16 ≈ 2150 万行

结论要脱口而出：一张两千万行的表，B+ 树只有 3 层，按主键查一条记录最多 3 次磁盘 IO；而且根节点和上两层内部节点几乎常驻 Buffer Pool（默认 128MB，生产一般开到物理内存的 50% 到 70%），实际第 1、2 次 IO 基本都在内存里完成，真正落盘的只有最后一次叶子页的读取。

这就是「矮胖」的威力：用节点内的二分（内存操作）换取树高的下降（磁盘 IO 的减少）。 页大小 16KB 本身是经验折中——太小则扇出小、树变高、IO 变多；太大则单页读写/预读粒度粗、浪费带宽、Buffer Pool 管理粒度也变粗。

四、InnoDB 的两棵树：聚簇索引与回表

4.1 聚簇索引：数据即索引

InnoDB 的主键索引就是聚簇索引（clustered index），叶子节点直接存整行数据。它决定了两件事：

• 表必须有主键。没有显式主键就找第一个「唯一且非空」的索引当主键，再没有就造一个隐藏的 6 字节 row_id。所以「表一定要有主键」不是规范洁癖，是存储引擎的硬约束。
• 自增主键不只是习惯。如果用 UUID 这类随机值当主键，插入位置随机 → 频繁页分裂：新数据插到已满页中间，要把一半记录搬到新页，还留下页内空洞和树碎片，写放大严重。而自增主键总是追加到最右叶子，顺序写、几乎不分裂。这是「为什么用自增 bigint 主键」的物理原因。

4.2 二级索引与回表：每个查询可能变成两次查找

二级索引（普通索引、唯一索引）的叶子节点存的是「索引列的值 + 主键值」。注意，存的是主键值，不是行物理地址。为什么？因为页分裂、行移动会让行的物理地址变化，而主键不会变——存主键，二级索引永远不用维护失效地址；代价就是回表。

于是查询分两种：

• 能拿到的列全在二级索引里 → 直接返回，这叫覆盖索引，不回表。
• 还需要别的列 → 拿着二级索引里的主键，回到聚簇索引再走一次 B+ 树找整行。这就是回表。

回表的代价是每命中一行，就多一次主键树的随机 IO。如果二级索引扫了 10000 行、每行都要回表，就是 10000 次随机查找——这就是「明明走了索引还是很慢」的头号原因。

五、联合索引与最左前缀：它是推论，不是规则

5.1 最左前缀的本质

联合索引 (a, b, c) 在 B+ 树里，是按 a 排、a 相同再比 b、b 相同再比 c 的字典序排的。所谓「最左前缀」，只是这个排序事实的同义反复：

• where a = ? and b = ? and c = ? → 三列全用上，能精确定位、连排序都省了。
• where a = ? and c = ? → 只有 a 能用。因为 c 的有序性只在「a 和 b 都相同」的那一组内部才成立；跳过 b，c 在整棵树里是乱的，无法定位连续区间。
• where b = ? → 完全用不上。b 的有序性以「a 固定」为前提，a 不定，b 全局无序。

记忆方式：联合索引的有序性像一串多米诺骨牌，断在哪一列后面的就全失效。

5.2 范围列会「断绝」后面的列

一个高频坑：where a = ? and b > ? and c = ?。这里 a 用得上，b 用得上（范围），c 用不上——因为 b 一旦是范围，b 相同的分组就没有唯一位置了，c 在范围结果里不再有序。

由此推出联合索引的列顺序原则（面试直接背）：

1. 等值列放前面，范围列放后面；
2. 区分度高的列放前面（能更快缩小候选）；
3. order by / group by 的列如果能接在等值列后面，可以顺带消除排序（EXPLAIN 里 Using filesort 消失）。

5.3 索引下推 ICP（Index Condition Pushdown，MySQL 5.6+）

没有 ICP 之前：where a = ? and b like 'x%' 使用索引 (a, b) 时，引擎只用 a 定位，把命中的行全部回表，回到 Server 层才过滤 b——大量回表被浪费。

有了 ICP：把能在索引里判断的条件下推到存储引擎层，在索引上就先过滤掉 b 不匹配的行，只有真正命中的才回表。EXPLAIN 的 Extra 会显示 Using index condition。

注意区分这两个 Extra（很多人搞混）：

• Using index = 覆盖索引，不需要回表，列全在索引里。
• Using index condition = ICP，减少了回表次数，但仍然要回表。

六、覆盖索引：把回表直接省掉

当查询要的所有列都在某个二级索引里，引擎就在索引树上完成全部工作，完全不碰聚簇索引。比如索引 (a, b, c)，select a, b, c from t where a = ? 就是覆盖索引，Extra 显示 Using index。

两个实用推论：

• count(*)：InnoDB 不维护精确行数（MVCC 下每行可见性不同），只能扫一遍索引来数。它会优先选最小的二级索引来扫，因为扫描量最小。覆盖索引让 count 更快。
• 列表查询只 select 需要的列：select * 几乎必然打破覆盖索引，逼出回表。

索引失效清单（反面同样要背）：

• 在索引列上做函数/运算：where date(created_at) = '2026-10-10'、where id + 1 = 5。
• 隐式类型转换：phone 是 varchar，却写 where phone = 13800000000（数字）→ 按数字比较规则转换后索引失效，全表扫。
• 前导模糊：like '%abc'。
• or 两侧有一侧没索引。
• 复合索引不满足最左前缀。
• !=、not in、is not null 等选择性差的操作，优化器可能直接放弃索引。

七、深分页：limit 100000, 20 慢在哪

7.1 慢的根因：它要「先数到第 10 万行」

limit 100000, 20 的语义是「取出前 100020 行，丢掉前 100000 行，返回后 20 行」。哪怕你走了索引：

• 二级索引要顺序扫描 100020 个索引项；
• 如果查询列不能覆盖，这 100020 行每一行都要回表（100020 次随机 IO）；
• 扫完前 100000 行后，它们全被丢弃——代价白付。

EXPLAIN 里 rows 会接近 100020，这就是慢的铁证。关键认知：限制条数（limit 的第二个参数）不影响扫描量，影响扫描量的是偏移量（第一个参数）。

7.2 方案一：延迟关联（deferred join）——减少回表

思路：先在覆盖索引上把主键捞出来，再只对最终要的那 20 行回表。

-- 原来：扫描 + 回表 100020 次
select * from article order by created_at desc limit 100000, 20;

-- 优化：子查询走覆盖索引（只取 id），外层只回表 20 次
select t.* from article t
join (
  select id from article order by created_at desc limit 100000, 20
) d on t.id = d.id;

子查询如果能走 (created_at, id) 这样的覆盖索引，扫描 100020 个索引项都在索引内完成（不回表），回表次数从 100020 降到 20。量级不变，仍是 O(offset)，但常数大幅下降。

7.3 方案二：keyset / 游标分页——才是真正的 O(1)

思路：不用「跳过 N 行」，而是用上一页最后一行的值作为起点，直接 seek 到位置。

-- 第一页
select * from article order by created_at desc, id desc limit 20;

-- 拿到上一页最后一行的 (created_at, id) 后
select * from article
where (created_at, id) < (?, ?)          -- 上一页最后一行的值
order by created_at desc, id desc
limit 20;

这里 (created_at, id) < (?, ?) 是元组比较，能在 (created_at, id) 联合索引上直接定位起点，然后顺序取 20 行——B+ 树的 seek 是 O(log n)，取 20 行是 O(1)，与偏移量无关。

代价与约束要主动说清楚：

• 排序键必须唯一（所以要额外带上 id 兜底，避免时间戳相同的行漏掉或重复）；
• 不能跳页：只能「下一页 / 上一页 / 无限滚动」，没法直接跳到第 5000 页，也拿不到总页数；
• 数据在翻页过程中新增/删除会导致轻微漂移（对信息流这类场景可接受）。

7.4 两张方案的对比与业务手段

方案	原理	复杂度	适用场景
延迟关联	子查询走覆盖索引，减少回表行数	O(offset)，常数变小	需要跳页、能接受 offset
keyset 游标	用游标值直接 seek 定位	O(1)，与 offset 无关	无限滚动、信息流
业务限制	限制最大可翻页数、缓存 id 列表	O(1)	后台管理、防爬

还有两个补充：限制最大翻页深度（很多产品只允许翻到第 100 页），以及把 id 列表按页缓存在 Redis（列表结构，直接按页取 id 再回表）。前者的合理性在于：没人真的会翻到第一万页，深分页请求往往来自爬虫。

八、EXPLAIN 实战：把结论验证一遍

explain select * from orders where user_id = 100 and status = 1 order by created_at desc;

读 EXPLAIN 的关键列（type 从好到坏）：

system > const > eq_ref > ref > range > index > ALL

• type：ref 表示用了非唯一索引等值查找，range 范围，ALL 全表扫（最差，见即红色警报）。
• key：实际选中的索引；possible_keys 是候选。
• key_len：用了联合索引的最左几个列，这是最实用的一个字段。
• rows：预估扫描行数。
• filtered：过滤后剩余百分比。
• Extra：Using index（覆盖）、Using index condition（ICP）、Using filesort（额外排序）、Using temporary（临时表）。

key_len 的计算值得背一个例子。联合索引 (a int, b varchar(20) not null, c int)，字符集 utf8mb4：

where a = ? and b = ?
key_len = 4 (a) + 20×4 + 2 (b 变长前缀) = 4 + 82 = 86
=> 说明 a、b 都用上了（对照只走 a 时的 key_len = 4）

反过来，如果 where b = ? 的 key_len 是 4 而不是 82，就说明只用到了 a——一眼看出最左前缀断在哪。

建索引的取舍：索引不是越多越好。每个二级索引都要在写入时维护（写放大）、占磁盘、让优化器选择空间变大（可能选错索引）。原则是为高频查询建必要索引，用 show index from t 定期清理冗余索引（比如已有 (a, b)，再建 (a) 就是冗余）。

九、面试追问三连

能拿满分的，是主动把这几个追问讲出来：

1. 为什么不直接上哈希或跳表？ —— 哈希不支持范围与排序，只适合等值点查；跳表赢在内存局部性差、无法批量预读，磁盘上每跳一步都是随机 IO。B+ 树是为「磁盘块 IO + 范围查询 + 排序」量身定做的。
2. 为什么二级索引存主键值而不是行地址？ —— 行地址会因页分裂、行移动而失效，主键不变，索引无需维护；代价是回表，用覆盖索引来规避。
3. 深分页优化到 O(1) 之后还要注意什么？ —— keyset 分页牺牲了跳页能力和总页数；游标键必须唯一（补 id）；数据变更会导致漂移；而且如果查询列不能覆盖，仍要控制回表行数。

十、收尾

一句话总结这题：B+ 树胜出的原因是它把「磁盘随机 IO 的次数」压到了常数级（三层装两千万行、点查 3 次 IO），同时用叶子链表白送了范围查询和排序；而所有索引优化的本质，都是围绕「减少随机 IO」——最左前缀是在省「定位不到的有序性」，覆盖索引和 ICP 是在省「回表」，keyset 分页是在省「扫过又被丢弃的行」。

顺着这条主线记，就不会把索引知识背成一堆互不相干的规则。

---

明日预告：按轮换回到系统设计方向 ——「设计一个分布式 ID 生成器：为什么数据库自增不够用、Snowflake 的 64 位怎么切分、时钟回拨的几种业界解法、号段模式（Leaf-segment）怎么扛住突发流量、为什么美团 Leaf 要同时维护号段和 Snowflake 两条腿？」

---

相关阅读

• 长上下文与 RoPE 长度外推
• 分库分表之后的在线扩容
• 分布式限流怎么做
• 短链接系统进阶