索引的本质：B+ 树、页与查找过程

本文是 MySQL 系统学习系列的 L2 核心篇。前置：MySQL 体系结构与一条 SQL 的执行旅程。学完可以配合面试题食用：MySQL 索引结构：B+ 树 vs B 树 vs 哈希索引、最左前缀与索引下推 ICP、覆盖索引与回表

上一章讲了 SQL 在 MySQL 里怎么走一遍各层组件，其中存储引擎那层留下了最大的一个坑：数据到底以什么结构放在磁盘上，查询凭什么快？答案就是索引。这一章把索引拆开看：为什么长成 B+ 树这个样子、2000 万行为什么只要 3 层、回表和覆盖索引是怎么回事。

为什么不是哈希、二叉树或者跳表

索引结构不是谁拍脑袋选的，是被磁盘的读取方式逼出来的。

InnoDB 和磁盘打交道的基本单位是页（page），默认 16KB。不管你要读一行数据还是一列的值，磁盘都至少给你搬一整页过来。一次随机读对应一次磁盘 IO，机械盘上大概 10ms 量级（SSD 快得多，但寻址成本依然远高于内存访问）。所以评价一个索引结构好不好，标准很单一：一次查询要走几次页读取。

拿几个候选结构算笔账，假设表里有 2000 万行：

哈希表：等值查询一次到位，O(1) 很美好。但哈希把有序性完全打散了，范围查询 WHERE id BETWEEN 100 AND 200 只能全表挨个算哈希再比对，等价于全表扫描。数据库里范围条件太常见了，哈希索引没法当主角（InnoDB 是自动为自适应哈希保留的内部优化，不对外）。
二叉搜索树 / 红黑树：二叉意味着每个节点只有 2 个分叉，2000 万行要 log₂(2000万) ≈ 25 层，最坏 25 次页 IO。树太高太瘦，每次分叉只排除一半数据，对磁盘太浪费。
跳表：层间也是二分缩减，层数同样是 log₂ 量级。Redis 的 zskiplist 用它是因为数据全在内存，不心疼多次指针跳转；搬到磁盘上就不行了。
B+ 树：每个节点是一页 16KB，能塞几百上千个键，分叉数（扇出）巨大。同样 2000 万行，树高只要 3 层左右，一次查询 2~4 次页 IO 搞定。

一句话总结：磁盘 IO 次数 ≈ 树高，想树矮就得每层多分叉，B+ 树的"矮胖"正是为页式磁盘读取设计的。LSM 树（RocksDB 那套）是另一条路线，写入更友好，代价是读放大和后台 compaction，MySQL 的 InnoDB 没选它。

B+ 树长什么样：一切数据都在叶子

B+ 树有两个关键设计，直接决定了后面所有话题：

非叶子节点只存索引键和指向子节点的指针，不存整行数据。16KB 的一页能塞下大概 1200 个键指针对（bigint 主键 8 字节 + 页指针 6 字节，再加页头开销）。
叶子节点存全部数据：键值 + 完整行数据（或二级索引的索引列 + 主键值），并且所有叶子节点用双向链表串起来。

mermaid

graph TD
    R["根节点（非叶子）<br/>15 | 56 | 77"] --> A["中间节点<br/>15,20,49"]
    R --> B["中间节点<br/>56,60,74"]
    A --> L1["叶子页 1<br/>1~15 行数据"]
    A --> L2["叶子页 2<br/>16~49 行数据"]
    B --> L3["叶子页 3<br/>50~74 行数据"]
    B --> L4["叶子页 4<br/>75~99 行数据"]
    L1 <--> L2
    L2 <--> L3
    L3 <--> L4

这两个设计各带来一个直接好处：

非叶子不存数据 -> 每页能放的分叉多 -> 树更矮。
叶子间双向链表 -> 范围查询找到起点后顺着链表扫就行，不用回到树上反复定位。

2000 万行只要 3 层，怎么算的

面试和实际容量规划都会用到这个推导，假设行数据平均 1KB：

叶子层：每页 16KB ÷ 1KB/行 = 16 行/页。2000 万行需要 2000万 ÷ 16 = 125 万个叶子页。
中间层：每页 16KB ÷ 14B/项 ≈ 1170 个指针。125 万叶子 ÷ 1170 ≈ 1068 个中间页。
根节点：1068 个中间页 ÷ 1170 ≈ 1 个根页。

3 层的 B+ 树，装 2000 万行绰绰有余。一次主键等值查询最多 3 次页 IO（根 -> 中间 -> 叶子），而且根节点那页几乎永远在内存里的 buffer pool，实际磁盘 IO 往往只有 1~2 次。

