去年线上有一张2000多万行的订单表接口偶尔会慢到3秒多。查了一眼慢日志SQL条件就两个字段user_id 和 status关键是这两个字段上也确实建了联合索引。explain 一看type 直接是 ALL整条 SQL 在走全表扫描。当时同事第一反应是“是不是要加 force index”我按住了他索引能不能被用上从来不是靠 force 解决的而是要看 mysql索引 的底层数据结构与算法是怎么设计的。B树长什么样、联合索引内部怎么排序、优化器怎么算成本这三件事搞清楚了90% 的索引问题都不用猜。这篇就顺着底层数据结构这条线把索引“为什么快”“为什么有时慢”“到底怎么建才算对”这几个问题聊透。适合天天写 CRUD 但没时间翻源码的后端开发也适合正在准备算法面试、想用一句话说清“数据库为什么选 B树而不是红黑树”的人。看完以后你应该能自己回答where a and b 到底怎么建索引、自增主键为什么好、一次全表扫描要读多少次磁盘——这些网上被问烂了的题答案其实都能从数据结构里推出来。1. 索引的本质一次磁盘IO的减法1.1 全表扫描到底要读多少数据很多人对“全表扫描很慢”没有体感因为平时 CRUD 的数据量太小。你可以算一笔账一张 2000 万行的订单表假设平均一行 0.5KB 到 1KB整张表就是 10GB 到 20GB。MySQL 的 InnoDB 存储引擎默认一页 16KB也就是说这张表要占大约 65 万到 130 万个数据页。一次全表扫描就得把这些页从头到尾读一遍。就算用的是 SSD顺序读大量数据也要吃掉不少带宽和时间如果遇到随机 IO、内存命中率不高的情况那就更糟糕了。你想想一个查询本来只想要某几个用户的订单结果数据库把整张表的页都翻了一遍这不就是拿着整本电话簿找一个号码吗这里有个很关键的概念InnoDB 读写磁盘的最小单位是页不是行。你想读一行数据数据库实际会把包含这一行的整个 16KB 页加载到内存。所以查询的成本本质上是“要读多少个页”的成本而不是“要读多少行”的成本。索引的价值就在于把“读几十万页”压缩成“读几个页”。1.2 数据页磁盘和内存交换的最小单位可以把数据页理解成一个装满记录的箱子。箱子固定在仓库里位置按页号排好。你要找一条记录如果不知道它在哪个箱子就只能把仓库从头到尾翻一遍如果知道它在 10086 号箱子那就只需要把这个箱子搬出来在箱子内部再翻一下。InnoDB 的 B树索引就是那个“份仓库地图”。它不直接告诉你记录在哪一行而是告诉你“你要的记录大概在哪个叶子页里”然后把范围一步步缩小。叶子页之间又通过链表串在一起所以范围查询也能顺着链表往后拖。“读几个页”和“读几百个页”的差距就是索引最核心的收益来源。这也是后文所有数据结构选型的出发点——任何看起来很高级的数据结构如果不能在“减少磁盘页访问次数”这件事上胜出在数据库场景里都是花瓶。1.3 索引把一个查找问题变成了数层高问题在没有索引的情况下MySQL 做等值查询只能遍历在有了 B树索引之后查找就变成了“从根节点开始逐层判断走哪个子节点最后落到叶子页”。这个过程每一层只需要读一个页。于是问题就变成了B树到底有几层层数多IO 次数多层数少IO 次数就少。这也是为什么数据库选择了“矮胖”的树而不是“高瘦”的树。下一节就把候选数据结构挨个拿出来比一比你会发现淘汰过程非常有意思。2. 候选结构逐个淘汰为什么最后留下的是 B树2.1 哈希索引等值查询最快但范围查询直接出局很多人第一次接触索引时都会问为什么不用哈希表哈希表的等值查询是 O(1)比树的 O(logN) 还快听着就很理想。哈希索引确实适合等值查询比如 where id 123。它把键值通过哈希函数换算成桶的位置一次就能定位。问题出在数据库查询远不止等值这一种范围查询大于、小于、between、排序order by、前缀匹配like abc%都是家常便饭。哈希表的数据是无序的这些查询全都没法高效完成。你总不能为了一个范围查询把哈希表整个扫一遍再一个个判断吧所以 InnoDB 里的哈希索引只是“配角”。它有一个自适应哈希索引机制在内存里自动为高频访问的 B树页面建哈希索引用来加速某些等值查询。但这层哈希只是 B树之上的缓存加速真正的索引结构还是 B树。这一点很多文章没讲透导致有人误以为“InnoDB 支持哈希索引所以可以用哈希当索引”这是不对的。2.2 二叉查找树和红黑树平衡了但树高压不住二叉查找树的查找复杂度是 O(logN)如果数据随机插入效果还行。但数据库的插入往往是递增的比如自增主键这时候二叉查找树会退化成一条链表查找复杂度直接变成 O(N)。你说这不就废了吗于是有了 AVL 树和红黑树这样的平衡树。它们通过旋转来维持左右子树高度差保证最坏情况下也是 O(logN)。单看算法复杂度1000 万行数据树高大约 24 层每层一次磁盘 IO也就 24 次看起来可以接受。但你算一下空间二叉树的每个节点只存一个键值1000 万行就需要 1000 万个节点每访问一层加载一个页而每个页只利用了一个节点里的一点数据页的利用率极低。更麻烦的是红黑树虽然平衡但高度上限是 2log(N1)1000 万行时可能到 40 多层也就是 40 多次磁盘 IO。IO 是数据库最大的成本这个数字完全压不住。平衡树确实解决了“退化”问题但没解决“矮”的问题。还有一个隐蔽问题树节点之间没有天然的连续顺序。你要做范围查询比如查出 id 在 100 到 200 之间的所有数据二叉树需要中序遍历可能要来回跳多个节点产生大量随机 IO。2.3 B树与B树关键差异决定了最后赢家B树是“多路搜索树”每个节点可以存多个键和多个子指针。正是“一个节点存多个键”这个特性让 B树能长得很矮。16KB 的页可以塞下很多个键值对一个节点就是一个页一次 IO 就能判断一批分支。树的层数压到 3 到 4 层查找一个数据最多 3 到 4 次 IO这才是数据库能接受的成本。但 B树还有个问题它的非叶子节点也会存数据记录。这样每个节点能存的分支数就少了因为数据行通常很大。如果数据行占 500 字节16KB 的页也就存 30 行间接导致树变高。而且范围查询依然麻烦需要在中序遍历中不断回溯父节点。B树做了两个关键改进第一非叶子节点只存索引键和子指针不存数据这样每个非叶子页能容纳的分支数量大增树更矮第二所有数据都放在叶子节点并且叶子节点之间用链表串起来。范围查询找到起点后直接顺着链表往后拖就行不需要中序回溯。这两个差异让 B树在数据库场景下几乎是必然选择。2.4 3层B树到底能存多少数据拿数字说话。假设索引键加指针一共占 14 字节一个 16KB 的页大约能存 1170 个分支。3 层的 B树最上面是根节点第二层有 1170 个内层节点第三层叶子节点就有 1170 乘以 1170约 136 万个页。如果每个叶子页能放 15 行数据对应平均行大小 1KB 左右这棵 3 层的 B树就能支撑约 2000 万行数据。也就是说2000 万行的表走主键索引查询一般只需要 3 次磁盘 IO 就能定位到目标页。索引生效时3 次 IO 和全表扫描 60 万次 IO 的差距就是体感和超时的差距。这里要注意上面是量级估算真实情况会受行大小、页填充率、键长度影响。但量级判断足够让你理解B树设计的核心目标就是“层数少、扇出大、叶子连续”。结构等值查询范围查询排序磁盘IO次数量级结论哈希表最快不支持不支持1次定位不适合做通用索引二叉/AVL/红黑树好较差较差20~40层树太高IO压不住B树好一般一般3~4层非叶子存数据浪费扇出B树好好好3~4层数据库主流选择3. 聚簇索引与二级索引InnoDB里的索引真实形态3.1 聚簇索引主键决定了数据的物理排列聊完理论层面的 B树再进入 InnoDB 的真实实现。InnoDB 里表数据本身就是按主键顺序存放在 B树叶子节点上的。这棵树的叶子节点存的是整行数据叫做聚簇索引。你可以理解成主键索引就是表本身而不是“表之外单独建了一个索引文件”。这个设计带来一个很实际的影响主键的选择直接决定了数据行的物理排列。自增主键插入时新记录总是追加到树的最右侧页分裂和碎片少写入性能稳定。而如果主键是 UUID 这类随机值插入时数据大概率落在已有页的中间InnoDB 需要频繁做页分裂、移动数据产生大量随机写入同时聚簇索引碎片化明显查询时也可能多读不少页。网上常说“主键不要用 UUID”根子就在这里。如果建表时没有显式定义主键InnoDB 会找第一个非空唯一索引作为聚簇索引实在找不到就会生成一个隐式的 ROW_ID 当主键。这个隐式主键对业务不可见也不可控所以我建议每个表都主动设计好主键别把命运交给隐式 ROW_ID。3.2 二级索引叶子为什么存主键而不是行指针二级索引非聚簇索引的叶子节点不存整行数据存的是索引键值加主键值。等值查询一条二级索引先找到目标索引键取到主键再拿主键回聚簇索引里查整行。这个“再查一次”的动作叫回表。那为什么二级索引叶子不直接存数据行指针如果存的是数据行的物理地址页分裂之后数据行移到别处所有二级索引都得跟着更新代价太大。而主键值在逻辑上是稳定的只要业务不主动改主键二级索引里的“定位线索”就始终有效。这本质上是一个“用稳定逻辑标识替代易变物理位置”的设计决策。明白了这个你就知道为什么二级索引里多存几个列会占额外空间以及为什么“使用覆盖索引”能省掉回表这一步——只要查询需要的列都已经包含在二级索引里MySQL 就不需要再回聚簇索引了。3.3 回表与覆盖索引Using index 的含金量举个例子。表里有联合索引 (user_id, status)你执行SELECT user_id, status FROM orders WHERE user_id 10086;这条查询需要的两列都在联合索引里MySQL 直接在二级索引的 B树上就能拿到结果不需要回表。这在 explain 的 Extra 列里会显示 Using index意思是“覆盖索引生效了”。再看这条SELECT * FROM orders WHERE user_id 10086;因为 select * 需要所有列而二级索引里没存这些列MySQL 只能查到主键后回表把整行读出来。Extra 里就不会有 Using index而是可能出现 Using index condition如果有索引条件下推或者什么都没有。覆盖索引是查询优化的利器能有效减少回表 IO。但也要注意度覆盖索引本质上是“把查询需要用到的列都塞进二级索引”塞太多列索引体积变大写入更新成本也跟着涨不能为了覆盖而无脑扩大联合索引范围。3.4 索引下推把过滤尽量留在二级索引里MySQL 5.6 引入了一个很容易被忽略但非常实用的优化索引下推Index Condition PushdownICP。它解决的问题是当二级索引无法完全定位所有满足条件的行时能不能尽量在二级索引内部多做一点过滤减少回表次数。打个比方联合索引是 (last_name, first_name)你要查姓“张”且名字里带“三”的人。联合索引只能帮你先定位到所有姓“张”的叶子节点如果没有 ICPMySQL 会把所有姓“张”的记录都回表再在聚簇索引里判断 first_name 是否包含“三”。有了 ICP存储引擎在扫描二级索引时就会先对 first_name 做一次过滤过滤不掉的才回表。回表次数大幅减少查询自然变快。explain 里只要看到 Extra 为 Using index condition就说明这条 SQL 吃到了 ICP 的优化。注意 ICP 不等于覆盖索引它不能完全消灭回表只是减少回表次数真正想彻底免回表还是得靠覆盖索引。场景Extra 显示说明覆盖索引Using index查询列都在索引里无需回表索引下推Using index condition存储引擎先过滤再回表全表扫描无type 为 ALL索引没起到作用4. 联合索引与最左前缀where a and b 为什么还是慢4.1 联合索引内部的排序规则联合索引的底层数据结构依然是 B树但叶子节点的排序规则变成了“先按第一列排第一列相同再按第二列排以此类推”。这和字典的排序逻辑很像先看姓再看名。假设有联合索引 (a, b, c)B树里的顺序大致是a 不同的记录a 值小的在前a 相同的记录再按 b 排序a 和 b 都相同才轮到 c 起作用。这个排序规则决定了你能怎么用这个索引。查询 if 条件只包含第一列或者“第一列加第二列”或者“第一列加第二列加第三列”都能利用索引的顺序去定位。但如果查询条件直接跳过第一列只用到第二列索引排序对你就毫无帮助因为整棵树的顺序不是按第二列排的。4.2 最左前缀的边界条件跳过中间列会发生什么最左前缀原则常被说成“查询条件必须从索引最左列开始”。更准确的说法是如果一个查询条件用到了联合索引的某几列那这些列在条件中必须从最左侧开始连续出现等值或范围索引才可能被高效利用。比如联合索引 (a, b, c)where a 1用到索引最左前缀 a。where a 1 and b 2用到索引前缀 a、b。where a 1 and b 2 and c 3用到索引完整的三个列。where b 2不能高效用索引因为跳过了 a。where a 1 and c 3只有 a 能用到索引定位c 没法利用索引排序去找。为什么 where a 1 and c 3 时 c 用不上很简单联合索引先按 a 排序再按 b 排序最后才按 c 排序。你有 a 的等值条件能把查找范围迅速缩到“a 等于 1”的一批记录上但这一批记录内部的顺序是按 b 排的c 在内部没有保持有序性可依赖自然没法继续用“二分定位”去查 c 3。4.3 范围条件会“折断”索引这是最常见的坑先看一个典型疑问联合索引 (a, b)查询 where a 100 and b 50为什么经常只走一半索引B树的联合索引先按 a 排再按 b 排。a 100 是一个范围MySQL 可以沿着 B树找到第一个满足 a 100 的叶子然后顺着链表往后扫。这期间 a 是递增的但相同 a 值内部的 b 才是局部有序的更准确地说在 a 不同值之间b 并没有全局顺序。所以 b 50 并不能像等值条件那样继续缩小扫描区间。这就是“范围条件后的列会失效”的本质原因。范围条件、、between、like abc% 这种前缀范围之后的列无法继续用于缩小索引扫描范围只能作为二级过滤条件。MySQL 8.0 里这些后续条件如果也能被索引包含通常会通过 ICP 在二级索引内部过滤一部分减少回表但扫描范围还是被范围条件撑大了。所以设计联合索引时要把等值条件放前面范围条件尽量放后面。如果是高频的范围查询字段和另一个等值字段组合优先把等值字段放第一列这样等值条件能把范围压到最小而不是一上来就让范围条件把扫描摊开。4.4 回到那个经典问题where a and b 到底怎么建索引热搜词里有人问“mysql where条件a and b应该怎么建索引”这是最典型的联合索引场景。假设查询是SELECT * FROM orders WHERE user_id 10086 AND status 1;正确的做法不是给 user_id 和 status 各建一个单列索引而是建一个联合索引 (user_id, status) 或 (status, user_id)。那到底谁放前面核心判断标准是区分度也就是这个列能筛掉多少数据。你可以用一条 SQL 估算SELECT COUNT(DISTINCT user_id) / COUNT(*) AS user_selectivity, COUNT(DISTINCT status) / COUNT(*) AS status_selectivity FROM orders;区分度高的列通常放前面因为它会先把搜索范围压得更小。比如 user_id 区分度高status 基本只有几个值那就建 (user_id, status)。但这里有个隐含前提如果 status 常被单独用来过滤或者你有其他 SQL 也需要 status 当头那 status 单独建索引或放在第一列也有价值。实际设计中要看你这个表最核心的几条查询路径是什么给主要矛盾做索引而不是给所有可能都做索引。如果两个条件都是等值联合索引的列顺序不改变查询能否命中只影响定位范围的大小。很多面试题把“选择性高的放前面”当绝对答案我觉得不够完整还得考虑这个索引能不能顺带覆盖其他高频查询、能不能消除排序。设计索引本质是在做多维度的取舍。4.5 order by 与 group by索引怎么帮忙消灭 filesort索引不止服务于 where也服务于排序。B树的叶子本身是有序的如果 order by 的顺序能和联合索引的列顺序匹配MySQL 直接按索引顺序读出来就行不需要额外的排序步骤。反之如果排序字段不在索引里或者排序方向和索引方向不匹配就会看到 Extra 里的 Using filesort。举例子联合索引 (user_id, status)SELECT * FROM orders WHERE user_id 10086 ORDER BY status;MySQL 可以先通过 user_id 10086 命中一组叶子记录而这组记录内部就是按 status 排好序的所以直接顺序读即可不使用 filesort。这既利用了 where又利用了排序一次索引解决两个问题。再看反例SELECT * FROM orders WHERE user_id 10086 ORDER BY create_time;create_time 不在联合索引里MySQL 必须先把数据取出来再排序于是 Extra 里出现 Using filesort。如果 create_time 是高频排序字段你可能需要单独建 (user_id, create_time) 的联合索引或者让上层业务接受一次排序开销。没有免费的午餐每多一个索引就多一份写入成本这是索引设计里最需要权衡的地方。5. MySQL 8.0索引新特性降序索引、不可见索引与函数索引5.1 降序索引排序方向不再被无视在 MySQL 8.0 之前索引定义里写 ASC 和 DESC 其实是一样的。联合索引的所有列不管是升序还是降序存储引擎都按升序存。这就带来一个尴尬场景索引是 (a ASC, b DESC)你的业务要 order by a ASC, b DESCMySQL 没法直接利用索引的排序方向只能先按索引顺序读出来再 filesort。MySQL 8.0 真正支持了降序索引。定义索引时声明 DESC 的列在 B树里确实按降序排列这样多列排序方向不一致的查询就可以直接走索引顺序不再需要 filesort。这个特性对“时间升序 状态降序”这类排序需求非常友好。如果你还在用 5.7 又想优化这类查询可以调整排序方向让排序字段尽可能全部升序或全部降序。这里也提醒一句降序索引同样会增加存储引擎维护成本只有明确碰到“多列混合排序”场景再考虑别为了炫技给所有列都加。5.2 不可见索引安全验证索引能不能删线上清理无用索引一直是件头疼事。你看到某个索引很久没人用想删掉又怕某个低频率业务突然暴雷。MySQL 8.0 提供了不可见索引把索引设为 INVISIBLE 后优化器在生成执行计划时不会考虑它但索引本身仍然存在并且会随数据更新继续维护。这个功能相当于给了索引一个“影子模式”。操作方式很简单ALTER TABLE orders ALTER INDEX idx_user_status INVISIBLE; ALTER TABLE orders ALTER INDEX idx_user_status VISIBLE;设成不可见后跑一段时间业务观察慢查询和线上现象。如果没有任何问题再真正 DROP如果发现问题立刻改回 VISIBLE。注意主键不能设为不可见因为主键的唯一性约束和聚簇结构都依赖它。这个手段在我优化线上索引时用过很多次比直接删除稳得多。5.3 函数索引从根源解决隐式转换和表达式失效很多“索引失效”问题的根源是查询条件里对索引列做了函数运算比如SELECT * FROM user WHERE LOWER(name) tom;索引存的是 name 原始值的排序顺序而条件要找的是 LOWER(name) 的等值匹配两者没法直接用上索引。MySQL 8.0.13 起支持函数索引你可以直接基于表达式建索引CREATE INDEX idx_lower_name ON user ((LOWER(name)));这样数据库就能按 LOWER(name) 的结果维护一棵额外的 B树上述查询自然走索引。类似的还有对日期函数、JSON 字段表达式做索引。代价是写入时要额外算函数值并维护索引空间和时间成本都会有所以函数索引只应该用在确有必要的高频查询场景。5.4 自适应哈希索引B树的专属加速器InnoDB 里有一个自适应哈希索引Adaptive Hash Index很多人会误解为“InnoDB 支持哈希索引可以直接建”。其实它不是你能自己建的那种索引而是 InnoDB 在内存中根据你对 B树索引的访问模式自动为高频访问的“页面”构建的哈希映射。它服务的对象是 B树的页命中后可以在内存里用 O(1) 的方式找到目标页而不用一次次从根节点走 B树路径。这个机制默认开启不需要人工干预。你可以通过 information_schema.INNODB_METRICS 观察它的命中率决定在极端压力下是否关闭innodb_adaptive_hash_indexOFF。但正常情况下你不应该也不需要手动去“建”它。理解了它和 B树的关系再回头看 2.1 节说的“哈希在 MySQL 里只是配角”就更清楚了。6. 一次索引失效的完整排查链路从explain到优化落地6.1 explain 输出应该怎么读四列定位问题我排查索引问题第一步永远是 explain。不需要把所有列背下来先看四列就够type访问类型。从好到差大致是 system const eq_ref ref range index ALL。ref 是等值条件下命中索引range 是范围扫描ALL 就是全表扫描。key实际使用了哪个索引。NULL 表示没走索引。rows优化器估算要扫描多少行。这个数字和真实数据量对比能快速判断成本。ExtraUsing index覆盖索引、Using index condition索引下推、Using filesort需要额外排序、Using temporary需要临时表。比如 type 是 ALLkey 是 NULLrows 接近全表行数那基本可以断定索引没生效问题不在索引数量而在查询写法或者列结构。6.2 一次隐式转换导致索引失效的完整复盘之前排查过一个线上问题user 表的 phone 列是 varchar查询条件是 where phone 138xxxxexplain 显示 typeALL 全表扫描。单独看 phone 列上有普通索引索引确实存在为什么没用问题出在参数类型上。Java 应用里传进来的是一个 Long 或 intMySQL 在比较时会把 varchar 列隐式转换成数字相当于在索引列上套了一层 CAST 函数。对列做函数运算B树的有序性就无从利用索引直接失效。排查链路是这样的先翻慢查询日志找到 SQLexplain 看到 ALL再看表结构确认 phone 是 varchar再看传入参数类型确认是数字。验证方式也简单把查询改成 where phone 138xxxx立刻变成 typerefrows 从几十万降到个位数。这个问题的修复最好在应用层做统一传字符串。如果实在改不动代码MySQL 8.0 下可以像 5.3 节那样建函数索引。但函数索引毕竟是额外成本底层根治才是正路。类似的元凶还有字符集不一致导致跨表 join 时索引失效utf8 和 utf8mb4 混用以及 in 或 or 中混入非索引列导致优化器放弃索引。这些坑和隐式转换一样都要用 explain 确认不要靠猜。6.3 区分度太低时优化器为什么主动放弃索引还有一种情况让人迷惑索引存在条件也写了explain 还是 ALL。问题往往出在区分度。比如 where gender malemale 这个条件能筛掉一半数据优化器一算走二级索引要随机回表几十万次还不如全表扫描顺序读来得快于是直接放弃索引。这不是 MySQL 的缺陷而是基于成本的理性选择。数据行和索引页的物理分散决定了回表有随机 IO 开销“先查索引再回表”并不总比“全表顺序读”便宜。尤其是 SSD 上顺序读很快时优化器更倾向全表扫描。设计阶段怎么避免用 4.4 节的区分度 SQL 先看一下候选列的区分度。区分度低的列单独建索引意义不大更适合放进联合索引配合高区分度列一起使用。如果已经是存量 SQL可以在必要场景下用覆盖索引让查询完全免回表这样优化器不用纠结“回表成本”因为根本不回表。6.4 从数据结构看索引维护成本为什么索引不是越多越好最后分享一个我常和同事强调的点索引是空间换时间的结构而空间不便宜。每加一个二级索引意味着写入时 B树要同步维护一份新结构插入要定位页、页满要分裂、更新可能触发移动、删除要标删与清理。写放大是真实存在的。一个表如果有四五个索引每次插入一行可能要写五六个 B树。业务如果偏读多索引收益明显业务如果偏写索引就是负担。所以设计索引时我的原则是先列出核心查询路径再设计两三个能够覆盖多条路径的联合索引而不是每个字段都建单列索引更不是为了“以防万一”堆一堆没用索引。MySQL 8.0 的不可见索引机制可以帮你安全清理存量无用索引设为不可见后观察慢查询没有异常再删除这套流程无限接近“零风险变更”。我在实际操作中还有一个习惯任何索引变更先在测试环境用 explain 验证对比修改前后的 type、rows、Extra再考虑上线。索引能不能生效不要靠经验瞎猜数据库已经在执行计划里给了你答案。数据量上来之后一次错误的索引变更造成的连锁反应远比普通代码 bug 难回滚。