前几天有个同事带着一脸困惑跑来找我，说他写了一条SQL，where条件里两个字段都建了索引，执行计划却告诉你他根本没走索引。我一问，表里建了两个单列索引，优化器觉得还不如全表扫描，执行计划果断把索引扔了。这类问题我见过太多次了，根源往往不在SQL写法上，而在对索引底层的结构理解不够——你不知道索引在磁盘上长什么样，就猜不透优化器的决策逻辑。今天的重点就是索引的数据结构，从最底层的B+树、哈希索引讲起，一直聊到联合索引怎么建、哪些场景会让索引失效。写个后端、做数据库调优、或者正在准备面试的人，这篇都适合。
1. 索引数据结构全景：从一次慢查询开始
1.1 一个典型的慢查询事故现场
先还原一个真实场景。某天线上反馈订单查询接口很慢，慢日志里抓出来了这样一条SQL：
SELECT * FROM orders WHERE user_id = 10086 AND status = 1 ORDER BY create_time DESS LIMIT 20;开发同学说user_id和status都建了索引，怎么会慢？DBA一看，user_id和status各有一个单列索引，优化器在这个查询里只能选其中一个来用，另一个索引帮不上忙。更麻烦的是ORDER BY create_time还得单独排序。如果数据量是几百万行，这个排序会直接拖垮查询。
这个例子引出了索引数据结构的第一课：索引不是越多越好，也不是随手给每个字段挂一个就完事。你得知道索引是怎么组织数据的，才能理解为什么联合索引更合适、为什么某些条件下索引会失效。
1.2 索引的本质：为了少读磁盘
索引到底是干什么的？说白了就是给数据建一个“目录”，让数据库不用把整张表翻一遍就能找到目标行。全表扫描就像在厚厚的一本书里从第一页翻到最后一页找一句话，索引则像书末的术语表，直接告诉你关键词在第几页。
但数据库的目录不是普通目录，它必须解决一个核心矛盾：数据量巨大，内存装不下，大部分数据在磁盘上。磁盘IO是极其昂贵的操作，一次随机IO往往要消耗几毫秒到几十毫秒，比内存访问慢几个数量级。所以在设计索引的数据结构时，最重要的指标不是“查找次数有多快”，而是“要读多少次磁盘块、每次能带回多少有效信息”。
很快你会发现，常见的二叉树、二分查找、哈希表这些数据结构，到了磁盘环境下都各有各的致命伤。这也是为什么MySQL InnoDB最终选择了B+树作为索引的默认结构，但哈希索引也有它的广阔舞台。
1.3 索引结构演进：从二叉树到B+树
把数据结构课上的知识串起来看，事情会清晰很多。最朴素的想法是用二叉查找树做索引：左小右大，查找时和根节点比一下，向左或向右走。问题在于，普通二叉查找树在插入有序数据时会退化成一条链表，查找复杂度直接掉到O(n)；更麻烦的是，每个节点只能存一个键，一次磁盘IO只能取一个节点，树的层数稍微一深，磁盘IO次数就爆炸。
于是有了平衡二叉树（AVL）和红黑树，它们通过旋转把树的高度控制住，让查找稳定在O(log n)。但红黑树的问题仍然是“太瘦高”——一个节点存一个键，高度通常还在十几层以上，而每一层都意味着一次磁盘IO。数据库里动辄几百万行数据，十几层的高度是不可接受的。
真正让数据库性能发生质变的是B树和B+树。它们的核心理念是“矮胖”——一个节点不只存一个键，而是存几十上百个键，并且一个节点对应一个磁盘页，一次IO就把一整块数据读进内存。这样几百万行的数据量，树的高度通常只有2到3层，意味着最多两三次磁盘IO就能定位到目标。
| 结构 | 节点存储 | 树高度 | 磁盘IO次数 | 范围查询 | 数据库使用场景 |
|---|---|---|---|---|---|
| 二叉查找树 | 1个键 | 高，可能退化为链表 | 多 | 差 | 基本不用 |
| 红黑树 | 1个键 | 较高，log n | 每层1次IO | 一般 | 内存场景 |
| B树 | 多个键+数据 | 矮 | 2到3次 | 较差，需回溯 | 早期文件系统 |
| B+树 | 内部节点只存键，叶子存数据 | 矮 | 2到3次 | 极好，叶子链表顺序遍历 | InnoDB默认索引 |
看到这张表你就明白了：数据库选B+树不是偶然，而是IO模型倒逼出来的必然。
2. 一层层拆开B树与B+树
2.1 B树的结构与查找过程
B树是一种多路平衡搜索树。所谓“多路”，是指一个节点可以包含多个键值和多个指向子节点的指针。假设一个节点能存4个键，它就有了5个分叉，所有键在节点内按顺序排列。查找时先在节点内部做二分查找，命中就结束；没命中就根据键的大小走向对应的子节点，直到命中或到达叶子。
用数据举个例子。假设一个B树节点能存100个键，那么树有3层时，最多可以容纳约100万个键。每一层对应一次磁盘IO，三次IO就能从100万条数据里找到目标，这个效率在工程上非常可观。
B树的一个特点是：所有节点都可以存储数据行或指向数据行的指针。这意味着你在非叶子节点就能找到目标，不用非要走到叶子。听起来不错，但这带来两个问题。第一，数据散落在不同层的节点上，查找性能不稳定，有的人找2层就到，有的人要一路走到第3层。第二，范围查询很尴尬——比如要查某个区间内的所有数据，B树得先找到起点，然后在中序遍历过程中不断向上回溯父节点，不断切换分支，产生了大量额外的磁盘IO。
2.2 B+树的结构：数据都在叶子上
B+树针对B树的问题做了两个关键改动。第一个改动是：内部节点（非叶子节点）只存键值和子节点指针，不存数据。这样一来，同样大小的磁盘页能容纳更多的键，树变得更“宽”更“矮”——16KB的页大概能存上千个键，树高度很容易控制在2到3层。第二个改动是：所有数据都集中在叶子节点上，并且叶子节点之间通过双向链表按顺序串联起来。
这两个改动让B+树在数据库场景下优势尽显。查找任意一条数据，都必须走到叶子节点，每一次查询的IO次数稳定在同一量级，不存在“运气好走两层、运气差走五层”的波动。范围查询直接从叶子链表头开始往后扫就行，不需要在树中间反复回溯。排序操作也爽了，叶子本身就有序，遍历叶子链表就是有序结果。对数据库来说，“稳定”和“有序”恰恰是最值钱的特性。
2.3 为什么InnoDB选B+树，而不是红黑树或B树
很多人刷算法题时觉得红黑树很强大，为什么数据库不拿来当索引？关键在于衡量标准不同。红黑树是内存数据结构，它的旋转操作在内存里很快；但在磁盘面前，它一次IO只能读一个节点，高度再矮也扛不住几百万行数据。简单算一下：InnoDB的B+树高度为2时，叶子节点能容纳数百万条记录，查找只需两次IO；同样数据量用红黑树，树高度至少20层，就是20次磁盘IO，差了十倍量级。
那为什么不直接用B树？B树在范围查询上的劣势是致命的。电商订单按时间范围查、分页查询、各种报表查询，全都是范围操作。B+树的叶子链表让这些操作变得像遍历数组一样轻松，这是B树给不了的。B+树还天然契合InnoDB的聚簇存储结构——后续会提到，主键对应的索引叶子节点直接存放整行数据，这个特性必须依赖“数据只在叶子”的设计。所以在InnoDB内部，B+树不是可选项，而是牢牢绑定在存储引擎核心里的默认方案。
2.4 为什么不用跳表？LevelDB的对比
Redis的Sorted Set用跳表，LevelDB的MemTable用跳表，为什么MySQL不换？跳表查找复杂度也是O(log n)，但它的每个节点通常只有两个指针，相邻节点之间跨度小，要素过多。跳表在内存中表现极佳，因为它按指针逐层跳跃；一旦换到磁盘上，节点离散存储，查找一个目标可能要跨越多层指针、多次随机IO，页缓存也无法充分利用。B+树的优势在于把大量键聚在同一个磁盘页里，一次IO读回一大堆“可用的键”，局部性原理被发挥到极致。数据结构好不好，不看理论上限，看它在特定介质上的适配程度——这就是工程思维。
3. 不只是B+树：哈希索引与全文索引
3.1 哈希索引：等值查找的王者
B+树合适不代表所有场景都该用它。哈希索引是另一个世界里的强者，它的思路完全绕开“比较大小”，直接通过哈希函数把键值映射到桶里。查找时计算一次哈希，定位到桶，再处理桶内的冲突链，等值查询能做到接近O(1)。这正是哈希索引的黄金场景：精确匹配，且对范围无欲无求。
在MySQL里，Memory引擎默认就使用哈希索引，因为它快、简单、不做磁盘持久化。InnoDB则更聪明，它搞了一个自适应哈希索引（AHI）。这玩意不是让你手动创建的，而是InnoDB在内存中自动监测热点数据，当某些B+树索引页被高频访问时，自动为它们建立哈希索引，把等值查询从多次IO降低到一次内存查找。很多人在慢查询日志里看到“AHI命中率低”之类的信息，其实就是访问模式太离散，自适应哈希索引发挥不出来。
哈希索引的致命短板也很明显：做不了范围查询，>、<、BETWEEN通通没法用；不支持排序；因为哈希值无序，也做不了前缀匹配。所以生产环境里，主键索引、联合索引几乎全是B+树，哈希只能当配角。有些开发同学一看到“哈希”两个字就觉得它更快，非要给业务唯一键建哈希索引，结果范围查询一来直接全表扫描，这就是对数据结构适配性不理解。
3.2 全文索引：倒排索引的应用
还有个常见的索引类型是全文索引，它背后的数据结构是倒排索引。传统索引是从文档ID找词，倒排索引反着来——从词找文档ID列表。建全文索引时，MySQL会对文本做分词，把每个词映射到包含它的行ID列表上，存储成类似“词 → 文档ID集合”的结构。搜索时先查词，再快速拉出所有包含该词的行。
很多人用LIKE '%关键词%'去搜大段文本，结果慢到怀疑人生。这就是数据结构选错了，LIKE '%xxx%'无法使用B+树的前缀匹配特性，索引失效，只能全表扫描。正确的做法是给文本字段建立全文索引，再用MATCH ... AGAINST语法做全文检索。InnoDB从5.6版本开始支持中文全文索引，但要先处理分词器问题，中文不按空格分词，需要选好ngram解析器。自己搭搜索引擎时，Elasticsearch的倒排索引也是同一个思想，明白了底层是倒排结构，你就知道为什么它能秒级搜索上亿文本。
3.3 空间索引：以R树为代表的几何结构
聊到索引数据结构，空间索引不能完全忽略。MySQL的MyISAM和InnoDB都支持空间索引，底层是R树。R树专门为多维几何数据设计，把空间上相邻的对象用最小边界矩形（MBR）包起来，上层节点用更大的矩形包含下层矩形，查询时逐层判断矩形是否相交，快速剪枝掉不相干的分支。地图上“找附近1000米的餐厅”这类查询，如果数据量大，会用到空间索引。但对绝大多数业务来说，地理坐标直接用GeoHash编码存成字符串，配合普通B+树前缀查询，一样能解决问题，还不必引入新结构。
4. InnoDB的聚簇索引与MyISAM的非聚簇索引
4.1 聚簇索引：数据跟着主键走
聊完几种底层结构，回到存储引擎这个层面来看索引形态。InnoDB里，主键索引就是聚簇索引，B+树的叶子节点直接存放整行数据。也就是说，表数据本身就是按主键顺序聚簇在B+树上的。查询走主键时，在叶子节点找到目标的同时就拿到了这一行的全部列，不需要再回表，快得很。
这个设计带来一个强约束：InnoDB表必须要有主键。如果你建表时不指定主键，InnoDB会先找第一个非空的唯一索引作为聚簇索引；实在找不到，它会自动生成一个隐藏的6字节rowid作为聚簇索引。很多开发同学不在意这个，但底层逻辑就是，没有明确的聚簇索引，InnoDB也得自己造一个，对不对齐你的数据访问习惯，它管不着。
聚簇索引还深刻影响插入顺序。如果主键是随机的UUID，新插入的数据在B+树上的位置是跳来跳去的，经常导致叶子节点的页分裂和页重排，产生大量碎片，插入性能明显下降。这也是为什么我强烈建议用自增整数或bigint做主键，而不是UUID——从数据结构的角度看，顺序插入能让B+树的叶子节点平稳扩展，避免页分裂。
4.2 二级索引：回表是怎么发生的
除了主键索引之外的索引都叫二级索引。二级索引的B+树叶子节点不存整行数据，只存索引列的值加上主键值。当查询条件命中了二级索引，却又要读取非索引列时，数据库会先从二级索引叶子拿到主键，再根据主键去聚簇索引上找完整行，这个过程叫回表。
回表意味着一次查询可能要跑两遍B+树，所以性能不如直接走主键索引。一个经典的优化思路是覆盖索引：如果你查询的列全部都在二级索引里，那么叶子节点上的数据已经足够，InnoDB就不回表了。比如SELECT user_id, status FROM orders WHERE status = 1，如果(status, user_id)上有联合索引，查出来的两列都能直接从索引拿，Extra列的Using index就说明发生了覆盖索引扫描。很多慢查询的优化方案，说白了就是把SELECT *改成覆盖SELECT所需列，加联合索引把回表次数降成0。
4.3 主键索引和唯一索引到底差在哪
这个问题被问过无数遍。主键索引和唯一索引从数据结构上看都是B+树，但两者的约束和用途有明显区别。一张表只能有一个主键索引，但可以有多个唯一索引。主键列不允许为NULL，唯一索引列允许有多个NULL值——在InnoDB里唯一索引对NULL是放行的，因为NULL本身代表“未知”，未知和未知不算重复。在InnoDB中，主键索引是聚簇索引，承载整行数据；唯一索引是二级索引，叶子节点只存主键值。主键是物理存储的锚点，唯一索引只是逻辑上的“不允许重复”约束加一个可用的加速路径。
从实用的角度说，业务上要求某个字段唯一时，比如手机号、身份证号，一定要给字段加唯一索引。这里有个容易踩的坑：数据库的并发环境里，两个请求同时插入相同手机号，如果没有唯一索引兜底，先靠应用层判断会存在竞态条件，导致脏数据。有了唯一索引，第二次插入就被数据库拒绝，业务层的判断+数据库唯一索引双保险才可靠。
4.4 MyISAM的非聚簇索引：一张对照表
MyISAM引擎的索引和InnoDB完全不同，它是非聚簇结构：B+树的叶子节点存放的是数据行的物理地址，而不是数据本身。索引文件和表数据文件分开存储，索引定位到地址后还需要再读一次数据文件，所以无论走主键还是二级索引，本质上都是两层结构。这种设计的优点是索引结构简单，统计和压缩方便；缺点也很明显，数据在物理文件中的顺序和索引顺序可能不一致，范围查询和批量插入的局部性不如InnoDB。如今主流业务基本都用InnoDB，因为崩溃恢复能力强、支持事务，聚簇索引本身也让主键查询更快。我在新项目里几乎不再建MyISAM表，只有个别只读、查全表的分析场景还在用。
5. 联合索引的结构与最左前缀：where a and b究竟该怎么建
5.1 联合索引是怎么排序的
回到开头那个让人困惑的问题：where条件里有多个字段，到底怎么建索引？答案通常不是给每个字段各建一个单列索引，而是建联合索引。联合索引在B+树里的排序逻辑是：先按第一个字段排，第一个字段相同的记录再按第二个字段排，以此类推。比如(user_id, status)这个联合索引，叶子节点上所有数据先按user_id分组，每组内部按status有序排列。
这个排序规则带来一个重要的结论——最左前缀原理。查询条件如果包含联合索引的最左列，就能利用这个索引；如果查询条件跳过第一个字段，只命中第二个或后面的字段，那么B+树的排序顺序帮不上忙，索引就会失效。WHERE user_id = 10086 AND status = 1能用到(user_id, status)，但WHERE status = 1在这个联合索引上毫无用武之地。
5.2 顶层设计：等值先行、区分度高的放左边
那么where a and b应该怎么建索引？关键是看查询条件和数据分布。如果a和b都是等值查询，即a = 1 AND b = 2，那么联合索引的两个列放谁在前问题不大，因为等值条件下，优化器会按照索引来检索，都能快速命中。要注意的是，若后面还有范围条件，比如a = 1 AND b > 100，那么范围条件右边的列就再也用不上了。这种情况下，把等值列放在联合索引的前面，范围列放最后，才能最大化索引利用率。
还需要考虑区分度。简单来说，某列的数据越分散，区分度越高。性别只有男、女两种值，区分度就很低；手机号基本不重复，区分度就高。建联合索引时，一般把区分度高的列放前面，因为B+树排序后，高区分度列能更快把数据缩到很小的范围。比如(user_id, status)明显比(status, user_id)好，因为user_id的取值范围大，能直接把几百万行缩到几十行。
5.3 为什么不建两个单列索引
有一种错误的做法是给a和b分别建单列索引。虽然查询条件里同时出现了两列，但优化器在一个查询里通常只能选择一个主要的B+树索引来定位，另一个索引最多通过index merge做交集合并。index merge在很多版本里都有额外开销，性能不如一个联合索引直接定位。开头的那个订单查询正好踩在这个坑上——user_id和status各有一个单列索引，执行计划只能用其中一个，然后对剩下的条件做过滤，如果过滤比例不高，还不如全表扫描。
联合索引还有个容易被忽视的好处：覆盖索引。比如(user_id, status, create_time)这个索引，查询只需要这三列时，走索引就能直接返回，不用回表。这个特性往往被忽略，但它对优化SELECT指定列的场景极其有效。
6. 索引失效场景排查与explain实战
6.1 常见失效场景速查表
数据结构搞懂了，还得能把它变成日常排障的直觉。下面这些场景，我在实际排障中几乎每周都会遇到，整理成一张速查表：
| 失效场景 | 根本原因 | 正确做法 |
|---|---|---|
对索引列使用函数，如WHERE DATE(create_time) = '2025-01-01' | 函数改变了列的原始顺序，B+树无法对上 | 改成范围条件create_time >= ... AND create_time < ... |
隐式类型转换，如WHERE phone = 13800138000，phone是varchar | 发生类型转换后索引列被视为函数处理 | 查询参数写成字符串，保持类型一致 |
LIKE '%keyword' | B+树只能按前缀匹配，前导通配符破坏了顺序 | 改用前缀LIKE 'keyword%'，或上全文索引 |
OR条件连接非索引列 | OR两边任意一边不能走索引，整体降级 | 改写为UNION，或确保OR两边都有索引 |
NOT IN、!= | 范围扫描的边界条件不满足索引定位 | 视业务改写为IN或范围查询 |
| 联合索引跳过了最左列 | B+树排序逻辑根本用不上 | 调整查询条件或索引列顺序 |
| 优化器认为全表扫描更快 | 表数据量小或查询返回比例太高 | 重新设计索引，或检查统计信息是否过期 |
6.2 explain实战：看穿执行计划
排查索引问题时，我最依赖的工具就是EXPLAIN。它的核心列就几个，看懂了基本能定位问题。type一列的值从好到差依次为system > const > eq_ref > ref > range > index > ALL，看到ALL基本就是全表扫描，是慢查询的重灾区。key列告诉你实际用到的索引是什么，key_len表示用到了联合索引的多少前缀列，这个数字变化很大——都是联合索引，用得深不深，它是客观证据。rows是估算扫描的行数，行数越大越危险。Extra列如果出现Using filesort，意味着排序没走索引，额外多了一次排序操作，这在海量数据下非常耗时。
举一个最常见的场景：
EXPLAIN SELECT * FROM orders WHERE user_id = 10086 AND status = 1 ORDER BY create_time DESC LIMIT 20;建了(user_id, status, create_time)联合索引后，type从ALL或index变成了ref，Extra里的Using filesort消失，说明排序也直接利用上了索引顺序。看到这个变化，就可以放心地把这个索引固化下来。排查慢查询的时候，先看type、再看rows、最后查Extra，十有八九能定位问题。
6.3 自检：索引设计的几条经验法则
建索引之前，先回答几个问题：WHERE条件里哪些列是等值、哪些是范围？SELECT需要哪些列，能不能覆盖？这个索引会用在哪些SQL上，会不会同时服务多个查询？回答完再动工。
几条经过检验的经验法则：
- 数据量小（几千行的维度表），别建索引，全表扫描最快。
- 索引列不要参与任何运算，包括函数、类型转换、四则运算。
- 优先用联合索引替代多个单列索引，别让单列索引“各自为政”。
- 索引数量控制在单表5个以内，索引会拖慢写入和存储空间。
- 更新频繁的列慎建索引，每次更新都要同步维护B+树。
- 排序字段能进联合索引就进，避免Using filesort。
这些经验不是书上看来的，是线上事故和慢查询日志教出来的。数据结构决定了理论边界，explain决定了实际效果，两个都抓牢，才能少踩坑。
我个人最大的体会是：数据结构课上学B树、B+树时觉得它们离业务很远，像个概念性的东西；工作几年后发现，数据库的所有性能问题最后都要回到这颗树上找答案。别看B+树只有两三层的“身高”，它承载的是整个InnoDB的存储世界，理解它能让你面对索引问题时真正站到底层视角。遇到慢查询别急着加索引，先停下来想想这颗树是怎么排序、怎么查找的，往往答案自己就浮出来了。
