深入理解MySQL索引：B+树为何成为查询加速的基石？

1. 为什么“索引能变快”这个问题值得从头讲一遍很多人在 MySQL 里建过索引也知道“加了索引查询就快了”但要真被问一句“为什么索引能加快查询速度”的时候往往只能答出“因为索引是 B 树”。再往下问“那 B 树到底是怎么把查询变快的”就开始卡壳了。这个卡壳很正常。因为数据库把很多事情都封装好了我们平时写 SQL 只需要关心表和字段压根看不到底层的树长什么样。但索引恰恰是整个数据库里最值得花时间搞懂的一个点它决定了查询速度的上限。你一旦想明白了 B 树为什么是索引的默认方案再去理解主键索引、覆盖索引、联合索引的最左前缀、回表这些概念都会顺畅很多因为底层逻辑是同一套。这篇文章不谈虚的我会拆开 B 树把“索引为什么快”这件事按原理讲清楚。你不用有数学基础也不需要提前懂什么数据结构只要跟着思路走就行。讲到关键参数时我会把公式和数字摆出来尽量做到看完之后能自己算“这棵树到底能装多少数据”。其中有些内容是我在实际优化 SQL 和排查慢查询时反复用到的所以写到后面也会顺带分享一些踩坑经验。比如索引不是越多越好、为什么某些情况下 MySQL 会放弃索引、为什么有些历史版本里会出现“sysindexes 找不到索引对应行”这类麻烦问题都会串在一起讲。2. 在聊 B 树之前先搞清楚查询慢在哪2.1 全表扫描到底慢在哪先说一个最基础的场景。假设你有一张用户表里面有 1000 万行记录现在要执行一条查询SELECT * FROM users WHERE id 9999999;如果这张表上没有任何索引MySQL 只能做全表扫描从第一行数据开始一行一行去对比 id 是否等于 9999999直到找到目标记录为止。最坏情况下要找 1000 万次。这里要注意数据库里的一次“查找”并不是 CPU 里的一次比较而是要涉及磁盘 I/O 的。数据在磁盘上不是一个整体而是按固定大小分成很多数据页通常 16KB 一页。InnoDB 读取数据的最小单位就是一页哪怕你只需要一行数据也要先把这一行所在的整个数据页从磁盘加载到内存里。所以全表扫描的代价本质上是“把所有数据页从磁盘读一遍”的代价。数据量越大需要读的页就越多耗时就越长。这跟你在一个几千页的 PDF 里用 CtrlF 找一句话一样它能找但前提是得把整份文档扫完。2.2 查询优化的核心减少磁盘读取次数明白了全表扫描的瓶颈是磁盘 I/O那优化的思路就非常清晰了让查询只读少量数据页而不是把整张表翻一遍。怎么做到最简单的办法就是给数据建一个目录。想象你在一所大学里要找一名学生如果没有任何索引就需要把全校每个学生的档案都打开看一遍。如果有了一张按学号排序的学生信息表你就可以直接翻到“学号在 9999999 附近”的区域只查那几页档案。数据库里的思想也一样索引就是一种有序的结构。有了索引之后查询路径从“扫描全表 N 页”变成了“顺着索引结构快速定位目标页”。关键在于索引这种结构本身要让磁盘读取次数尽可能少。这就引出了数据结构选型的问题能把数据组织成有序结构的东西很多数组、二叉树、哈希表、B 树都行那为什么最终 B 树成了主流数据库的默认选择答案要从每一层数据结构的特点说起。3. B 树是怎么把查询变成“对数级”的3.1 多路查找树矮才是王道如果让一个不了解数据库的人来设计索引他最可能想到的是用二叉查找树。二叉树有一个非常突出的优点结构简单左小右大每次比较都能排除一半数据。比如有 1000 万条记录二叉查找树的查找次数大约是 log2(1000万)也就是大约 24 次比较。24 次听起来不多但问题是这个树的每个节点通常对应磁盘上的一个页而每访问一个节点都是一次磁盘 I/O。24 次磁盘随机读在全表扫描面前确实快得多但仍然不够理想。B 树的核心改进是把“二叉”变成了“多叉”。一个节点里可以同时存储很多个键值以及指向下一层节点的指针。这样一来树的层数会大幅下降。数据量不变的情况下树的高度越低查询要经历的磁盘 I/O 次数越少。3.2 算给你看一棵 3 层的 B 树能存多少数据我在给团队讲这块的时候最喜欢算一笔账。InnoDB 里默认页大小是 16KBB 树的每个节点就是一个数据页。先看非叶子节点。非叶子节点不存真实数据只存“键值 子节点指针”。假设主键是 BIGINT占 8 字节指针在 InnoDB 里大约占 6 字节。那么一个非叶子节点能存储的键值对数量大约是16384 / 14 ≈ 1170也就是说一个非叶子节点可以分出 1170 个分支。再看叶子节点。叶子节点存的是完整的行记录按一行的数据量来算。假设一行数据平均是 1KB那么一个 16KB 的页里大约能放 16 行记录。把这两个数乘一下一棵高度为 3 的 B 树能存放的数据量是1170 × 1170 × 16 ≈ 2190 万行注意树的“高度”是从根节点到叶子节点的层次数。高度为 3 意味着只需要读取 3 个数据页根节点页、中间层页、叶子节点页。也就是说对于 2000 多万行的表通过主键索引查询只需要 3 次磁盘 I/O。同样是 2000 万行全表扫描可能需要读取 130 万个数据页。这就是天壤之别。3.3 非叶子节点只存键、叶子节点才存数据这个设计很妙你有没有想过为什么不让所有节点都存数据如果中间节点存了数据浪费了空间一个页能承载的分支数就少了。分支少了树就会变高查询要读的页就变多。B 树干脆规定所有数据只存在叶子节点非叶子节点纯粹是个“目录”。这样每个目录页都能放满键值和指针大约 1170 个分支从而让整棵树变得非常“矮胖”。这和现实中图书馆的索引卡片有点像卡片柜只放书名和书架编号不会把书的内容也抄一遍。另外还有个细节是叶子节点之间会通过链表串起来。这样做的好处是范围查询特别方便比如查询 id 在 100 到 200 之间的所有记录只要定位到 100 这个键所在的叶子节点然后顺着叶子节点之间的链表顺序往下走就行了不需要跳回上层重新搜索。3.4 B 树定位一条记录实际经历的几个步骤我现在把一次索引查询的完整路径写一遍。假设我们要执行SELECT * FROM users WHERE id 500;步骤如下从 B 树的根节点开始读取根节点所在的数据页。根节点里有若干个键值比如 100、300、600根据 500 在这些键值之间的位置确定走哪个子节点指针。顺着指针读取第二层的数据页重复同样的比较逻辑确定下一层方向。一直走到叶子节点。在叶子节点内部做线性查找或二分查找找到目标记录。如果叶子节点存的是整行数据就直接返回结果。如果这个索引不是主键索引叶子节点存的是主键值那么还要根据主键值回到聚簇索引再查一次这个动作叫回表。整个过程下来读取的页数基本稳定在数据页层数级别也就是高度 H 次。B 树的高度一般不会超过 4因为超过 4 层需要的数据量已经非常惊人了。4. 为什么偏偏是 B 树而不是哈希、二叉树、B 树4.1 哈希索引等值查询快但范围查询直接歇菜哈希索引的优势是等值查询比如 WHERE id 500它能做到近乎 O(1) 的查找速度。但真实业务里很少有“只要等值查询不用范围查询”的场景。你总会写大于、小于、BETWEEN、ORDER BY 这类语句。哈希索引的本质是把键值通过哈希函数算成一个存储位置它天生不保持顺序。所以一旦涉及范围查询哈希索引就需要把整个哈希表遍历一遍性能极差。而且哈希索引也不支持前缀匹配对 LIKE abc% 这种查询毫无办法。相比起来B 树本身是有序的。键值从小到大排列叶子节点之间还是双向链表。所以等值查询能走范围查询也能走排序也能走适用面广得多。4.2 二叉搜索树平衡问题让树容易变高二叉搜索树在数据随机插入时表现不错但一旦数据有序插入比如按递增的主键 1、2、3、4… 依次写入二叉树就会退化成一条链表。查询复杂度从 O(log n) 退化到 O(n)。红黑树能解决平衡问题它保证左右子树高度差不会超过太多维持查找复杂度 O(log n)。但红黑树毕竟是二叉树每个节点最多两个子节点。对于同样的 1000 万数据红黑树的深度大约在 20 到 25 之间也就是最坏情况下要读 20 多层。每读一层都是一次磁盘 I/O代价依然太高。B 树通过多叉结构把树的高度压到了 3 到 4 层天然比二叉树更适合磁盘访问。4.3 B 树和 B 树比差在哪B 树是 B 树的“前身”它的特点是所有节点都能存数据。表面上看这有利于数据访问因为可能在中间层就找到目标记录了。但这个特点放到磁盘场景里反而是劣势中间节点存数据导致一个页能存的分支数变少树变高平均 I/O 次数增加。数据分散在所有节点里做范围查询时要在中序遍历上花费更多功夫而且需要跨层访问。B 树把数据全部集中在叶子节点天然形成了一条有序链表范围查询、排序、聚合统计都更有优势。所以在现代关系型数据库里B 树几乎成了标配。4.4 16KB 数据页这个参数也有讲究数据库里的页大小直接影响树的扇出和整体性能。页太大单个叶子节点里能装的行多但读取一页的 I/O 开销也高。页太小树的层数变高。InnoDB 默认 16KB 是在“单次磁盘 I/O 成本”和“单页能容纳的数据量”之间做的一个折中。理解这个参数后你就知道为什么很多调优文章会建议“主键不要太长”了。主键越长非叶子节点里每条索引项占的空间越大一个页能容纳的分支数就越少树就容易变高最终直接拖慢查询。5. 从 B 树原理回到真实数据库MySQL 里的索引到底长什么样5.1 主键索引就是聚簇索引在 InnoDB 引擎里表本身就是一个以主键为排序依据的 B 树。这句话很重要——InnoDB 的数据文件不是乱堆放行的每一行的实际存储位置是按主键顺序组织在聚簇索引的叶子节点里的。所以对 InnoDB 来说主键不仅仅是一种约束它直接决定了数据的物理排列。这也是为什么强烈建议主键用自增 ID 或者有序 ID。如果主键是随机生成的 UUID新插入的行可能落在已有数据页的中间位置导致频繁的数据页分裂写入性能会明显变差。5.2 二级索引和回表为什么有时查询还是慢二级索引也是一棵 B 树但它的叶子节点存储的不是完整行记录而是“索引列的值 主键值”。当你通过二级索引查数据时第一次查询只是找到了主键还需要拿着这个主键再回到聚簇索引里查一次完整记录这就是回表。回表意味着多一次 B 树查找多几次磁盘 I/O。如果一次查询命中了大量二级索引记录然后每条都要回表那性能可能反而不如全表扫描。那怎么避免回表很简单如果查询所需的所有字段都包含在索引里MySQL 在二级索引的叶子节点里就能拿到全部数据不需要回表这叫做覆盖索引。设计索引的时候你要尽量让自己常用的查询能用上覆盖索引。5.3 联合索引的最左前缀原则是 B 树排序规则的延伸联合索引就是把多个列合并成一个索引比如INDEX idx_user_age_city (age, city)。这个索引的底层 B 树先按 age 排序在 age 相同的情况下再按 city 排序。因为这个排序顺序查询条件里如果只写 city不走联合索引。因为整个 B 树是按 age 作为第一关键字排序的city 在树里只是局部的次级有序没法单独利用。如果你只查 age那走索引没问题查 age 和 city走索引也没问题查 city 和 ageMySQL 优化器通常也能自动调整条件顺序仍然走索引。核心原则就是最左列必须在查询条件里。这一点理解了你就能解释很多“为什么加了索引但没用上”的问题。比如索引是(a, b)你只查WHERE b 1索引就是从根节点开始都无法定位优化器只能放弃。5.4 MySQL 什么时候会放弃索引很多初学者会发现明明字段上建了索引执行计划里却是全表扫描。原因一般有这么几类查询条件对索引列做了函数处理比如WHERE YEAR(create_time) 2024索引会失效。隐式类型转换比如索引字段是字符串但查询条件里用了数字MySQL 需要先把字段转成数字再比较索引也容易失效。查询结果集占比太大。如果优化器算出来读取索引回表的成本比全表扫描还高它会选择全表扫描。典型场景是查询条件能命中表中 30% 以上的行。统计信息过期导致优化器做出了错误判断。这种情况通常可以用ANALYZE TABLE刷新统计信息。6. 面试和实战中经常出现的概念盘点6.1 聚簇索引和非聚簇索引的区别一句话版本聚簇索引的叶子节点存的是整行数据非聚簇索引的叶子节点存的是索引键和主键值。InnoDB 的主键索引就是聚簇索引MyISAM 里的索引都是非聚簇索引索引文件和数据文件是分开的。6.2 索引能加快排序和分组吗能。因为 B 树天然有序如果查询的 ORDER BY 字段正好是索引字段MySQL 可能直接用索引顺序输出结果不需要额外做 filesort 操作。同理GROUP BY 也可能会借助索引减少分组时的临时表操作。但要注意只有排序顺序和索引顺序一致时才能利用这个特性。比如索引是(a, b)你写ORDER BY a ASC, b DESC这里因为升降序不一致索引就走不上排序优化了。6.3 视图能加快查询速度吗很多人会问这个问题其实答案很直接普通视图只是保存了一条 SQL 定义不保存数据。查询视图时本质上还是去查底层表它不会自动提升查询速度。只有物化视图具体化视图才会预先存储结果但 MySQL 官方内置的普通视图并不物化。所以不要指望“建个视图就能让查询变快”视图的价值是逻辑封装和权限控制不是性能提升。6.4 主键索引和唯一索引的关系主键索引天然是唯一索引一张表只能有一个主键但可以有多个唯一索引。主键在 InnoDB 里还承担着聚簇索引的定位作用是物理存储的组织者。唯一索引约束数据唯一但它的叶子节点存的是主键不是完整行。6.5 分页慢的问题和索引有什么关系LIMIT 2000000, 10这种深分页慢是因为 MySQL 要先扫描并跳过前 2000010 条记录。即使走索引记录本身也是从叶子节点一条条数过去的。比较常用的优化思路是延迟关联先用覆盖索引查出目标主键再用主键去关联原表取完整行。因为二级索引 主键构成的索引树通常比聚簇索引小很多所以扫描成本低一些之后再统一回表效率会好不少。7. 实际排查索引问题时的几个经验和快查表7.1 一个经典报错sysindexes 找不到对应索引行有一次我在排查一个老环境里的数据库启动异常时遇到了一个非常冷门的报错“未能在 sysindexes 中找到数据库 id 9 中对象 id 1 的索引 id 1 对应的行”。这类问题经常出现在比较老的数据库版本里尤其是经历过非正常关机、磁盘损坏或者大量并发 DDL 之后。sysindexes 是传统系统表用于记录表、索引和统计信息。当索引定义在系统表里丢失或不一致时数据库就可能认为某些索引行对应不上。排查思路一般是先确认是不是统计信息或索引元数据损坏尝试更新统计信息。对于损坏严重的场景考虑重建索引。如果连系统表都无法正常访问那通常需要离线修复或者从备份恢复。这类问题现在新版本里已经很少出现了但它提醒我一件事索引并不只是加快查询的东西它也是一份需要维护的元数据。索引一旦损坏数据库整个可用性都会受影响。7.2 索引越多越好吗不是。每多一个索引写入数据时就要额外维护一棵 B 树的增删改。表上的索引越多INSERT、UPDATE、DELETE 的代价就越大。索引还会占额外的磁盘空间内存缓冲池里也要给它们留位置。我的实操习惯是先根据慢查询日志找出真正需要优化的高频 SQL再针对这些 SQL 设计索引。那种“把所有常用字段都加上索引”的做法往往会让系统在写入量大的时候吃大亏。7.3 检查索引是否生效的常用方法最直接的办法是看执行计划。MySQL 里用EXPLAIN就能看到查询走了哪个索引大致扫了多少行有没有回表有没有 filesort。我一般重点看这几个字段type如果出现 all说明全表扫描要警惕如果出现 ref、range、const证明索引用上了。key实际使用的索引名。rows预计扫描的行数行数越少通常越好。Extra如果出现 Using filesort 或者 Using temporary说明排序或分组没有走索引要考虑优化。我遇到过很多开发上来就说“慢查询加了索引还是慢”结果一执行计划发现type index看起来走了索引实际是把整个索引树扫了一遍。这种情况要么是条件列无法有效定位要么是回表次数太多需要重新设计索引。7.4 索引偶发失效的快速定位思路如果某个查询平时走索引某天突然变得很慢我一般按这个顺序排查看执行计划是否发生变化。很多时候是统计信息过期ANALYZE TABLE刷新一下就行。看查询条件里是否有隐式类型转换。字段类型和传入参数类型不一致MySQL 会做隐式转换导致索引失效。看 SQL 里是否故意加了函数或表达式。看数据分布是否改变优化器可能认为走索引不划算。如果是生产环境还要考虑是否有内存和磁盘性能下降导致 I/O 变慢而不是索引本身失效。7.5 业务侧的索引设计我给几个老实践第一字符串字段做索引时尽量使用前缀索引不要整个长字符串都索引。比如一个 URL 字段可能只需要索引前 50 个字符既节省空间也提升叶子节点的容量。但要注意前缀索引不支持覆盖索引也无法用于 ORDER BY。第二联合索引的字段顺序要按“选择性”来排。选择性越高的字段放到越靠左能让索引更快收敛。比如性别字段选择性很低放最左边意义不大。第三频繁更新的字段不适合做长索引。更新一列如果这列在索引里意味着 B 树叶子节点可能发生分裂、合并代价很高。8. 索引不只存在于数据库里Lucene、缓存和其它存储里的索引聊到索引很多人会以为只有数据库才有。其实“用索引加快查询速度”这个思想在整个计算机系统里到处都是。热搜词里出现了 Lucene 索引库的维护与查询这里顺带提一下对理解通用原理也很有帮助。Lucene 是搜索引擎底层的核心库它也有索引但它的索引结构和 B 树不完全一样。Lucene 的倒排索引更适合“根据关键词找文档”这种搜索场景而数据库的 B 树索引更适合“根据条件找精确记录或范围记录”。两者的目标一样都是在海量数据里减少无谓扫描只是数据结构选择了不同方向。工业级搜索引擎在 Lucene 之上还会把多个 Segment 合并管理并在内存里维护类似“跳表”的结构来加速查找。你看只要数据量大到一定程度“如何快速定位目标”就成了绕不开的核心问题而索引就是最通用的解法。缓存系统里也有索引的变体。有些场景用类似跳表的结构做有序集合有些场景用哈希索引做点查询有些场景用 LSM 树做写入友好的索引。它们本质上都在回答同一个问题查询怎样能少读点数据。理解了这一点你会发现学习 B 树不是选择题而是一种学习迁移能力。你掌握了“树高度决定 I/O 次数”“叶子节点有序链支持范围查询”之后再看其它存储系统的索引方案思路会清晰得多。9. 我自己的一个小习惯写 SQL 前先想清楚数据访问路径做了这么久的数据库优化我自己最大的一个体会是索引不是加在字段上的而是加在“数据访问路径”上的。同样一个字段在等值查询、范围查询、排序、分组、多表关联里对索引结构的要求并不完全一样。你设计索引时不应该只盯着单个 SQL而是要盯着这个表最核心的访问模式。我在给业务系统设计索引时通常会拿出一张白纸把这个表最主要的查询路径画出来主键查询是一种路径按用户 ID 查最近订单是另一种路径按状态和创建时间做后台筛选又是另一种路径。每一条路径对应一个合适的索引。路径多了就要斟酌合并和取舍因为索引并非免费的午餐。有一次优化一个订单分页查询最初表上有 7 个索引结果写入特别慢。我梳理路径后发现很多索引其实覆盖了相似的查询场景。最后我把索引合并成 3 个联合索引查询性能没有下降写入和磁盘占用却明显改善了。这就是理解索引底层原理带来的实际收益。最后分享一个不算技巧、但很实用的提醒不要等到线上报警了才去看慢查询。现在就在测试环境把核心 SQL 的执行计划跑一遍看看 rows 的预估行数看看有没有 Using filesort有没有因为数据量还很小时优化器给出的次优选择。趁数据量小的时候把这些习惯养好等数据真的涨起来你就不会慌。