别的不敢说只要是干过后端开发或者跟数据库打过交道的朋友一定被问过这么一个问题MySQL的索引底层到底用的什么数据结构每次看到这类面试题我都觉得很多人只是背了个B树的结论真要问一句为什么是B树而不是红黑树、不是哈希表、不是B树能讲清楚的人就不多了。这篇博客我就把这些东西好好捋一遍从磁盘IO的物理限制讲到B树的设计动机从聚簇索引讲到回表从最左前缀讲到索引失效最后把EXPLAIN和常用的排查手段也带上争取让你看完之后既能在面试里接得住为什么也能在真实的慢SQL优化里知道从哪里下手。我自己做后端也有快十年了踩过的索引坑不计其数。有时候一个接口慢到报警查下来就是少了联合索引有时候加了索引反而变慢原因是优化器没走索引或者走了索引但回表次数爆炸。这类问题基本都集中在不懂底层原理上。所以这篇文章不会只讲结论会把每一个关键选择背后的权衡都拆开来看希望你能真正理解索引到底是靠什么在加速又是在哪些场景下会失灵。1. 为什么索引能快从数据存储说起要搞明白索引为什么快首先得搞清楚一个基础问题数据是放在哪里的CPU又是怎么拿到数据的。很多人觉得数据库查询慢是数据太多、遍历太慢但真正卡脖子的地方往往是磁盘IO和内存之间的速度差。1.1 磁盘IO和内存之间的鸿沟现在的服务器内存读写速度大概是几十纳秒到一百纳秒级别而一块普通的SSD随机读大概在几十微秒到几百微秒级别机械硬盘更是要好几毫秒。这个差距有多大呢打个比方如果CPU执行一条指令是1秒钟那么从内存读数据就相当于从书桌上拿一本书而从磁盘读数据就相当于跑到楼下图书馆借书机械硬盘则相当于把书送到外地去复印。数据库里的数据量一大不可能全放内存绝大部分数据都躺在磁盘上所以一次查询的耗时很大程度取决于发生了多少次磁盘IO。InnoDB在这里的设计很巧妙它把数据划分成一个个16KB的页Page每次磁盘IO至少读写一个完整的页而不是读一条记录。这个页就是InnoDB和磁盘交互的最小单位。换句话说你查一条记录磁盘给你的是一个16KB的数据页哪怕这个页里只有一条你想要的记录。理解这一点很重要因为索引结构的设计本质上就是在围绕如何用最少的磁盘IO次数找到目标记录做文章。1.2 没有索引时查找是怎么做的没有索引的时候MySQL只能走全表扫描。全表扫描的流程很简单从表空间的第一个数据页开始一个页一个页地读进内存然后在每个页里逐行比对。假设一张表有1000万条记录每条记录100字节那总数据量大约是1GB按16KB一页算就是65536个页每次查询要把这65536个页全部读一遍。就算每个页都在磁盘上连续存放顺序读一个机械盘上的大文件速度还能接受但如果数据页分散在不同位置随机IO的代价就大得离谱。更麻烦的是这种全表扫描的时间复杂度是O(N)表数据翻一倍查询时间基本也翻一倍。业务表一旦上了量级这种线性增长谁都扛不住。索引做的事情其实很朴素它额外维护一种紧凑的有序结构让你不需要从头扫到尾而是通过这个结构快速定位到目标数据所在的页再用几次IO把页捞上来。所以索引的核心目标是两件事第一尽量降低查询的IO次数第二让查询时间复杂度和数据总量解耦从O(N)变成O(log N)级别。2. 索引可选的底层结构为什么最后选了B树知道索引要解决IO问题之后我们来看看MySQL在众多数据结构里是怎么选的。这里就不得不提哈希表、二叉树、红黑树、B树和B树这几兄弟了。只有把它们的优缺点都捋一遍你才能理解InnoDB为什么用B树不是偶然而是一道精心计算的取舍题。2.1 哈希索引等值查询的天花板哈希索引应该是最好理解的一种结构了。它对索引键做哈希函数运算算出一个桶的位置然后在桶里找目标记录。理论上来讲一次哈希定位就能找到数据所在的页时间复杂度趋近于O(1)这比B树的O(log N)还要快。那为什么MySQL默认的InnoDB索引不是哈希索引呢因为哈希结构天生解决不了范围查询和排序。你要查age between 25 and 30哈希表里的键是散列的落在各个桶里根本没法直接按顺序扫出来只能一个一个键去算哈希再访问本质上退化成了等值查询的叠加。索引键要用来排序时也是一样哈希后的结果没有任何有序性可言连age 25这种最基础的过滤条件都没法走索引。InnoDB里确实存在哈希索引但它是自适应哈希索引是存储引擎在运行时根据热点查询自动构建的而且它建立在B树之上相当于给B树加了一层缓存加速。也就是说它的角色是辅助不是替代。我们平时建索引用的BTREE指的就是B树。2.2 二叉树和红黑树会遇到更尴尬的场景有人可能会想既然哈希搞不了范围查询那用二叉搜索树呢二叉搜索树在理想情况下查找复杂度是O(log N)而且中序遍历就能得到有序序列看起来挺合适。问题在于二叉搜索树的性能高度依赖树的形状。如果插入的记录是按照递增顺序来的比如主键自增1、2、3、4...二叉搜索树会退化成一条链表查找复杂度直接变回O(N)。数据库的写入是有顺序的主键自增更是常态所以这种退化并不是小概率事件而是必然会发生。红黑树是平衡二叉树的代表它通过旋转保持了树的大致平衡树高能维持在log N的水平。回到我们的场景里InnoDB一页16KB可以存放很多记录。如果用红黑树当索引每个节点只存一条记录的键值和指向子节点的指针树的高度依然很高。假设表有1000万条记录log2(1000万)大约等于24也就是说查找一次要走24层每层都是一次磁盘IO最少24次读盘。对比下面要说的B树三四层搞定这个差距就很明显了。红黑树在内存里的数据结构比如TreeMap、TreeSet里很好用但放到磁盘场景下过高的树高导致的IO次数是不可接受的。2.3 B树与B树的区别关键在数据存放位置上B树Balance Tree是多路搜索树一个节点可以存多个键值和多个子节点指针每个节点的大小通常设计成一个磁盘页。这样树的高度被大幅压缩三层B树就能支撑千万级甚至上亿级别的数据量查找的时候磁盘IO次数也就三次左右。B树是在B树之上做了两处关键调整。第一B树的非叶子节点只存键值不存数据而B树的非叶子节点既存键值又存数据。第二B树的叶子节点之间通过双向链表连接所有叶子节点形成一条有序链表。这两处调整解决了两个大问题。首先是页利用率问题。B树的每个节点都要存数据数据一大一个页能容纳的子节点数量就变少树的高度随之增加。B树非叶子节点不存数据只存键和指针一个16KB的页能放成千上万个键值树的扇出系数特别大三层左右就能撑住海量数据。其次是范围查询的效率。B树要范围查询时需要在各个节点之间反复跳转B树呢先搜索到范围起点对应的叶子节点然后顺着叶子节点的双向链表往后扫就行一次顺序扫描搞定。这也是MySQL范围查询、排序能够高效走索引的根本原因。2.4 B树的页面结构和双向链表B树的非叶子节点里存的是键值子节点页号相当于目录。叶子节点存的是键值记录位置或记录本身相当于正文。整个搜索过程就是先查目录一层层缩小范围最后落到包含目标记录的叶子页里。为什么叶子节点要用双向链表这是因为MySQL的索引在叶子节点这一层是有序排列的而且相邻节点之间用前驱指针和后继指针连起来。范围查询和ORDER BY的时候找到边界之后顺着链表依次读页能做顺序IO而不是随机IO效率提升是数量级的。举个例子执行SELECT * FROM t WHERE id BETWEEN 100 AND 200如果索引叶子节点是链表结构找到id100的叶子页之后后面的页面都可以按顺序读如果叶子节点之间没有连接就得一次一次跳到父节点再下来IO次数就难看了。还有一个容易被忽略的细节是页分裂和页合并。B树作为平衡树在插入删除时要维持树的平衡数据页存满了就要发生页分裂把一部分记录挪到新页里同时更新父节点的索引键删除数据导致页利用率过低时会发生页合并。页分裂和页合并本身是正常的维护行为但频繁发生时会导致索引碎片变多、写放大严重。这些内容后面实操部分会再讲到。3. MySQL InnoDB里索引到底长什么样理解了B树的通用结构之后我们回到InnoDB这个具体的存储引擎来看。InnoDB里的索引分为聚簇索引、二级索引和联合索引它们都是B树但组织方式有区别。很多开发者在实际工作中分不清主键索引和二级索引的区别查数据的时候回表这个概念也经常一知半解这些都必须掰开讲清楚。3.1 聚簇索引数据就是索引索引就是数据InnoDB的表数据本身就是按主键建立的B树来组织的。这棵B树的叶子节点直接存放整行的完整记录也就是说主键索引的叶子节点就是数据行本身不再需要额外引用回表。这种索引我们称为聚簇索引Clustered Index也叫主键索引。正因为叶子节点存的是完整数据行InnoDB的表只能是数据跟着主键走的形态。每张InnoDB表只能有一个聚簇索引因为一份数据只能有一种物理排列方式。如果你建表时没有定义主键InnoDB会先找表中第一个非空的唯一索引来当聚簇索引要是连唯一索引都没有就自动生成一个6字节的隐藏主键ROW_ID来当聚簇索引。这个隐藏主键你平时是碰不到的但它确实存在而且用不上它的时候你的表反而容易产生一些隐性的性能问题。这里有一个非常重要的推论二级索引的叶子节点存的不可能是完整数据行只能存主键值。所以走二级索引查数据的时候通常需要拿着主键值再回到主键索引里再查一次这个过程就是回表。一张表只有一个聚簇索引也就决定了它的数据只能有一份、只能按一种顺序物理排列其他索引只能作为辅助。3.2 二级索引与回表为什么会有额外IO二级索引也叫辅助索引或普通索引它的B树结构和聚簇索引类似叶子节点里存的不是完整记录而是索引键值主键值。比如你在员工表的name字段上建了一个索引这棵B树的叶子节点就存放了name和各种name对应的主键id。当查询条件是WHERE name 张三时MySQL可以在二级索引树里快速找到name张三的叶子节点拿到那条记录的主键id然后拿着这个id再去主键索引聚簇索引里查完整行。这个过程叫回表。回表到底慢不慢取决于你要查多少条记录。如果WHERE name LIKE 张%命中了5000个名字二级索引查询会先通过索引树找到这5000个主键id然后这5000个id可能分布在各个不同的数据页里意味着最多可能触发5000次随机IO来查找数据行。这个代价是非常高的也是为什么很多优化建议里都强调减少回表次数。要想减少回表最直接的办法就是用覆盖索引后面会专门讲。还有一个思路是控制返回行数因为一条慢查询往往不是索引查找本身慢而是回表次数太多、随机IO太多。3.3 联合索引和最左前缀顺序就是一切联合索引就是在多个列上建一个B树索引比如(a, b, c)三列联合索引。这棵B树的排序规则非常关键先按a排序a相同的情况下按b排序b也相同的情况下按c排序。也就是说联合索引的排序规则是有严格顺序的这直接决定了最左前缀原则。最左前缀原则的意思是如果你建的是(a, b, c)联合索引那么查询条件里包含a时能走索引不包含a时无法走索引。WHERE b 1 AND c 2这种没有a的查询就用不上这个索引因为B树在全局上是按a排好序的没有a这个前缀b和c整体上是无序的没法二分查找。我见过很多同事建联合索引时顺手写WHERE c1 AND b2以为没走最左前缀就失效了。实际上MySQL优化器会做条件重排调整WHERE条件顺序只要b2 AND c1这个组合里包含索引最左边的列就可以走索引。真正决定能不能走索引的是查询条件的列有没有包含联合索引的第一个列而不是WHERE里书写的顺序。还有一个点很容易被忽略联合索引里的中间列如果被范围查询打断后面的列就发挥不了索引的作用。比如(a, b, c)索引查询WHERE a 1 AND b 10 AND c 5a可以用等值定位b可以用范围扫但c没法在b的范围扫描中继续走索引只能作为回表后过滤或者索引内过滤来处理。所以在设计联合索引时等值判断的列要放在前面范围查询的列放在后面。3.4 覆盖索引和索引下推减少回表的两个利器覆盖索引是指查询的列全部在索引树里就能拿到不需要回表。比如你建了(name, age)联合索引执行SELECT age FROM t WHERE name 张三在二级索引的叶子节点里既有name又有age还有主键id查询要返回的列age不需要再去主键索引里取这就是覆盖索引。它的价值在于把查完索引还要回表变成了查完索引直接返回省掉了大量随机IO。判断一个查询是不是覆盖索引最简单的方法是看EXPLAIN结果里Extra列是否出现Using index。如果出现了就说明这一步查询所需的数据直接从索引树上取没有回表。索引下推Index Condition Pushdown简称ICP是MySQL 5.6引入的优化它允许在二级索引遍历过程中先把一些WHERE条件里能判断的列下推给存储引擎在索引读取阶段提前过滤掉不满足条件的记录。没有ICP的时候InnoDB只能根据索引键把命中的记录全部回表取回完整行后再在Server层做过滤回表次数会多很多。有了ICP一些过滤操作能在索引遍历阶段完成回表次数大幅下降。你在EXPLAIN里看到Extra列有Using index condition就说明这条路走的是索引下推。要注意的是覆盖索引和索引下推不是一回事但它们的目标是一样的少回表、少IO。实际做SQL优化的时候我都会先看能不能用覆盖索引直接解决问题不行的话再看能不能用联合索引配合ICP减少回表范围。4. 索引失效场景的底层原理解读很多人对索引的理解停留在建了索引查得就快这个层面遇到慢查询加索引没用就开始乱猜。其实索引失效并不是玄学底层逻辑都是因为破坏了B树的有序性或破坏了索引键的定位能力。搞明白这些原理你就能判断一条SQL该不该优化、怎么优化。4.1 函数运算导致索引失效在索引列上做函数运算是一个很经典的失效场景。假设name列上有索引执行WHERE UPPER(name) ZHANG问题出在哪B树里存储的索引键是原始name值排序也是按原始字符串的字符顺序排的。当查询把条件改成UPPER(name)后MySQL需要先对每一行的name做一次UPPER运算再和ZHANG比较。问题是索引键里根本没有UPPER(name)这个值的有序序列B树没法直接定位所以优化器只能放弃索引改成全表扫描。有人会问MySQL 8.0不是支持函数索引吗是的MySQL 8.0之后你可以直接建CREATE INDEX idx_upper_name ON t ((UPPER(name)))这样虚拟列上会生成独立的索引键B树里按UPPER(name)排序就能走索引了。原理不是MySQL开窍了而是你额外存了一份函数结果的排序值。4.2 隐式类型转换隐式类型转换是另一个隐藏很深的问题。比如user_id列是varchar类型你执行WHERE user_id 10086MySQL会把varchar列转成数字去比较还是反过来这里有一个关键规则当字符串列和数字比较时MySQL会把字符串转换为数字进行比较。转换之后索引列user_id上相当于做了一次CAST(user_id AS SIGNED)函数运算导致索引失效。在实际排查中这种问题特别容易发生在字段类型设计为varchar但存的是数字的表上。建表时图省事把id、phone全建成varchar然后查询时写WHERE phone 13800138000看起来很正常其实每次查询都全表扫描。解决办法说起来很简单查询参数写成字符串WHERE phone 13800138000或者更彻底一点把字段类型改成bigint。用EXPLAIN看key列是否变成NULL就知道了。4.3 范围查询打断联合索引范围查询导致联合索引后面的列失效是大家容易搞混的。前面提过联合索引(a, b, c)查询WHERE a 1 AND b 10 AND c 5时a能精确定位b能范围扫c就走不了索引了。这是因为B树的排序是先按a排再按b排最后按c排。b 10之后扫描到的所有b都是大于10的但它们在c这个维度上并没有排好序因为排序的第二关键字已经被范围条件限制住了c的有序性只存在于b相同的情况下。这种场景不是索引完全失效而是部分失效。优化方案有两个一是调整索引列为(a, c, b)让等值条件的c在范围条件的b前面这样c也能走索引二是如果c的过滤效果很好可以考虑在c上单独建索引。当然具体怎么做要结合实际情况但底层原理都是一样的B树叶子的有序性是在多个键值按顺序叠加下形成的范围条件会破坏后面字段的有序性。4.4 排序与索引Filesort在什么时候出现ORDER BY能不能走索引同样取决于B树的叶子节点有序性。如果查询的排序字段恰好是索引的顺序MySQL就能直接按索引顺序读取不需要额外的排序操作EXPLAIN里不会出现Using filesort。反过来如果排序字段和索引顺序对不上MySQL就得先把结果集取出来再用内存或磁盘来排序这就是Using filesort。有一个常见的误解ORDER BY a在(a, b, c)联合索引上是不是一定能走索引分情况讨论。如果查询条件里WHERE a 1那么ORDER BY b也能走索引因为a确定之后b仍然是有序的。如果查询条件里WHERE a 1 AND b 10那么ORDER BY c就未必能走索引了因为b被范围条件打破之后c的无序性再次出现。所以判断排序能否走索引的通用方法是看排序字段是否和当前索引扫描段内的一致等值条件算确定范围条件算打破。另外还有一个微妙的地方是排序方向和索引方向要一致。B树叶子链表通常是按索引键升序排列的如果你ORDER BY a DESCMySQL要么反向扫描链表要么做filesort。反向扫描在某些情况下可行但如果同时又夹杂了多字段排序方向不一致比如ORDER BY a ASC, b DESC索引序就派不上用场了。设计索引时如果明确知道排序需求把索引定义成(a ASC, b DESC)这种混合序在MySQL 8.0里是可以做到的。5. 实操建索引与排查索引问题讲了这么多原理最后落到实操。这一部分我会把建索引的核心参数、EXPLAIN怎么看、常见问题速查和排查方法讲清楚都是可以直接拿去用的经验。5.1 核心索引参数说明建索引最基础的语句是CREATE [UNIQUE] INDEX index_name ON table_name (col1, col2, ...);如果建表时就要建索引可以直接写在DDL里CREATE TABLE user ( id BIGINT PRIMARY KEY AUTO_INCREMENT, name VARCHAR(50) NOT NULL, age INT NOT NULL, KEY idx_name_age (name, age) ) ENGINEInnoDB;这里有几个参数要注意。UNIQUE表示唯一索引用来约束业务上的唯一性同时也能加速等值查找。索引可以指定前缀长度比如KEY idx_name (name(10))只对name的前10个字符建索引好处是减少索引占用空间坏处是精度降低一些短的尾部不同的值没法精确过滤。对于超长的VARCHAR/TEXT列前缀索引几乎是必须的。如果列允许NULLB树里NULL值的处理方式和普通值不同索引会失效吗不会但多列索引里一个NULL会让很多判断变得麻烦实际设计时尽量给索引列加上NOT NULL约束。还有一个参数是索引的可见性MySQL 8.0引入了INVISIBLE索引建了之后优化器默认不用它只在显式开启情况下才考虑。这个功能在打算删除某个索引又不确定有没有影响的时候特别好用。先设为INVISIBLE跑一段时间的生产流量确认没有慢SQL后再真正删除。5.2 Explain执行计划怎么看排查慢SQL的第一步永远是EXPLAIN。语法很简单直接在SQL前面加EXPLAIN关键字MySQL会给你一张执行计划表。重点看这几列列名含义重点关注type访问类型从好到差依次是system const eq_ref ref range index ALL至少要到range最好到refkey实际用到的索引名如果是NULL说明没走索引key_len索引使用的字节数能算出联合索引用了哪几列rows预估扫描行数越小越好用于评估是否大面积回表Extra附加信息Using index、Using index condition、Using filesort、Using temporary 需要重点注意type列里const和eq_ref是等值查询的理想状态ref也还行range代表扫描了一个范围index是扫描了全索引树ALL是全表扫描。看到ALL或者key为NULL基本就可以判断这条SQL需要优化了。key_len的计算值得单独讲一下。它表示MySQL在索引里实际用了多少字节。假设有一个联合索引(a, b)a是int类型4字节且非空b是varchar(20)且非空那么key_len 4 204 2 86。其中204是因为utf8mb4字符集下一个字符最多占4字节2是varchar长度标识占用。如果查询条件只用了a列key_len就只会是4。所以看key_len你就能判断联合索引到底用到了几个字段就明白索引是不是因为范围查询被打断了。5.3 常见问题速查与避坑经验在实际使用中有几类问题是特别高频出现的我整理成一个速查表方便你直接对照。问题可能原因解决方案查询很慢但明明建了索引索引列上有隐式类型转换或函数运算用EXPLAIN看key是否为NULL修正WHERE写法联合索引只用了前面一列查询条件没带最左列或中间列有范围查询调整查询条件、调整索引列顺序排序慢出现Using filesort排序字段和索引顺序不匹配设计专用排序索引或让排序字段参与联合索引回表次数过多查询列不在索引中改成覆盖索引即把查询字段放进索引里出现Using temporary分组或去重字段无索引在GROUP BY/DISTINCT字段上建索引索引很大、写变慢索引列数太多或建了冗余索引删除重复索引压缩索引长度必要时用前缀索引数据频繁插入删除后变慢页分裂和碎片变多用ALTER TABLE t ENGINEInnoDB重建表或者配合OPTIMIZE TABLE整理碎片这里说两个我踩过的坑。第一个坑是我曾经给订单表建了一个五列的联合索引覆盖了所有查询场景看起来非常完美。结果上线之后写入变慢因为每次插入都要维护一棵五列组成的B树页面分裂频繁主键的随机IO也多了。后来我把联合索引拆成了两个三列的写压力立刻降下来了。索引不是越多越好、越宽越好每个索引都是写入放大尤其是高频写入的业务表宁可多建几个窄索引也不要追求一个万能索引。第二个坑是关于排序的。有一个报表查询ORDER BY create_time DESCcreate_time上明明有索引但EXPLAIN里依然出现了Using filesort。排查之后发现是因为前面多加了一个WHERE status 1的过滤条件而status不参与create_time索引导致最终排序集合不是按create_time排列的。后来我把索引改成了(status, create_time)优化器先按status定位再按create_time顺序扫描filesort直接消失查询时间从2.8秒降到了0.1秒。这个故事说明排序能不能走索引不只看排序字段是否有索引还要看它和WHERE条件在同一个索引里是否能构成有序序列。5.4 索引维护与监控的实用建议最后聊一下日常维护层面的经验。索引不是建完就能一劳永逸的业务在变查询模式也在变。我一般会定期做三件事。第一件事是做慢日志分析。把long_query_time设成1秒甚至0.5秒定期捞慢日志按SQL去重、按执行频率排序优先排查那些频率高且耗时长的查询。这类查询每慢一点累积起来都可能是容量问题。第二件事是检查索引基数Cardinality。用SHOW INDEX FROM table_name可以看每个索引的基数如果Cardinality明显小于表行数说明这个索引的区分度不高比如性别列上建索引基数撑死就两个值优化器很可能直接放弃索引。对区分度低的列建索引既占空间又没有实际效果。第三件事是善用索引统计信息更新。InnoDB的索引统计信息不是实时更新的有时候表数据发生剧烈变化后优化器还会拿旧的统计信息做决策导致走了很差的执行计划。可以执行ANALYZE TABLE table_name来更新统计信息让优化器重新评估。很多时候一条SQL突然变慢不是因为索引坏了而是统计信息过期了。我个人在实际操作中还有一个体会排查索引问题永远比优化索引写法更花时间。花半小时搞清楚一条慢SQL到底卡在哪一步远比盲目加索引、删索引要有效得多。EXPLAIN里的每一列都有意义真正花功夫读懂它很多性能问题解决起来就是几分钟的事。希望这篇文章不只是让你记住了B树更让你在以后遇到一条慢查询时能自己动手分析出它慢在哪、索引帮了什么忙、又为什么没帮上忙。