这个推导反过来也解释了一个容量直觉：为什么单表建议别超过 2000 万行左右。不是硬限制，而是行数再涨，B+ 树要长到 4 层，每次查询多一次页 IO，索引维护成本也随之上升。分库分表的阈值讨论通常从这里出发。

聚簇索引与二级索引：回表的由来

聚簇索引（clustered index）就是那张"叶子存整行数据"的主 B+ 树，InnoDB 表数据本身就按主键组织在聚簇索引的叶子里——索引即数据，数据即索引。所以一张 InnoDB 表必须有主键，你没显式建的话 MySQL 会优先挑一个非空唯一索引，实在没有就用隐藏的 row_id 建。

二级索引（secondary index，也叫辅助索引）是另外建的 B+ 树，叶子不存整行，只存索引列的值 + 主键值。

sql

-- 表结构假设：id 为主键，name 上有普通索引
CREATE TABLE user (
  id     BIGINT PRIMARY KEY,
  name   VARCHAR(50),
  age    INT,
  KEY idx_name (name)
) ENGINE=InnoDB;

-- 这条查询的执行路径：
SELECT * FROM user WHERE name = 'zhang';
-- 1. 在 idx_name 树上找到 'zhang'，叶子节点里拿到主键 id=88
-- 2. 拿着 id=88 回到聚簇索引树再查一遍，取出整行   <- 这就是"回表"

回表不是错误，是二级索引的工作方式，但它有成本：二级索引树上一次查找 + 聚簇索引树上一次查找，两棵树各走一遍。如果查出的行数很多，回表次数线性增加，优化器算完账可能直接放弃二级索引走全表扫描。

主键设计三原则的索引依据

回表机制直接解释了主键选型的几条军规：

自增：聚簇索引按主键有序，自增主键永远追加到最后一页，页写满开新页即可。用 UUID 或随机值做主键，新行会插到已有页中间，触发页分裂——原页放不下要劈成两页，还连带挪动记录、更新页链表，写入放大明显。
不太长：每个二级索引的叶子都要存一份主键值，主键越长（比如 36 字符的 UUID），所有二级索引都跟着膨胀，占空间还降低每页可存的键数（扇出变小、树变高）。
不常更新：主键一变，所有二级索引叶子里的主键值都得跟着改。

最左前缀与索引下推：联合索引的排列规则

联合索引 (a, b, c) 不是三棵树，是一棵 B+ 树，键按 a 排序、a 相同再按 b、b 相同再按 c 排。可以理解成先把三元组拼成字符串 (a,b,c) 再整体排序——排好的序列里，a 是全局有序的，b 只在 a 相同的片段内局部有序，c 的局部范围更小。

mermaid

graph TD
    subgraph 联合索引 a,b,c 的叶子排列
    A["(1,1,1) (1,2,5) (1,2,9) (2,0,3) (2,3,1) (5,1,1)"]
    end

这个排列规则推出最左前缀原则：

sql

-- 假设索引 KEY idx (a, b, c)
WHERE a = 1 AND b = 2          -- ✅ a、b 都能走索引
WHERE a = 1 AND c = 3          -- ⚠️ 只有 a 走索引，c 在 a=1 的片段内无序，只能过滤
WHERE b = 2                    -- ❌ b 全局无序，索引失效
WHERE a = 1 AND b > 10 AND c = 5  -- a、b 走索引；b 是范围后，c 无法用于定位（ICP 除外）

范围条件是个分水岭：b > 10 之后，命中片段里 c 是乱序的，索引只能用到 b 为止。

索引下推（ICP，Index Condition Pushdown，MySQL 5.6+）是在这个基础上的一个减负优化：以前引擎在索引里定位到 a=1 AND b>10 的行就停，把整行回表取出来再交给 Server 层过滤 c；开了 ICP 后，引擎直接在索引叶子节点里先把 c=5 判断掉，不满足的不回表。判断下推到引擎层，省的是回表次数。

覆盖索引：SELECT 的列决定走不走索引

继续沿用回表的逻辑推一步：如果二级索引的叶子里已经有查询需要的所有列，那回表这一步干脆可以省掉——这就是覆盖索引（covering index）。EXPLAIN 里对应 Extra: Using index。

最典型的场景是 SELECT * 换成明确列清单：

sql

-- 只需要 name，而 idx_name 的叶子恰好有 (name, id)
SELECT name FROM user WHERE name LIKE 'zhang%';   -- 覆盖索引，不回表
SELECT *    FROM user WHERE name LIKE 'zhang%';   -- 还要 age，必须回表

动手实操：用 EXPLAIN 看见回表与覆盖索引

空讲原理没用，亲手跑一遍对比才记得住。完整实验流程：

sql

