SELECT * FROM users WHERE name 张三 用了 0.5 秒你该了解一下索引了。一、开场白为什么你的查询比蜗牛还慢想象一下这个场景你在一个有一亿条记录的表里查一条数据没有索引。MySQL 的表情大概是这样的好的我从第一行开始看……第二行……第三行……第 87,432,651 行……找到了这就是传说中的全表扫描Full Table Scan——像在没有目录的字典里找一个字一页一页翻。效率感人老板流泪。那么索引是什么索引就是书的目录。想翻到第 5 章不用从第 1 页开始翻直接看目录跳过去搞定。但问题来了MySQL 的索引用的是什么数据结构为什么不用二叉树为什么不用 Hash为什么偏偏是B 树坐好我们从头讲起。二、先认识几个候选人在 MySQL 选择索引数据结构的路上有好几个候选人来面试。让我们看看它们各自的表现。2.1 二叉搜索树BST第一个被淘汰的选手二叉搜索树的逻辑很简单左子树所有值 根节点 右子树所有值。查找时间复杂度是 O(log n)看起来不错对吧但问题在于它太瘦高了。一棵存了 100 万条记录的二叉树高度大约是 20 层。每读一个节点就是一次磁盘 I/O后面会详细讲20 次磁盘 I/O……你的查询还没返回咖啡都凉了。更可怕的是如果插入的数据是有序的比如自增主键二叉搜索树会退化成一条链表查找变成 O(n)——比全表扫描好不了多少。二叉搜索树面试时说我能 O(log n) DBA 问你有多少层 20 层。 下一位。2.2 红黑树 / AVL 树矮是矮了但还是太瘦红黑树和 AVL 树是自平衡的二叉树保证了树的高度不会太高。Java 的TreeMap、C 的std::map底层就是它们。但问题是它们每个节点只有两个子节点二叉嘛。即使平衡了100 万条数据仍然需要大约 20 层。20 层 20 次磁盘 I/O 20 次去磁盘上找一下 20 次灵魂拷问。红黑树我有颜色我自平衡 DBA你有几个孩子 两个。 太少了。下一位。2.3 Hash 表速度飞快但偏科生Hash 表的查找速度是O(1)——常数时间不管你有多少数据一次哈希计算直接定位。听起来完美但 Hash 表是个严重的偏科生❌不支持范围查询WHERE age 18Hash 表一脸懵逼我只知道等于大于是什么❌不支持排序ORDER BY nameHash 表顺序是什么能吃吗❌不支持最左前缀匹配联合索引Hash 表我只认完整的 key。❌存在哈希冲突数据量大了以后不同的 key 可能映射到同一个位置需要遍历链表。MySQL 中只有Memory 存储引擎默认使用 Hash 索引InnoDB 有一个自适应哈希索引Adaptive Hash Index但那是自动的你没法手动控制。Hash 表面试时说我 O(1) DBA范围查询呢 不会。 排序呢 不会。 那你来干嘛 ……我快。 快有什么用功能不全啊。下一位。2.4 B 树B-Tree优秀但可以更好B 树是一种多路平衡查找树每个节点可以有多个子节点不只是两个。这意味着同样数据量下B 树比二叉树矮得多。B 树的特点每个节点既存索引 key也存数据 data所有叶子节点都在同一层一个节点可以有多个子节点比如 100 个100 万条数据B 树可能只需要3-4 层。3-4 次磁盘 I/O 就能定位数据比二叉树的 20 次好太多了但 B 树有一个问题每个节点都存了数据 data导致每个节点能存的 key 数量变少了树就相对变高了。而且 B 树的叶子节点之间没有指针相连范围查询需要中序遍历整棵树效率不够好。B 树面试时说我矮我多路我平衡 DBA不错。但你每个节点都塞数据太胖了。有没有更精简的方案 B 树看了一眼旁边的弟弟……我弟可以。三、B 树最终赢家登场B 树是 B 树的改良版也是 MySQL InnoDB 存储引擎的默认索引结构。如果说 B 树是一个人既当厨师又当服务员那 B 树就是专人专事——非叶子节点只负责索引叶子节点才存数据。3.1 B 树 vs B 树核心区别特性B 树B 树非叶子节点存数据✅ 存❌ 不存只存 key叶子节点链表❌ 没有✅ 有双向链表范围查询需要中序遍历沿链表顺序扫描即可查询稳定性不稳定可能在任意层找到稳定一定走到叶子节点每个节点能存的 key 数较少因为存了 data较多只存 key3.2 为什么 B 树这么矮胖这是 B 树最大的优势矮胖。来算一笔账。InnoDB 的一个页Page大小是16KB。假设一个索引 key 是 8 字节比如 bigint一个指针是 6 字节那么一个页大约能存16384 / (8 6) ≈ 1170个 key两层 B 树根节点 1170 个 key每个指向一个叶子节点每个叶子节点假设存 100 条数据 → 可以存储1170 × 100 117,000条数据三层 B 树1170 × 1170 × 100 ≈ 1.37 亿条数据也就是说1.37 亿条数据只需要 3 次磁盘 I/O 就能定位B 树我 3 层楼就能装 1.37 亿条数据。 红黑树我需要 20 多层。 B 树哦。 凡尔赛本赛3.3 叶子节点的链表范围查询的神器B 树的叶子节点之间通过双向链表连接。这意味着范围查询WHERE age BETWEEN 18 AND 30先定位到 18然后沿着链表往后扫到 30完事。ORDER BY链表本身就是有序的排序零成本。全表扫描只需要遍历叶子节点链表不需要遍历整棵树。这就是为什么 B 树在数据库场景下吊打其他数据结构的原因。四、InnoDB 中的索引聚簇索引 vs 二级索引讲完了数据结构我们来看 MySQL InnoDB 中索引的具体实现。这里有两个核心概念聚簇索引Clustered Index和二级索引Secondary Index。4.1 聚簇索引数据本身就是索引InnoDB 的聚簇索引有一个非常特别的设计叶子节点存储的是完整的行数据。也就是说聚簇索引的叶子节点 数据页。数据和主键索引是一体的表数据本身就是一棵 B 树。这就像一本字典目录和正文是合在一起的——找到目录项就直接看到了释义。InnoDB 选择主键作为聚簇索引的 key。如果没有定义主键InnoDB 会选一个唯一的非空索引如果还没有InnoDB 会自动生成一个隐藏的 6 字节 ROW_ID 作为主键。4.2 二级索引回表的代价除了主键索引你创建的其他索引比如INDEX idx_name (name)都是二级索引。二级索引的叶子节点存储的不是完整行数据而是主键值。查找流程在二级索引的 B 树中找到name 张三得到主键值id 42拿着id 42去聚簇索引主键索引的 B 树中再查一次得到完整行数据这个过程叫回表Back to Table——就像你先在作者索引里找到了书名再去书架上找那本书。二级索引我找到了张三的 id 是 42。 DBA然后呢 二级索引然后你自己去主键索引里找完整数据吧。 DBA……你就不能一次性给我 二级索引不能我只存了主键。告辞。4.3 覆盖索引避免回表的优化技巧如果你查询的字段刚好都在二级索引里就不需要回表了。这就是覆盖索引Covering Index。-- 假设有索引 INDEX idx_name_age (name, age) ​ -- 需要回表SELECT * 需要所有字段 SELECT * FROM users WHERE name 张三; ​ -- 不需要回表name 和 age 都在索引里 SELECT name, age FROM users WHERE name 张三;在EXPLAIN中如果看到Using index说明用到了覆盖索引没有回表。覆盖索引你要的字段我都有别回表了。 DBA你真是个好索引。 覆盖索引那当然。我可是精心设计的。五、联合索引与最左前缀原则5.1 联合索引的 B 树长什么样假设你有一个联合索引INDEX idx_abc (a, b, c)B 树的排序规则是先按 a 排序a 相同的按 b 排序b 相同的按 c 排序。就像字典先按拼音排序拼音相同按声调排序声调相同按笔画排序。5.2 最左前缀原则这是面试高频考点也是日常开发最容易踩坑的地方。-- 有索引 INDEX idx_abc (a, b, c) ​ -- ✅ 能用到索引 WHERE a 1 WHERE a 1 AND b 2 WHERE a 1 AND b 2 AND c 3 ​ -- ✅ 能用到部分索引只用到 a WHERE a 1 AND c 3 ​ -- ❌ 用不到索引 WHERE b 2 WHERE b 2 AND c 3 WHERE c 3为什么因为 B 树是按(a, b, c)的顺序排序的。如果你不给 a直接查 b就像字典里没有拼音直接找声调——完全无从下手。最左前缀原则你得先告诉我 a 是什么我才能帮你找 b。 开发者那我直接查 b 呢 最左前缀原则那你自己全表扫描吧我帮不了你。 开发者……5.3 索引下推Index Condition Pushdown, ICPMySQL 5.6 引入了索引下推ICP优化。对于联合索引(a, b, c)WHERE a 1 AND c 3在没有 ICP 的时候MySQL 在索引中找到a 1的所有记录然后全部回表再在 server 层过滤c 3。有了 ICP 之后MySQL 在索引中找到a 1的记录后直接在存储引擎层检查c 3不满足条件的就不回表了。减少了回表次数。ICP虽然你没按最左前缀查 c但我在索引里帮你先过滤一波少回几次表。 DBA你真是个贴心的优化器。六、磁盘 I/O为什么少读几次这么重要6.1 磁盘 vs 内存速度差了 10 万倍这里要科普一个关键知识点磁盘 I/O 是数据库最大的性能瓶颈。存储类型访问时间L1 缓存~1nsL2 缓存~4ns内存RAM~100nsSSD~100μs100,000nsHDD 机械硬盘~10ms10,000,000nsHDD 比内存慢10 万倍。每一次磁盘读取CPU 都要等很久。这就是为什么 B 树的矮胖特性如此重要——树矮一层就少一次磁盘 I/O。从 20 层降到 3 层意味着从 20 次磁盘 I/O 降到 3 次查询速度提升了一个数量级。6.2 局部性原理与预读操作系统和磁盘有一个优化机制叫局部性原理Principle of Locality时间局部性最近访问的数据很可能马上又会被访问空间局部性访问了某个地址附近的数据很可能也会被访问基于这个原理操作系统在读取磁盘时不会只读一个字节而是预读Read-ahead一整个页通常 4KB。InnoDB 正是利用了这一点它的页大小是16KB默认每次读取一个完整的页。B 树的一个节点就是一个页所以读一个节点 一次磁盘 I/O 读 16KB 数据。操作系统你要读一个字节我给你读 4KB反正你大概率会用到旁边的数据。 InnoDB那我要 16KB。 操作系统你是有多贪 InnoDB我一个节点就这么大。七、实战索引设计的军规理论讲完了来点实战建议。7.1 选择性Cardinality是关键选择性 不重复的索引值 / 数据总记录数选择性越高索引效果越好。比如gender性别字段只有 M/F 两个值选择性 ≈ 2/N ≈ 0建索引基本没用email字段几乎每个值都不同选择性 ≈ 1非常适合建索引-- 查看索引选择性 SHOW INDEX FROM your_table; -- 看 Cardinality 列7.2 覆盖索引优先尽量让查询的字段都在索引里避免回表-- 差SELECT * 无法覆盖索引 SELECT * FROM orders WHERE user_id 100; ​ -- 好只查需要的字段且都在索引里 SELECT order_id, amount FROM orders WHERE user_id 100;7.3 不要在索引列上做函数操作-- ❌ 索引失效 SELECT * FROM users WHERE YEAR(create_time) 2024; ​ -- ✅ 改成范围查询 SELECT * FROM users WHERE create_time 2024-01-01 AND create_time 2025-01-01;在索引列上使用函数、表达式、隐式类型转换都会导致索引失效MySQL 只能走全表扫描。开发者我在索引列上加了个函数索引怎么不生效了 MySQL你在我精心排好序的 B 树上做了变换原来的顺序没了我怎么用索引 开发者……好吧。7.4 前缀索引对付长字符串对于VARCHAR(255)这种长字符串字段可以只索引前 N 个字符ALTER TABLE users ADD INDEX idx_email_prefix (email(10));但前缀索引不能用于 ORDER BY 和覆盖索引需要权衡。7.5 索引不是越多越好每个索引都是一棵独立的 B 树需要额外的存储空间和维护成本每次INSERT、UPDATE、DELETE都要同时更新所有相关的索引索引越多写操作越慢一般建议单表索引不超过 5-6 个DBA这个表有 12 个索引。 开发者多索引多保险嘛。 DBA你每次插入一条数据要同时维护 12 棵 B 树。你的 INSERT 语句在哭。八、总结一张图看懂索引选型数据结构查找时间范围查询排序适用场景二叉搜索树O(log n)需遍历需遍历内存数据结构红黑树/AVLO(log n)需遍历需遍历内存数据结构Hash 表O(1)❌ 不支持❌ 不支持等值查询B 树O(log n)中序遍历中序遍历文件系统B 树O(log n)链表顺序扫描天然有序数据库索引B 树胜出的原因总结️矮胖3-4 层就能存储上亿数据磁盘 I/O 次数最少叶子节点链表范围查询、排序、分组都是天然支持非叶子节点不存数据每个节点能存更多 key树更矮查询稳定每次查询都要走到叶子节点性能可预测磁盘友好节点大小 页大小完美利用预读机制九、后记下次当你的 SQL 查询飞快返回时别忘了感谢那棵默默无闻的 B 树。它可能只有 3 层楼高但每一层都是精心设计的。当你的查询慢了先看看EXPLAIN看看索引有没有用上。大部分性能问题都是索引没设计好。记住索引不是万能的但没有索引是万万不能的。DBA 的终极忠告 先看 EXPLAIN再看索引最后才考虑加机器。 如果你的 SQL 需要全表扫描请先反思一下自己的人生选择。参考资源MySQL 官方文档 - B-Tree and Hash IndexesWikipedia - B TreeWikipedia - B-treeInnoDB Diagrams Project (GitHub)