【MySQL篇|第八篇】索引底层实现

在日常开发中，只要表数据量稍微大一点，慢查询就会成为绕不开的问题。而解决慢查询最直接、最有效的手段，往往就是加索引。但很多同学对索引的理解停留在“加了就快”的层面，面试时被追问“索引底层是怎么实现的”就容易卡壳。本文从索引的本质出发，一步步拆解 MySQL 索引的底层数据结构，重点讲清楚 B+ 树为什么能成为 InnoDB 的默认选择。

一、索引到底是什么

从最朴素的角度理解，索引就是一种帮助 MySQL 高效获取数据的数据结构。它的作用类似于书籍的目录：如果没有目录，想找某一章内容只能从第一页翻到最后一页；有了目录，就能直接定位到目标页码。所以这个目录的设置是非常关键的，我们的目录有很多种做法，有些的目录清晰明了，而有些的很难很快的定位到需要的地方，因此这个目录的制作也是一个关键部分。

把这句话拆开看，有三个关键点：

• 本质是数据结构：索引不是“魔法”，它本身也要占用磁盘空间，也需要维护。
• 目的是高效获取数据：索引把“全表扫描”的 O(n) 查找，优化成近似 O(log n) 的查找。
• 代价是空间和维护成本：索引越多，写入时需要的额外更新越多，占用的磁盘也越大。

在 InnoDB 中，索引和数据是存放在一起的，索引即数据，数据即索引。这一点非常关键，后面讲聚簇索引时会反复用到。

二、为什么不用二叉树、红黑树或哈希

既然索引是数据结构，那为什么 MySQL 不直接用最熟悉的二叉树？原因在于磁盘 IO 的特性。

2.1 二叉搜索树的退化问题

普通二叉搜索树在数据有序插入时会退化成链表，查找复杂度从 O(log n) 退化为 O(n)。即使换成平衡二叉树（AVL）或红黑树，树的高度依然偏高。假设一张表有一千万条数据，红黑树的树高大约在 20 到 30 层，每下降一层就可能意味着一次磁盘 IO，这个代价是无法接受的。因此这个方法还是行不通，只能适用于那些数据量少的一些表。

2.2 哈希索引的局限

哈希索引的等值查询是 O(1)，看起来很美，但它有两个致命问题：

• 不支持范围查询，因为哈希值本身没有顺序性。
• 不支持排序，也无法利用最左前缀原则。

所以哈希索引只适合等值查询场景，InnoDB 的自适应哈希索引也是内部优化，用户无法直接创建。

2.3 磁盘 IO 才是真正的瓶颈

数据库的数据存放在磁盘上，磁盘读取以页（Page）为单位，InnoDB 默认一页 16KB。一次磁盘 IO 会把整页数据读入内存。因此，索引结构设计的核心目标不是“比较次数最少”，而是让树的高度尽可能低，从而减少磁盘 IO 次数。这就引出了多路平衡查找树。

三、B 树与 B+ 树的结构对比

3.1 B 树的基本形态

B 树是一种多路平衡查找树，一个节点可以存放多个 key 和多个子节点指针。相比二叉树，B 树把“瘦高”的形态变成了“矮胖”，树高大幅降低。但 B 树的非叶子节点也存储数据，这会带来两个问题：

• 每个节点能容纳的 key 数量变少，树高相对更高。
• 范围查询需要在树中反复中序遍历，效率不够稳定。

3.2 B+ 树的改进

B+ 树在 B 树基础上做了三点关键改进：

下面用一张简化的结构图说明 B+ 树的形态：

flowchart TD
A["根节点: 15 | 30"] –> B["内部节点: 5 | 10"]
A –> C["内部节点: 20 | 25"]
A –> D["内部节点: 35 | 40"]
B –> E["叶子: 1,3,5"]
B –> F["叶子: 7,9,10"]
C –> G["叶子: 16,18,20"]
C –> H["叶子: 22,24,25"]
D –> I["叶子: 32,34,35"]
D –> J["叶子: 38,40,42"]
E -.双向链表.-> F
F -.双向链表.-> G
G -.双向链表.-> H
H -.双向链表.-> I
I -.双向链表.-> J