-- 1. 建表造数据（10 万行足够看出差异）
CREATE TABLE icp_demo (
  id     BIGINT AUTO_INCREMENT PRIMARY KEY,
  name   VARCHAR(50) NOT NULL,
  city   VARCHAR(20),
  age    INT,
  KEY idx_name (name)
) ENGINE=InnoDB;

-- 存储过程灌数据（MySQL 8 默认 binlog 需要显式声明，用 SESSION 级即可）
DELIMITER $$
CREATE PROCEDURE fill_icp()
BEGIN
  DECLARE i INT DEFAULT 0;
  SET SESSION log_bin_trust_function_creators = 1;
  WHILE i < 100000 DO
    INSERT INTO icp_demo(name, city, age)
    VALUES (CONCAT('user_', LPAD(i, 6, '0')),
            ELT(1 + FLOOR(RAND() * 5), 'BJ','SH','SZ','HZ','CD'),
            18 + FLOOR(RAND() * 50));
    SET i = i + 1;
  END WHILE;
END$$
DELIMITER ;
CALL fill_icp();

-- 2. 回表版：SELECT * 需要索引里没有的列，必须回聚簇索引取整行
EXPLAIN SELECT * FROM icp_demo WHERE name LIKE 'user_001%';
-- key: idx_name
-- Extra: NULL            <- 走了索引但需要回表（8.0.18+ 无 Using index 即回表）

-- 3. 覆盖索引版：只查 id 和 name，idx_name 叶子 (name, id) 全都有
EXPLAIN SELECT id, name FROM icp_demo WHERE name LIKE 'user_001%';
-- key: idx_name
-- Extra: Using index    <- 覆盖索引，免回表

-- 4. 加一个联合索引看 ICP：
ALTER TABLE icp_demo ADD INDEX idx_name_city (name, city);
EXPLAIN SELECT * FROM icp_demo WHERE name LIKE 'user_001%' AND city = 'BJ';
-- Extra: Using index condition  <- 索引下推生效，city 在索引层过滤后再回表

四个观察点：

第 2 步和第 3 步只差 SELECT 的列，执行计划一个回表一个不回表——查询要什么列，直接影响索引能不能被"用满"。
第 3 步的 Using index 就是覆盖索引的标志。注意 Using index 和 Using index condition 是两回事，后者是 ICP。
实测性能差距：SELECT * 版在 10 万行、LIKE 前缀命中几百行时差距不大；把命中行数放大到几千行，回表版的 rows/耗时明显上台阶，可以用 EXPLAIN ANALYZE（MySQL 8.0.18+）看实际执行数字。
索引不是越多越好：每个二级索引都要维护一棵树，写入时全部跟着改。高频查询的列组合才值得建。

常见误区与小结

"哈希索引查询快，MySQL 应该用它" —— 等值确实快，但范围查询和排序直接废掉，磁盘场景下树高才是硬指标。
"UUID 做主键没问题，反正唯一" —— 唯一性没问题，随机插入引发页分裂 + 所有二级索引膨胀，写入吞吐和索引空间一起遭殃。
"WHERE 里列顺序决定索引是否生效" —— 优化器会做等值条件交换，WHERE b=2 AND a=1 一样能用上 (a,b)；决定因素是索引列的排列，不是 SQL 书写顺序。
"EXPLAIN 出现 Using index condition 就是覆盖索引" —— 它是索引下推，还是要回表；覆盖索引的标志是 Using index。
"索引建了就该被用" —— 优化器按成本估算选路，回表代价高或命中行数太多时放弃索引反而更快，别看到全表扫描就急着加索引。

小结：索引的三个话题其实是一条线——B+ 树的矮胖结构让查找只要几次页 IO；聚簇索引与二级索引的分工引出回表；回表成本又推导出覆盖索引、最左前缀、ICP 这些优化手段。把"叶子存什么、一次查询走几棵树"想清楚，大部分索引问题都能自己推出来。下一篇进入 InnoDB 的另一半核心：事务与 MVCC，看一致性读是怎么在不加锁的情况下实现的。

参考

参考：MySQL 8.0 官方文档 InnoDB Storage Engine 章节（B+ Tree Indexes / Clustered and Secondary Indexes）、《高性能 MySQL》第 5 章索引部分、Dewen 博客 mysql 索引实现系列

索引的本质：B+ 树、页与查找过程 ​

为什么不是哈希、二叉树或者跳表 ​

B+ 树长什么样：一切数据都在叶子 ​

2000 万行只要 3 层，怎么算的 ​

聚簇索引与二级索引：回表的由来 ​

主键设计三原则的索引依据 ​

最左前缀与索引下推：联合索引的排列规则 ​

覆盖索引：SELECT 的列决定走不走索引 ​

动手实操：用 EXPLAIN 看见回表与覆盖索引 ​

常见误区与小结 ​

参考 ​