很多后端开发把索引当成“面试题”来背，背完B+树、哈希索引之后就觉得懂了，但真到了线上慢查询排查，或者被人追问一句“为什么MySQL不用红黑树做索引”，往往就露馅了。我在优化线上订单表的时候，被这个底层问题卡过整整一个下午。后来把索引的数据结构从头理了一遍，才明白之前建的索引为什么时灵时不灵。这篇文章就把这套底层逻辑掰开讲清楚，涵盖MySQL索引的完整数据结构脉络，从为什么需要索引、各种数据结构的对比，到InnoDB里B+树的真实形态、联合索引的最左前缀原理，再到索引失效场景的根因分析。适合正在准备面试的后端开发，也适合做SQL优化但总觉得差点理论的DBA或者架构师。
索引的数据结构这个问题，本质上是在问一件事：数据库凭什么能用一条SQL在千万行数据里快速定位到目标行。搞清楚这个问题，索引优化就不再是靠记忆力和感觉，而是靠推导。
1. 先搞清楚：索引到底解决的是哪一类问题
1.1 没有索引时，MySQL是怎么查数据的
先把最底层的执行过程讲明白。没有索引的情况下，MySQL执行一条select * from orders where user_id = 123，只能做全表扫描——从表对应的第一个数据页开始，一页一页读进内存，逐条比对user_id字段，直到找到所有匹配的行。
这里的关键是“页”这个概念。InnoDB的存储单位是页，默认16KB。一张千万级别的表，数据页数量可能达到几十万个。全表扫描意味着要把所有这些页从磁盘读出来，哪怕实际命中的只有那么几行。更麻烦的是，这些数据页在磁盘上的物理位置不连续，一次查询可能要发起大量随机磁盘IO。机械硬盘的随机IO大概在10ms级别，哪怕SATA SSD也得几十微秒，几十万次随机IO累积起来，一次查询几十秒甚至几分钟都是可能的。
举个生活化的例子：一本没有目录也没有页码标记的书，你想找“第二章第三节第三段”讲的内容，只能从头一页一页翻。翻完前半本才找到，这个“从头翻”的成本就是你为没做索引付出的代价。
1.2 索引的三个隐含代价，很多人忽略了
既然索引能把查询从全表扫描变成“查目录”，那是不是索引建得越多越好？显然不是。每一个索引都是一棵独立的B+树，它带来三个隐藏的成本。
第一是空间成本。一个二级索引等于额外存了一份排序后的键值结构，索引列越大、越长，这份结构占的空间就越多。第二是写入成本。每次insert、update、delete，除了要改数据页，还要同步维护该表上每一棵索引树。数据量越大、索引越多，一次写入需要同步更新的树就越多，写入放大效应越明显。第三，也是最容易被忽略的，索引会给优化器增加负担。表上有五六个单列索引和两三个联合索引时，MySQL的优化器需要估算哪种索引组合成本最低，索引越多，估算空间越大，选错执行计划的概率也越高。
所以索引不是免费午餐，它是一种典型的用空间换时间、用写入性能换查询性能的结构。理解了这一点，才能理解为什么我们在设计索引时，总说“能用联合索引覆盖多个查询，就不要建一堆单列索引”。
2. 一路淘汰过来的方案：从二叉树到哈希到B树到B+树
2.1 二叉树和红黑树的致命伤：树高等于磁盘IO次数
顺着“查询要快”这个需求，很多计算机基础比较好的人会想到二叉树。二叉搜索树确实能实现二分查找，理论上O(log n)的查找效率。但二叉树有一个硬伤：数据有序插入时，它会退化成链表，查询复杂度直接变O(n)。于是又有AVL树，通过旋转强行保持平衡，把高度控制在O(log n)。红黑树则进一步放宽了平衡条件，用局部调整降低旋转成本，Java的HashMap、TreeMap里都在用。
那MySQL为什么不用红黑树做索引？答案是磁盘IO。红黑树的节点在逻辑上是一棵树，但在磁盘上各节点存储位置是随机的。千万行数据量下，红黑树的高度大约是2 * log₂(n)，也就是四十层左右。每访问一个节点，就是一次随机磁盘IO，查一条数据需要四十多次IO，这个成本根本无法接受。
换句话说，树的高度直接等于查询时的磁盘IO次数。所以一切设计的核心目标，都是把树“压矮”。压矮的方向有两个：一是每个节点多存几个键值，让树的“叉”变多；二是让每个节点的大小尽可能贴近磁盘页的大小，一次IO读一整个节点，把性价比提到最高。
2.2 哈希索引：等值查找极快，但最怕范围查询
哈希索引的思路和树完全不同。它把索引列的值通过哈希函数计算出一个桶位置，等值查询where user_id = 123时，直接计算哈希值就能定位到桶，时间复杂度接近O(1)。
听起来更快，但哈希有两个致命限制。第一，哈希函数计算出来的结果是无序的，所以哈希索引完全无法支持范围查询where create_time > '2024-01-01'，也无法支持排序。第二，哈希冲突需要额外处理，大量冲突时性能会退化。MySQL的Memory引擎默认用哈希索引，InnoDB也内置了自适应哈希索引（AHI），但它只是B+树之上的一个加速缓存，专门用来优化等值查询热点，而不是用来替代B+树作为主索引结构。
2.3 B树和B+树的差异：数据是否下沉到叶子
B树（Balance Tree）是多路平衡搜索树，每个节点可以存多个键值和多个孩子指针，解决了二叉树太高的问题。以MySQL为例，如果主键是bigint，一个B树节点能存的键值数量远大于2，树高可以压缩到三四层。
但B树有一个问题：它的内部节点不只存索引键，还存对应的行数据（或行指针）。行数据的体积远大于键值本身，这导致每个内部节点能容纳的孩子指针数量被大幅压缩，树的扇出变小，树高反而变高。另外，B树的范围查询需要在中序遍历中跨多个节点回溯，拿到一批连续数据时，访问路径是跳跃的，不利于磁盘顺序读。
B+树针对这两个问题做了改进：内部节点只存键值和指向子节点的指针，所有的行数据全部下沉到叶子节点；叶子节点之间用双向链表串联起来。这样有两个直接好处。一是内部节点可以塞下更多索引项，扇出大幅提升，同样高度下能索引的数据量成倍增加。二是范围查询时，只要找到起始叶子节点，然后顺着链表顺序往下读就行，完全符合磁盘预读的顺序IO特性。这也是为什么几乎所有主流关系型数据库的索引最终都选择了B+树。
2.4 顺带说一句：Redis用跳表，MySQL为什么不用
这里可以延伸一个小知识点。Redis的有序集合用的是跳表而不是B+树，很多人会问：为什么MySQL不照抄Redis的方案？核心原因是内存和磁盘的差异。Redis的数据都在内存里，内存随机访问成本极低，跳表实现简单、插入删除方便、区间查询也顺手。而MySQL的数据在磁盘上，磁盘最小的读写单位是页，B+树把节点大小和页对齐，一次IO就能把一个完整节点读进内存，局部性远好于跳表——跳表的节点分散，访问下一个节点时大概率需要重新发起IO。技术选型从来不是“哪个结构更高级”，而是“哪个结构更适配当前存储介质”。
3. 把B+树放到InnoDB里，具体长什么样
3.1 页、扇出、三层树能撑起千万级数据
说到InnoDB，必须把B+树的节点和存储引擎的页挂上钩。InnoDB的每个B+树节点对应一个数据页，默认16KB。页的大小决定了扇出的上限。
算一笔账：假设主键是bigint，占8字节，加上指向子节点的指针6字节，一个索引项一共14字节。一个16KB的页，也就是16384 / 14 ≈ 1170，能放下约1170个索引项。这就是B+树第一层内部节点的扇出。再看叶子层，假设一行数据平均1KB，一个叶子页能放16行记录。
于是三层B+树的容量就是：根节点有1170个孩子，每个孩子又有1170个孩子，叶子节点总数就是1170 * 1170 ≈ 137万个页，再乘以每个页16行记录，总共能存大约2190万行数据。换句话说，两千万行以内的表，B+树只需要三层。查询时最多三次磁盘IO就能定位到目标记录：一次根节点、一次中间层、一次叶子节点。这个数字对比全表扫描的几十万次IO，差别就是几百毫秒和几十秒的差距。
这也是为什么主键建议用bigint自增而不是随机UUID。自增主键让新记录在叶子节点上顺序追加，页分裂概率低；随机UUID会导致叶子页频繁分裂、数据页碎片化，索引膨胀的同时IO次数增多。
3.2 聚簇索引、二级索引与回表
InnoDB的表本身就是一棵以主键为索引键的B+树，这棵树的叶子节点直接存整行数据。这就是聚簇索引（Clustered Index）。聚簇索引的查找路径最短：主键条件一旦确定，直接通过B+树定位到叶子节点，顺带把整行数据拿出来了，不需要二次跳转。
而二级索引（Secondary Index，也就是我们平时create index建的普通索引）叶子节点存的是索引字段的值加上主键值，不存整行数据。执行where name = '张三'且name上有二级索引时，MySQL先通过这棵二级索引的B+树找到匹配记录的主键值，再拿主键去聚簇索引的B+树里找整行数据。第二次查找就叫“回表”。
回表不是必然的。如果查询需要的所有字段都已经包含在二级索引里，比如索引是(name, age)，查询只要name和age，那二级索引的叶子节点就能覆盖所有需要的数据，MySQL会把这个情况标记为Using index，也就是覆盖索引。覆盖索引不仅省掉回表的IO，还能让优化器在某些排序场景直接使用索引的有序性，是SQL优化里性价比最高的手段之一。
3.3 插入引发的页分裂，以及它的连锁反应
B+树是动态平衡的，插入数据时如果叶子页满了，就需要做页分裂：把一部分数据挪到新页，再把新页挂在父节点下。页分裂的代价不只是多几次IO。分裂后的数据页在磁盘上通常不是相邻的，破坏了叶子链表原本的物理连续性，后续的范围扫描会从顺序读退化成随机读。
更隐蔽的问题是，页分裂会留下碎片空间，页的填充率下降，同样数据量占用的磁盘页变多，索引体积膨胀。这也是为什么表在频繁删除、更新之后，即使数据量没变，查询也可能变慢——索引页的填充率已经被碎片打穿了。定期执行optimize table，让InnoDB重建索引页、提升填充率，往往就能把慢查询救回来，这招在维护老表时特别好用。
4. 实战：联合索引怎么建，最左前缀是怎么回事
4.1 从“where a and b”说起
网上被问烂的一个问题：where a = 1 and b = 2，该怎么建索引？答案几乎永远是联合索引(a, b)优先于两个单列索引(a)、(b)。
为什么？因为联合索引在B+树里的排序方式是“先按a排序，a相同再按b排序”。这就相当于一个先按姓氏排、再按名字排的通讯录：你要找“张伟”，先定位到“张”的区域，再在里面找“伟”，全程利用索引的有序性。
反观两个单列索引的方案，MySQL通常只会选择其中区分度高的那个索引，找到一批a = 1的记录，再用主键回表逐条过滤b = 2的条件。这就是一次索引查询加一次回表过滤的过程，比联合索引一步到位要绕得多。
联合索引(a, b)的一个额外好处是它能支撑更多查询：where a = 1走索引没问题，where a = 1 order by b也能用索引的有序性避免文件排序，where a = 1 and b > 5同样可以。几乎就是一个索引服务了多个查询模式，这也是我说“能用联合索引就别拆单列索引”的底气来源。
4.2 explain实验：看执行计划说话
光讲原理没用，落地一定要看explain。我建了一个简单的测试表，索引就建(a, b)：
create table idx_test ( id bigint primary key auto_increment, a int not null, b int not null, c varchar(64), key idx_a_b (a, b) );跑下面两组查询：
explain select * from idx_test where a = 1 and b = 2; explain select * from idx_test where b = 2;第一组的执行计划里，key那列是idx_a_b，key_len大概是8字节，说明a和b两列都被索引用上了。第二组的key同样可能显示idx_a_b，但仔细看rows会变大，而且Extra可能出现Using where——这时索引并没有真正按b做裁剪，只是用了索引的a列结果再逐条过滤b。
真正需要注意的是，别被骗了：只要执行计划里出现了索引名，不等于索引被用到了最佳状态。判断联合索引到底用了几列，靠的是key_len的长度。key_len从8变成4，说明只用到了a列，b列的部分没有参与索引定位，只是变成了普通的条件过滤。这个排查手法在线上分析慢查询时是硬功夫。
顺便说一个最左前缀的延伸场景：如果查询条件是where b = 2这种跳过a直接用b的情况，联合索引(a, b)是帮不上忙的。此时要么建一个(b)单列索引，要么把整个索引改成(b, a)。怎么选？看哪个查询更热门、更频繁。如果where b出现的频率远高于where a and b，那建(b, a)是对的；反过来，(a, b)是常态。没有银弹，一切以真实业务查询为准。
5. 索引失效场景，每个都能追溯到数据结构根因
5.1 对索引列做函数运算、隐式类型转换、前导模糊
很多人背过“索引失效的几种场景”，但换个说法就判断错了。原因是只背结论，不懂原理。这里我逐个从数据结构层面拆。
第一类，对索引列做函数或计算，比如where year(create_time) = 2024。B+树索引的有序性建立在create_time原始值上，但条件是对year(create_time)的结果做比较。数据库在每条记录上都要先算一遍函数，得到的结果是无序的，B+树的有序性完全被打破，优化器只能放弃索引改全表扫描。同理，where id + 1 = 10也会失效，把计算挪到等式右侧变成where id = 9就好了。
第二类，隐式类型转换。索引列是varchar，查询条件是数字，MySQL会默认把varchar转成数字再比较，相当于对索引列做了隐式的cast()函数，和上面的情况一样，索引失效。典型例子：手机号字段是varchar，查询写where phone = 13800138000，索引直接废掉。解决方法是加上引号，where phone = '13800138000'。
第三类，前导模糊where name like '%张'。B+树的有序性允许'张%'这种前缀匹配：从第一个字符是“张”的位置开始扫描。但'%张'需要知道“以张结尾的所有字符串”的起点，这个起点在B+树里根本不存在，只能全扫。反直觉的补充：where name like '%张%'中，如果查询字段有覆盖索引，MySQL有可能会用索引扫描，但仍然不是索引定位，而是扫描整个索引树，性能上和全表扫描半斤八两，别指望太多。
5.2 范围查询之后的列、OR连接、NOT IN这些边角
联合索引的失效更隐蔽。对索引(a, b, c)来说，where a = 1 and b > 10 and c = 5，c条件用不上索引。原因还是B+树的排序规则：a确定之后，b是有序的，可以用范围定位；但范围查到的所有b > 10的记录里，b是无序的，c自然也不再有序。所以范围之后的列无法继续用索引定位，只能逐条过滤。这也意味着联合索引列的顺序设计极其讲究：把等值查询的列放前面，把范围的列放后面。
OR连接是另一个被忽视的失效场景。where a = 1 or b = 2，如果a有索引，b没有索引，优化器要对两个条件分别走索引和全表扫描，再把结果合并，成本反而更高，所以它通常会直接选择全表扫描。解决方法是确保每个OR条件都有索引，或者用union all把两个查询拆开。NOT IN和!=也类似：B+树擅长等值和范围，但“不等于”意味着要排除一个点、扫几乎整棵树，优化器一算成本，大概率选全表扫描。
为了便于排查，我把常见的失效场景整理成一张表：
| 场景 | 根因 | 解决方案 |
|---|---|---|
where year(create_time)=2024 | 函数破坏索引有序性 | 改写为create_time >= '2024-01-01' and create_time < '2025-01-01' |
where phone = 13800138000 | 隐式类型转换使列参与计算 | 查询值加引号保持类型一致 |
where name like '%张' | 前导模糊无法定位起点 | 使用前缀匹配，或配合全文索引 |
where a=1 and b>10 and c=5 | 范围后的联合索引列无序 | 调整索引列为(a, c, b)，把范围列放最后 |
where a=1 or b=2 | OR条件中存在无索引列 | 给b建索引，或改用union all |
update大量行时索引维护成本激增 | 写入需要同步维护每棵B+树 | 精简索引数量，合理利用联合索引 |
6. 主键索引、唯一索引的差别，以及不同引擎的索引实现差异
6.1 主键索引和唯一索引到底差在哪
这是一个高频面试题，也是一个经常被搞混的概念。首先要清楚，在InnoDB里，主键索引就是聚簇索引，它决定了表数据的物理存放顺序。一张表只能有一个主键，且主键列不能为NULL。如果你建表时没有指定主键，InnoDB会找一个非空的唯一索引当主键；找不到就自动生成一个隐藏的6字节rowid作为聚簇索引键。从性能和代码可维护性两个角度看，都强烈建议显式声明主键。
唯一索引的要求宽得多：一张表可以有多个唯一索引，且唯一索引允许NULL值，MySQL中一个唯一索引上可以存在多个NULL。区别还体现在查询路径上：主键索引是聚簇索引，主键查询一次就拿到行数据；唯一索引是二级索引，查询到主键后还要回表。当然，覆盖索引场景下唯一索引也不需要回表。
写入时的差异更实际。唯一索引为了保证唯一性，每次插入或更新都要先查一遍索引页，确认没有重复值，这一步必然存在；普通索引没有这个约束，InnoDB可以利用change buffer把对二级索引的修改缓存下来，后续再合并。所以高并发写入场景下，不必要的唯一索引会带来额外的性能损耗。这个差异在单机低负载下看不出来，但在批量导入数据时尤其明显。
6.2 不同引擎的索引组织和Oracle的一个小提醒
MySQL里常见的是InnoDB和MyISAM。MyISAM的索引是典型的非聚簇结构：索引文件（.MYI）和数据文件（.MYD）分开，所有索引的叶子节点都只存指向数据行的物理地址。B+树叶子定位到地址后，还需要再访问一次数据文件才能拿到整行数据。InnoDB则直接把数据放进主键索引的叶子节点，省了一次跳转，这也是InnoDB逐渐替代MyISAM成为默认引擎的底层原因之一。
如果平时会用Oracle，可以顺带记一个知识：Oracle的默认索引结构是B*树，可以理解为B+树的一种变体；Oracle的索引默认和表放在同一个表空间，但可以单独指定索引表空间，目的是让索引的IO和数据的IO落在不同的物理磁盘上，减少竞争。至于“Oracle视图加索引”，严格来说普通视图是虚拟表，本身不存储数据，不能直接建索引；需要预先物化的物化视图支持建立索引。看到网上有人问能不能给普通视图加索引，答案是不行，要给视图对应的基表加。
最后分享一个排查索引问题的个人习惯
我每次接手一个慢查询，不是先看SQL，而是先看表结构里的索引列表和explain结果。先算出key_len，判断联合索引到底用到了哪一列；再看Extra里有没有Using filesort或Using temporary——这两项出现意味着索引的有序性没有被利用，排序和分组走了临时文件，代价极大。最后才回去看SQL条件，从B+树的有序性出发推导哪些条件下能索引定位、哪些只能索引扫描。这套流程走下来，90%的索引失效问题都能定位到根因，而不是靠猜。索引数据结构这个知识点，在面试里是考点，在真实线上环境里是救命稻草。把树的排序逻辑彻底想透，建索引就不再是一件靠经验堆出来的事。