可以看到，内部节点只负责导航，真正的数据全部在叶子层，并且叶子层是一条有序链表。这正是 B+ 树能同时兼顾等值查询和范围查询的原因。

四、InnoDB 的索引实现：聚簇索引与二级索引

4.1 聚簇索引

InnoDB 使用主键构建聚簇索引（Clustered Index），叶子节点存放的是整行数据。也就是说，聚簇索引的叶子节点就是数据页本身。如果没有显式定义主键，InnoDB 会选择一个唯一非空索引代替，再没有就生成一个隐藏的 6 字节 row_id。

这也解释了一个常见现象：按主键查询最快，因为一次 B+ 树查找就能拿到整行数据。

4.2 二级索引与回表

除了主键索引，我们创建的其他索引都叫二级索引（Secondary Index）或辅助索引。二级索引的叶子节点存放的是索引列的值 + 主键值，而不是整行数据。

因此，通过二级索引查询非索引列时，需要先查到主键，再拿主键去聚簇索引里查一次完整数据，这个过程叫回表。回表意味着两次 B+ 树查找，这也是为什么“尽量使用覆盖索引”会成为优化常识。

4.3 覆盖索引

如果查询需要的列全部包含在二级索引中，就无需回表，这种索引称为覆盖索引。例如：

— 假设存在联合索引 idx_name_age (name, age)
SELECT name, age FROM user WHERE name = 'Tom';

这条查询只需要扫描 idx_name_age 就能拿到全部结果，执行计划中 Extra 会显示 Using index。

五、索引的物理存储与页结构

InnoDB 以页为单位管理数据，索引页的结构大致如下：

页内记录通过单向链表串联，Page Directory 提供稀疏索引，使得页内查找也能用二分法。页与页之间则通过 File Header 中的前后指针形成双向链表，这就是 B+ 树叶子层链表的物理基础。

六、联合索引与最左前缀原则

联合索引是把多个列组合起来建一棵 B+ 树，排序规则是先按第一列排序，第一列相同再按第二列排序，以此类推。这直接决定了最左前缀原则：

— 联合索引 idx_abc (a, b, c)
SELECT * FROM t WHERE a = 1 AND b = 2; — 命中 a、b
SELECT * FROM t WHERE b = 2 AND c = 3; — 无法使用索引
SELECT * FROM t WHERE a = 1 AND c = 3; — 只命中 a
SELECT * FROM t WHERE a = 1 AND b > 2 AND c = 3; — c 无法用于索引查找

理解最左前缀的关键，是把它想象成一本先按姓氏、再按名字排序的电话簿：你只知道名字而不知道姓氏，是无法快速定位的。

七、索引失效的常见场景

建了索引不代表一定用得上，以下场景容易导致索引失效：

这个我在前面具体讲到过，不了解的可以去看前几期文章

• 对索引列做函数运算或表达式计算，如 WHERE YEAR(create_time) = 2024。
• 隐式类型转换，如字符串列用数字比较 WHERE phone = 13800000000。
• 以通配符开头的模糊查询，如 LIKE '%abc'。
• 使用 OR 且两侧列没有都建索引。
• 违反最左前缀原则的联合索引查询。
• 优化器判断全表扫描更快，例如区分度极低的列。

排查时建议使用 EXPLAIN 查看 type、key、rows 和 Extra 字段，确认索引是否真正生效。

八、索引设计的一些实践建议

九、总结

回到最初的问题：MySQL 索引是什么？它是一种为了减少磁盘 IO 而设计的有序数据结构；底层怎么实现？InnoDB 用 B+ 树组织索引，非叶子节点只存键做导航，叶子节点存数据并用双向链表串联，从而同时支持高效的等值查询和范围查询。聚簇索引的叶子节点是整行数据，二级索引的叶子节点是索引列加主键，需要时通过回表补齐数据。

理解了这层结构，很多看似零散的优化规则——覆盖索引、最左前缀、避免函数运算、慎用随机主键——都会变得顺理成章，因为它们本质上都是在减少树的高度、减少回表次数、减少磁盘 IO。