2. 索引的数据结构
聊到 MySQL 索引，十个面试官里九个会问同一个问题：为什么索引要用 B+ 树？以前我也觉得这是个“背答案”的题，直到自己实际去建索引、排查慢 SQL、看执行计划时踩了一堆坑，才意识到——如果你不理解索引底层的数据结构，那你建索引就是在盲人摸象。字段加不加索引全凭感觉，索引失效了也看不出原因，联合索引顺序排错更是家常便饭。
这篇文章我想换个角度，不直接列知识点，而是从“索引到底是什么数据结构”这条线讲起，把 B+ 树、Hash、聚簇索引、回表、最左前缀这些概念串起来，落到你where a and b到底该怎么建索引这个实际问题上。搞清楚底层结构，你就知道为什么有些规则是“死记硬背”，而有些规则是可以自己推出来的。这篇文章适合所有写过 SQL、建过索引但没系统性梳理过原理的后端开发，也适合正在准备面试想彻底搞懂索引的人。
2.1 索引的本质：不只是“排好序的列”
先说个基础认知。很多人觉得索引就是给某个字段排个序，方便查询快一点。这话方向没错，但低估了索引的复杂性。索引的本质，是一份独立的、有序的、经过特殊组织的数据结构，它单独存储在磁盘上，与表数据分离但又通过指针或物理位置关联。
为什么要把它做成“独立”的？你想想，如果直接在原始表数据上做排序，那每次插入、删除、更新一行，整张表的数据可能都要重新整理一遍，代价太大了。所以数据库的做法是：把需要加速的字段单独提取出来，按照某种数据结构重新组织，形成一份“目录”。这份目录体积远小于原表，可以更快地加载到内存，查找时先查目录、拿到位置，再回表取完整数据。这个思路其实就是你查字典的流程：先查部首目录，定位到页码，再翻到那一页看具体内容。
那么问题来了：这份“目录”用什么样的数据结构来组织，才能做到查找快、插入快、删除快、范围查询也快？这就是本文的核心，也是“索引的数据结构”这个标题真正要解决的问题。不同数据库、不同存储引擎选用了不同的数据结构，你得先知道有哪些选项，以及它们各自的优缺点，才能明白 MySQL 为什么偏偏选了 B+ 树。
2.2 索引家族盘点：从 Hash 到 B+ 树
2.2.1 Hash 索引：精确匹配的“神”，范围查询的“坑”
先讲 Hash 索引，因为它的思路最直观：对索引字段的值做一次哈希运算，直接定位到数据所在的槽位。你可以理解成一个大型的Map<哈希值, 数据指针>，查询时计算哈希、命中槽位、取出指针，时间复杂度是 O(1)，这速度理论上比 B+ 树还快。
但 Hash 索引有个致命短板：它只能做等值比较。where name = '张三'这种是它的主场，但where age > 18、where name like '张%'这种范围查询、模糊查询它就完全无能为力了。因为哈希函数是“打散”的，学过的朋友应该记得，哈希后的值是乱序的，你做不了有序遍历。另外，Hash 索引还不支持索引排序，因为存储时根本没有顺序可言；更麻烦的是，一旦发生哈希冲突，维护成本和查询性能都会劣化。可以看到很多存储引擎，例如早期版本的 MyISAM 和 MEMORY 引擎，对 Hash 索引的支持都局限在等值场景。实际业务中，我们 70% 以上的查询都是范围类、排序类的场景，所以主流的 InnoDB 没有把 Hash 作为默认索引结构，而是在内存层面做了一层自适应哈希索引（Adaptive Hash Index）来加速特定热点数据的等值查询。用一句话总结：Hash 很快，但它是个偏科生。
2.2.2 二叉搜索树与平衡二叉树：理论合理，工程不行
既然 Hash 做不了范围查询，那用树结构？二叉搜索树（BST）确实可以：左子树小、右子树大，中序遍历就是有序序列，等值查询和范围查询都能做。但二叉搜索树有个严重的不确定性：如果插入的数据本身是有序的，比如按照自增 ID 逐条插入，二叉搜索树会直接退化成链表。这时候查询时间复杂度从理想的 O(log n) 崩成 O(n)，跟全表扫描没区别了。
为了解决退化问题，出现了平衡二叉树（AVL）和红黑树。它们通过旋转操作来保证树的高度始终是 log n 级别，查询效率稳定。但问题来了：树是“矮”了，可每个节点只能存一个键值对。MySQL 一张表几百万行数据，这棵树的高度会是二十几、三十几层。我们硬盘读取数据是按“页”来的，每读一层树，就要一次磁盘 IO。30 层就是 30 次磁盘 IO，按每次 IO 10ms 估算，就是 300ms。这个延迟在业务系统里基本属于不可接受的灾难。数据量一大，树再平衡也扛不住磁盘 IO 的次数。
等读完 B+ 树你再回头看，就会明白：平衡树不是输在“算法复杂度”，而是输在“树太高”。所以工程上真正需要一种又矮又胖的树——每个节点能存多个键，层级很低，一次 IO 就能读入更多有效信息。这就是 B 树和 B+ 树登场的逻辑，理解这个演进过程非常重要，因为这是索引数据结构设计的核心动机：无论是哈希、二叉树还是 B 树，一切选择都是在“查询速度、写入成本、磁盘 IO、范围查询支持”这几者之间做权衡。而 B+ 树在这个权衡网格里，是综合得分最高的那个。
2.2.3 B 树、B+ 树和跳表：谁是真正的王者
B 树是多路搜索树的一种，它允许每个节点存储多个关键字，并且有多个子节点。你可以把 B 树理解成“一个节点就是磁盘的一页”，比如 MySQL InnoDB 默认一页 16KB，一个节点能存几百上千个键值。这样一来，三层 B 树就能轻松存下千万级数据。这个特性让 B 树的高度非常低，一般 3 到 4 层就能撑起一个大表，磁盘 IO 次数被压到了个位数。
不过这里有个容易混淆的点：B 树的每个节点既存索引键，又存完整的数据记录（或者指向数据的指针）。而 B+ 树做了进一步改良，内层节点（也叫非叶子节点）只存索引键和指向子节点的指针，真正数据只放在叶子节点，并且叶子节点之间用链表串联。这一改动带来了三个工程上极其重要的收益：第一，内层节点能装更多索引键，树变得更矮；第二，叶子节点的链表让范围查询不再需要回溯到父节点，直接顺着链表扫就行；第三，所有数据都在叶子层，查询任何一条记录经历的 IO 次数是固定的，也就是“查询稳定”。
那跳表呢？Redis 的 ZSET 就用跳表实现有序集合。跳表的思路是用多级链表做“跳跃”查找，实现简单、并发友好。但它本质上是内存数据结构，数据全在内存里才能发挥优势，如果落到磁盘上，对 IO 的利用效率远不如 B+ 树。所以结论很清晰：关系型数据库的磁盘特性决定了 B+ 树的王者地位，而跳表更适合内存数据库。
2.3 为什么 MySQL 偏偏选了 B+ 树
2.3.1 磁盘 IO 是压倒性因素
先掰扯清楚一个关键问题：为什么磁盘 IO 次数这么重要？固态硬盘随机读大概几十到一百微秒，机械硬盘更慢，差不多 10 毫秒。虽然内存随机访问是纳秒级，但数据库表数据是放在磁盘上的，每访问一层索引结构，就对应一次磁盘 IO。这个成本是内存的十万倍量级，所以索引数据结构的第一设计目标就是尽量减少磁盘 IO 次数。
B+ 树的高度通常只有 3 到 4 层，意味着查询一条记录最多 3 到 4 次磁盘 IO。再加上 InnoDB 的缓冲池（Buffer Pool）会把热门的非叶子节点缓存在内存中，实际查询中真正打到磁盘的往往只有最后一层叶子节点的 IO。相比之下，如果用二叉树做索引，千万级数据树高可能就是 24 层左右，即使全部节点都缓存，也架不住磁盘的随机读取。读到这里你应该能明白，不是 MySQL 开发者偏爱 B+ 树，而是磁盘硬件特性逼着他们选择了 B+ 树。
2.3.2 范围查询和排序的先天优势
除了 IO 次数，还有一个业务上的刚需是：SQL 里太常见between、>、<、order by这类操作了。B+ 树的叶子节点之间用双向链表串起来，本质上就是一个天然的有序数组。你查一个范围，比如age between 20 and 30，B+ 树先精确定位到 20 这个键所在的叶子节点，然后顺着链表往后遍历到 30 就行。这个过程不会跳回树的上层，效率极高。
对比一下 B 树，B 树的数据分布在所有节点，范围查询时要不断地回到父节点甚至根节点去遍历子树，增加了额外的 IO 和计算。而 Hash 索引在范围查询面前直接投降。所以 B+ 树在“有序性”这一点上，对于实际业务 SQL 是命中率最高的选择，这也是它最后胜出的核心原因之一。
2.3.3 写放大与页分裂的工程平衡
有人可能会问：“B+ 树的写性能呢？插入要分裂页、删除要合并页，好像不轻松嘛。”确实，B+ 树的写入并非没有代价。它为了保证有序性，插入时如果目标页已满，就需要做页分裂操作，旧数据挪动、新页分配，这个过程会产生额外的写入。这也是为什么我们推荐用自增主键作为 InnoDB 主键索引：因为插入的数据总是追加在叶子节点的末尾，很少触发页分裂。如果主键是 UUID，那插入时位置完全随机，页分裂会非常频繁，写性能会明显劣化。
但要注意，这个“写开销”是可控的、均值稳定的。B+ 树通过局部分裂维持全局有序，不像平衡二叉树那样需要大量的节点旋转。而且 InnoDB 还引入了顺序插入优化、Change Buffer等技术来缓和二级索引的随机写入问题。综合来看，B+ 树在读写之间拿到了一个很好的平衡点。我没有贬低 Hash 或二叉树的意思，它们各有适用场景，但就关系型数据库这种既要写、又要读、还要范围扫描的混合负载而言，B+ 树是最不坏的那个方案。
2.4 InnoDB 引擎中的索引到底长什么样
2.4.1 聚簇索引：整张表的“骨架”
InnoDB 的表数据本身就是按主键构建的 B+ 树来存储的。这句话值得你多读两遍。它不是“主键索引额外存在某个文件里”，而是整张表的行数据就挂在主键 B+ 树的叶子节点上。所以这个索引想不叫“聚簇索引”都难，因为数据记录聚集在主键周边。
如果你建表时没有显式声明主键，InnoDB 会找一个非空唯一索引来充当聚簇索引；要是也没有，它就隐式生成一个 6 字节的 ROWID 来建聚簇索引。所以，每一张 InnoDB 表一定有一个聚簇索引，而且聚簇索引能且只能有一个。理解聚簇索引的关键在于：叶子节点存储的是完整的一行数据，所以通过主键where id = 1查询，走一次 B+ 树即可拿到全部字段，不需要额外回表。
2.4.2 二级索引与回表：你建的非主键索引都叫二级索引
除了主键之外的索引，都叫二级索引或者非聚簇索引。比如你给name字段建一个普通索引，那么 InnoDB 会另外构建一棵 B+ 树，树的内层节点存name的值，叶子节点存的是主键值，而不是完整数据行。这一点很多新手容易搞错，以为二级索引的叶子节点存的是数据行地址——不是的，它存主键值。
那查询时怎么拿完整数据？假设执行select * from user where name = '张三'，MySQL 先在name这棵 B+ 树上查到一个或多个主键值，然后再用这些主键值到聚簇索引的 B+ 树里查完整记录。这一步就叫回表。回表不是错误的操作，但是回表次数越多消耗越大。如果你要的字段在二级索引的叶子节点里全都有（也就是主键加上索引字段本身），那就无需回表，这种优化叫覆盖索引。我在实际调优中，经常通过explain看Extra列有没有Using index，如果有就说明这条查询已经覆盖索引了，回表被省掉了，性能自然好。
2.4.3 联合索引：一次建多个字段，底层还是一棵树
联合索引特别有意思，它也是一棵 B+ 树，只不过节点里存的是多个字段的值，排序时先按第一个字段排，第一个字段相同再按第二个字段排，以此类推。所以联合索引(a, b)实际上在 B+ 树里形成了一种“先按 a 有序、同 a 内按 b 有序”的复合排序。这正是最左前缀原则的数据结构根源。打个比方：你把电话簿按“姓+名”排序，姓在前名在后。你想查所有姓“张”的人，效率很高，因为姓是第一关键字；你想查名字里带“伟”的人，就没法直接利用了，因为“名”不是第一排序关键字。
建联合索引时字段顺序为什么重要，底层结构已经给出答案：哪个字段放在最左边，它就拥有最高排序优先级。如果你查询条件里没有第一个字段，那么 B+ 树的排序优势就发挥不出来。这也可以反向推导出很多 SQL 优化规则。例如where a and b，建(a, b)联合索引是合理的；但如果你还经常单独查 b，那(b, a)就更为合理。世上没有一份索引适合所有查询，得看你实际业务里哪些查询最频繁。
2.5 从数据结构推导建索引法则
2.5.1 最左前缀到底在说什么
我在面试候选人的时候，很多人能背出“联合索引服从最左前缀”，但问一句“为什么”，就答不上来了。其实你只要还原一下 B+ 树的节点结构就懂了：联合索引(a, b, c)的每个非叶子节点存的是(a, b, c)三个值，但对整棵树来说，节点的路由顺序是：先比较 a，再比较 b，最后比较 c。如果你查询条件里没有 a，B+ 树根本无法定位到具体的分支节点，因为没有“第一层”的比对标准。
所以最左前缀并不是一个“强加的规则”，而是 B+ 树排序方式决定的自然属性。MySQL 5.6 之后引入的索引条件下推（ICP）能在一定程度上缓解这个问题，但它不能根本改变 B+ 树的有序路由逻辑。理解这一层之后，你在设计联合索引时，就应该把查询频率最高、筛选性最强的字段放在左侧。有时候“筛得狠”比“查询频率高”更重要，因为 B+ 树定位时第一步就过滤掉大量数据，整棵树的搜索空间会大幅收窄。
2.5.2 哪些操作会让索引结构失效
理解了索引结构，索引失效的很多场景就都能解释了。常见的失效场景包含但不限于：对索引列使用函数或表达式计算，比如where DATE(create_time) = '2024-01-01'，因为 B+ 树存的是原始值，不是函数处理后的值，索引无法支持这个运算；隐式类型转换，比如where phone = 138xxxx而 phone 字段是 varchar 类型，字符集和排序规则不同导致索引失效；前导模糊查询like '%abc'，因为 B+ 树是有序结构，它只能从最左侧开始匹配，最左侧通配符让有序匹配无从谈起；使用or连接非索引列，导致优化器需要全表扫列；还有对索引列做!=、not in等操作，本质上破坏了有序匹配策略。你要是有兴趣，可以用explain查看key字段，看看这些语句是否真的走了索引。实践一下比背结论可靠得多。
2.5.3 一条 SQL 的索引选择与执行计划
拿一个很典型的例子来分析：select * from t where a = 1 and b = 2。表上有联合索引idx_a_b(a, b)。这条 SQL 应该能走索引，因为 a 是联合索引最左列，等值条件下 B+ 树可以先定位 a=1 对应的叶子区间，再过滤出 b=2 的行。相比之下，如果你建的是两个独立索引idx_a(a)和idx_b(b)，MySQL 会评估两个索引哪个区分度更高，然后用其中一个去查，再回表过滤另一个字段。此时 MySQL 的优化器有时候还会选择“索引合并”功能，用两棵 B+ 树分别查主键集合，再做求交集。索引合并听着很美好，但实际执行时开销往往不小，我很推荐你在设计表时，优先考虑联合索引而不是拼命堆单列索引。联合索引本质上是一棵已经排好序的复合树，查找效率远高于“查两次再合并”。
2.6 常见问题与避坑实录
2.6.1 为什么推荐自增主键，而不是 UUID 主键
很多新手建表时喜欢用 UUID 作为主键，理由是“全局唯一、业务无关、插入前不知道 ID”。但如果理解了聚簇索引叶子节点是有序排列的，你就知道 UUID 这种随机字符串会导致新插入的行大概率落在已有叶子节点中间，频繁触发页分裂。每次页分裂要移动已有数据、更新指针、重新分配磁盘页，写放大非常明显。
自增主键则刚好相反：新数据永远追加在 B+ 树的最右侧叶子节点，页分裂次数少，写入几乎是顺序 IO。这不是“玄学”，而是 B+ 树有序结构下的必然结果。当然，如果业务上确实需要 UUID 这种业务主键，你可以让它作为唯一索引存在，另外加一个自增主键作为聚簇索引，这样兼顾了业务查询语义和写入性能。我在一个日活百万的项目里实测过，使用自增主键后批量导入性能提升了 30% 以上，可见页分裂的影响有多大。
2.6.2 为什么索引字段要短，而且不要为 NULL
索引字段长度和宽度的问题，同样可以从 B+ 树结构推出。一个 B+ 树节点能容纳多少个索引键，取决于一个键占多少字节。键越短，节点能容纳的键越多，树高就越低，IO 次数越少。所以设计索引的时候，别贪多、别用长文本做索引。如果业务必须用，可以考虑前缀索引，截取字段前 N 个字符做索引。你可能会担心前缀索引的区分度问题，这个可以通过select count(distinct left(name, N)) / count(*)来估算样本区分度，实际验证后再定前缀长度。
至于 NULL，B+ 树在比较时对 NULL 的处理比较特殊（InnoDB 里 NULL 会被当作一个特殊的最小值或者与普通值分开处理）。如果索引列允许 NULL，那么where 索引列 is null的查询效率、索引扫描时的统计信息都可能变得更复杂，优化器也可能犹豫是否走索引。代码里用空字符串或者默认值兜底，通常比让字段存 NULL 对索引更友好。
2.6.3 建了多少索引才算够
这个问题没有标准答案，但有一条经验：索引越多，写入越慢。每建一个二级索引，就相当于在表上多维护一棵 B+ 树。写入一条记录时，主键索引要写，每一个二级索引也都要写。所以给一张高频写入的表堆五六个索引，写入性能必然肉眼可见地下降。我的习惯是：先用业务查询日志统计高频 SQL，只给那些查询频繁、数据量大的表建索引；同一个查询尽量只用一个索引；能用联合索引解决多个查询，绝不拆成多个单列索引。索引是“空间换时间、写换读”的方案，你建它之前得想清楚要牺牲哪一边。
2.7 实操中的一条心法
说点我自己积攒的经验。我每次拿到一条慢 SQL，并不急着搜“怎么优化”，而是先做三件事：跑一遍explain，看有没有走索引，看type是不是ref或range，看Extra有没有Using temporary、Using filesort；再算一下区分度，用count(distinct 字段)/count(*)评估这个字段值重复程度；最后看表数据量和写入频率，决定是加索引还是干脆全表扫。index 的下推力度，大多数情况下用联合索引（a,b）解决高频过滤，配合覆盖索引解决高频查询字段，就能把 90% 的慢查询压下去。索引数据结构的价值，不在于让你背出一棵树长什么样，而在于你踩到慢查询的坑时，能从“为什么”而不是“是什么”的角度找到出路。你自己动手建几个索引、观察几次执行计划变化，会比抄任何一份总结都管用。
