面试最爱问:「MySQL 为什么用 B+ 树做索引,不用红黑树或哈希表?」要答好它,得先看数据存在磁盘上的现实约束。这篇把 B+ 树、聚簇索引、回表、覆盖索引一次讲透。
InnoDB 读写磁盘的最小单位是页(默认 16KB 的存储单元),不是一行。哪怕只查一行,也要把整页从磁盘搬进内存。
所以好索引的目标只有一个:让一次查询碰尽可能少的页。树越矮,路上经过的页越少。
B+ 树(多路平衡搜索树,数据只存在叶子层)三特点:
根/中间节点: [10 | 20 | 30] ← 只存键+指针,不存数据
↓ ↓ ↓
叶子节点: [1,3,5] [11,13] [21,23] ← 存完整行,双向链表串起来
算一笔账:非叶节点一项 14 字节(8 字节键 + 6 字节指针),一页存 1170 项;叶子一页存 16 行(按 1KB 一行)。三层 = 1170 × 1170 × 16 ≈ 2190 万行,查询只需 3 次页读取。这就是「三层 B+ 树撑起两千万行」的由来。
为什么不用别的结构?红黑树是二叉树,两千万行高 20 多层,每层一次页读取吃不消;哈希索引(用哈希函数定位的索引)等值查询快,但完全不支持范围和排序。
B+ 树的插入位置由键值决定。自增主键永远插在最右端,那一页写满了就开新页,旧页安安静静不动——这是最理想的写入姿势。
换成无序的 UUID(随机生成的全局唯一标识),每次插入的位置随机分布:目标页可能不在内存,要额外读盘;页满了还要页分裂(把一页数据挪一半去新页),树频繁搬家。同样的写入量,UUID 主键的表会比自增主键的表大不少、写入慢不少。
所以规范是:本地表用自增;分库分表场景自增会撞,换趋势递增的分布式 ID(9.7 的雪花算法就是干这个的)。
聚簇索引(叶子直接存整行数据的索引)就是主键那棵 B+ 树,一张表只有一棵。没有主键时,InnoDB 会选唯一非空索引,实在没有就偷偷生成隐藏列。
二级索引(叶子存主键值而非整行的索引)是另外建的树。查 idx_age 这棵树,叶子拿到的是主键值,不是目标数据。
于是有了回表(拿二级索引查到的主键,再回聚簇索引查整行):
SELECT * FROM user WHERE age = 25;
-- idx_age 树找到 age=25 → 叶子里是 id=1,3
-- 再去聚簇索引树查 id=1,3 的整行 ← 这就是回表,每条一次树查找
覆盖索引(查询要的列全在索引里,不用回表)是高频优化手段:
CREATE INDEX idx_name_age ON user(name, age);
SELECT id, name, age FROM user WHERE name = '张三';
-- Extra: Using index ← 不回表,索引里全有了
SELECT * FROM user WHERE name = '张三';
-- 要取所有列,索引不够用,乖乖回表
这也是「禁止 SELECT *」的底层原因之一:少取几列,才有机会被索引覆盖。
联合索引 idx(a,b,c) 的排序规则:先按 a 排,a 相同按 b,再按 c。所以查询必须从最左列开始连续命中:
WHERE a=1 AND b=2 ✅ 命中 a,b
WHERE a=1 AND c=3 ✅ 只命中 a
WHERE b=2 ❌ 缺了最左列 a
WHERE a=1 AND b>2 AND c=3 ✅ a,b 命中,b 是范围,c 断掉
索引下推 ICP(MySQL 5.6 起,在存储引擎层就用索引列过滤)解决一个浪费:查 a=1 AND c=3 时,老版本把所有 a=1 的行都回表再判 c;有了 ICP,引擎直接在索引里先过滤 c,回表次数大减。EXPLAIN 里 Using index condition 就是它在工作。
拿数字感受一下:a=1 的行有一万条,其中 c=3 的只有一百条。没有索引下推:一万次回表、一万次 Server 层判断;有索引下推:引擎层判断一万次(只读索引,不回表),回表仅一百次。回表是随机读、索引扫描是顺序读,两者的单次代价差好几倍——所以这个优化在联合索引跳列查询里收益巨大。
邮箱、URL 这类长字符串,整列建索引太占空间。可以只取前 N 个字符建前缀索引(只用列前缀的索引):
CREATE INDEX idx_email ON user(email(10));
-- 只用前10个字符建索引,空间省一大半
代价:索引里不再有完整值,无法覆盖索引(还是要回表),也排不了完整序。取舍公式是「区分度」:COUNT(DISTINCT LEFT(email, n)) / COUNT(*),从 n=5 开始往上试,区分度接近全列时停手,多一个字符都是浪费空间。
顺便算笔账:一列 VARCHAR(255) 存满时,整列索引项最大约 1020 字节(utf8mb4 每字符 4 字节),一页 16KB 只能放 16 项;取前 10 字符后一项约 40 字节出头,一页能放 400 项。树矮了一大截,这就是前缀索引省下的真金白银。
写入视角算笔账:每棵索引树都要为一次写入付费,十棵树就是十次页维护,INSERT 吞吐可能直接折半。读取视角:真正高频的查询通常就三五条,为低频查询建的索引常年闲着,维护税却天天交。经验起点:单表 5 个以内,超了就合并——(a) 和 (a,b) 两棵树并成一棵,最左前缀让只查 a 的语句照样用。索引是负债,查到了收益才回本。
INDEX(name(10))B+ 树用「非叶只存键、叶子链表串」换来了矮树和快范围查询;二级索引查整行要回表,想让回表消失就设计好覆盖索引。