FXJ Wiki

Back
25 min read
中文
八股 /
mysql /
innodb /
b+树 /
索引

MySQL 为什么快：从页结构、索引到 B+ 树

以原始 MySQL 笔记为主，保留基础、索引、B+ 树与执行计划相关整理。
views | comments

收录内容#

  • MySQL 基础与索引

MySQL 基础、索引与 B+ 树#

基础#

SQL 的执行流程#

  • 连接器:使用命令进行连接，经过 TCP 三次握手，且验证用户名密码成功(则读取用户权限)
  • 查询缓存(MySQL8.0 之前)：如果是查询语句，则查询缓存(key-value 形式)
  • 解析 SQL：
    • 词法分析：根据输入识别关键字
    • 语法分析：根据词法分析的结果，判断是否符合语法
      • 若符合语法，则构建出一个 SQL 语法树(方便后面的模块获取 SQL 的类型，字段名，条件等等)
      • 若不符合语法，则直接报错
  • 执行 SQL：
    • 预处理器：
      • 检查表/字段是否存在(对于 MySQL8.0 之前则是在预处理之前，语法分析之后做的检查)
      • 将 select * 扩展为所有列
      • (提升性能：对于重复的语句，可以重复执行)
      • (减少 SQL 注入：参数化查询，变量和查询的结构是分离的)
    • 优化器：负责确定 SQL 查询语句的执行方案
      • 即在表中有多个索引的时候，确定使用哪个索引(EXPLAIN 命令可以使出执行计划)
    • 执行器
      • 调用 read_first_record 指针指向 InnoDB 引擎查询接口，让引擎定位符合条件的记录
        • 若记录不存在，则上报执行器，查询结束
        • 若存在，则返回给执行器，然后执行器判断是否符合条件，符合条件则发送给客户端，然后开始循环(一条一条的查询，只是用户在查询完一起显示而已)
        • 引擎读取完毕后，对执行器返回读取完毕信息，执行器收到信息，退出循环，停止查询

![](./Pasted image 20250528015254.png)

索引下推：在查找 where 后的某个条件的同时会将后面的条件加入判断，减少回表次数(也就是在引擎位置就多过滤了很多，所以可以提升效率)

索引下推的条件: (必须要求有一个合适的索引进行有效的过滤操作，通常是第一个条件)

  • 简单条件：诸如等值条件（=）、范围条件（如 >>、<<、BETWEEN）以及一些非空条件（IS NOT NULL）。
  • 组合条件：对于使用逻辑运算符（如 AND、OR）连接的条件，可以对简单条件进行组合下推。

SQL 的存储#

数据库文件存放位置：/var/lib/mysql/<database> 对于该路径下：

  • db.opt：存储数据库的默认字符集和字符校验规则
  • .frm：存储表结构
  • .ibd：存储表数据(独占表空间文件)
    • 对于表空间文件的结构：![](./Pasted image 20250528124745.png)
    • 行：表的记录按照行存放
    • 页：表的记录按照页进行存储， 数据库的读取按照页为单位，整体读入内存(也是 InnoDB 引擎磁盘管理的最小单位)
      • 对于每次读取数据：
        • 首先检查缓存层（缓冲池）以获取数据。
        • 如果数据不在缓存中，则访问数据文件。
        • 根据索引快速定位数据。
        • 最后读取数据页以获取实际的行数据。
    • 区：在表中数据量大的时候，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照区（extent）为单位分配。每个区的大小为 1MB，对于 16KB 的页来说，连续的 64 个页会被划为一个区，这样就使得链表中相邻的页的物理位置也相邻，就能使用顺序 I/O 了。
      • 这里是由于相邻的页在物理位置上不一定相邻，磁盘查询时会有大量随机的 IO(非常慢)，所以需要让相邻的页物理位置也相邻就可以使用顺序 IO，范围查询时就很快
    • 段是由多个区（extent）组成的。段一般分为数据段、索引段和回滚段等。
  • InnoDB 的行格式：(Redundant、Compact、Dynamic 和 Compressed)
    • ![](./Pasted image 20250528140000.png)
    • 记录的额外信息
      • 变长字段长度列表，逆序存放(Q: 这里的逆序是怎么个逆序法?为什么要逆序存放？)
        • 因为记录头信息中有一个指向下一个记录的指针，指向的是下一条记录的记录头信息和真实数据之间的位置,向左读记录头信息，向右读则是真实数据
        • 使得位置靠前的记录的真实数据和数据对应的字段长度信息可以同时在一个 CPU Cache Line 中，这样就可以提高 CPU Cache 的命中率。
      • NULL 值列表：逆序存放
      • 记录头信息:内容比较多，常见的有：delete_mask ，next_record，record_type
    • 记录的真实数据
      • row_id
        • 如果我们建表的时候指定了主键或者唯一约束列，那么就没有 row_id 隐藏字段了。如果既没有指定主键，又没有唯一约束，那么 InnoDB 就会为记录添加 row_id 隐藏字段。row_id 不是必需的，占用 6 个字节。
      • trx_id
        • 事务 id，表示这个数据是由哪个事务生成的。 trx_id 是必需的，占用 6 个字节。
      • roll_pointer
        • 这条记录上一个版本的指针。roll_pointer 是必需的，占用 7 个字节。

若发生了行溢出的情况，又如何存放呢？ 行溢出：即一个页无法放下一条记录，多余的则存放到另外的溢出页中

SQL 的查询上限#

这个问题其实没有一个绝对统一的红线。原笔记里这里原本留了一个空位，我现在把后面优化部分里那套判断标准接回来：不要死背“单表 2000 万”这种数字，更应该看行大小、索引层数、访问模式以及是不是已经出现性能瓶颈。

  • 行特别大时（接近页大小的一半，约 8KB），3 层 B+ 树能容纳的数据量会明显下降，可能只到一两百万级；
  • 行特别小时，3 层 B+ 树理论上能装下非常多的数据；
  • 一个常规业务表，落到千万级数据量时，就应该开始重点观察查询 RT、CPU、IO、索引层数和扫描页数；
  • 真正该考虑分库分表、冷热分离或者归档的时机，不是“到了某个神奇数字”，而是针对这张表的查询已经明显变慢，并且确认是数据量、索引层数或扫描范围带来的问题。

所以面试里更稳的答法是：

  1. 先说没有绝对上限；
  2. 再说常规表到了千万级通常要重点关注；
  3. 最后落回“是否出现实际瓶颈”，比如慢 SQL、B+ 树变高、范围扫描页过多、全表扫描成本过大。

索引#

分类#

按「数据结构」分类：B+tree 索引、Hash 索引、Full-text 索引。 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。 按「字段个数」分类：单列索引、联合索引。

数据结构#

B+ Tree 对于主键和非主键的索引是不一样的：

  • 主键索引：叶子节点存储的是实际数据
  • 二级索引：叶子节点存储的是主键值

回表：对于使用二级索引查询某数据，是先通过二级索引的 b+树索引值找到对应的叶子节点获取主键值，再通过主键索引进行查询，在这个过程中则进行了回表，即需要两个 b+树才能查询到数据

但是当查询的数据能在二级索引中就能查询到，则不需要回表，这个过程叫做覆盖索引

为什么选择 B+树? 小林coding的解释 ↗

  • 相比 B 树：B 树携带的数据量更大，在相同磁盘 IO 情况下能查询的节点更多，但是不够矮胖，且删除节点 B 树的变化比较复杂(B+树则比较稳定)，且 B+树的叶子节点实际上是双向的链表连接的
  • 相比二叉树：
  • 相比 Hash：对于查找某一个值是比较快的(引申如： HashMap)，但是不适合范围查询
B+树！(重)#

[!NOTE] 一个讲的非常醍醐灌顶的描述 InnoDB 的 B+树是如何产生的？

我觉得需要了解的概念：

  • 一个数据页的结构及其每个部分的作用
  • 具体一个数据是如何被填入到 B+树的？如何被构建起来的？

为了形象描述，使用 canvas 进行查看 MySQL思维导图

![](./Pasted image 20250531232615.png) kind of confused:

物理存储#

主键索引(聚簇索引)，二级索引(辅助索引)

字段特性#

从字段特性的角度来看，索引分为主键索引、唯一索引、普通索引、前缀索引。

字段个数#

单列索引，联合索引

[!TIP] 这个地方比较重点！包括最左匹配原则，联合索引范围查询，什么时候索引会失效？

最左匹配原则#

对于联合索引：存在最左匹配原则：需要按照最左优先的方式进行索引的匹配，

若使用联合索引进行查询不遵循这个原则则联合索引会失效

对于联合索引(a,b,c)：则 where 条件为 a=? and b=? and c=? 由于有优化器的存在，这里的顺序可以调换，索引不会失效 而对于 b=? and c=? 等连 a 都没有的情况则联合索引会失效，即能匹配多少匹配多少

联合索引范围查询*#

对于联合索引范围查询: Q1: select * from t_table where a >> 1 and b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

在符合 a>>1 的前提下，b 字段的值实际上是无序的，所以不能根据 b=2 这个条件来减少扫描的记录数量，即 b 字段无法利用联合索引进行查询

Q2: select * from t_table where a >>= 1 and b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

在符合 a>>=1 的前提下，b 字段的值实际上是无序的，但是对于 a=1 的二级索引记录范围里，b 字段的值是有序的！，所以在这里 a,b 字段都利用到了联合索引。

Q3: SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2，联合索引（a, b）哪一个字段用到了联合索引的 B+Tree？

在 MySQL 中这里是>>=2&&<<=8，所以是都可以用到联合索引进行查询的！

Q4: SELECT * FROM t_user WHERE name like ‘j%’ and age = 22，联合索引（name, age）哪一个字段用到了联合索引的 B+Tree？

在符合前缀为‘j’的 name 字段的二级索引记录的范围里，age 字段的值是「无序」的，但是对于符合 name = j 的二级索引记录的范围里，age 字段的值是「有序」的

对于 name='j' and age=20 的情况就会直接忽略，Q4 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

[!NOTE] 注意：这里在查查询 key_len 的时候实际上计算字段占用的长度永远都是 2 字节，因为只是告诉你用了哪些索引字段，而不太倾向于告诉你更加具体的值

具体表现为 EXPLAIN <SQL> 得出的结果，查看 key_len 字段的大小即可

索引下推到底是什么？ ICP 是一种针对索引访问过程中判断条件执行位置的优化策略，它发生在“索引遍历”阶段。 其核心思想是：将部分过滤条件“下推”到索引层面，让索引引擎在扫描索引页时提前过滤满足条件的记录，减少后续回表查询（访问数据行）的次数。 ICP 不是一种新的索引结构，而是在已有索引基础上的一种访问优化。

索引的区分度为：某列的数据去重后的数据个数/数据总数

当区分度很小，特别均匀的时候，则不如不用索引，查询优化器若发现百分比已经达到 30%时，一般会忽略索引进行全表扫描

联合索引进行排序：select * from order where status = 1 order by create_time asc

利用索引的有序性，在 status 和 create_time 列建立联合索引，这样根据 status 筛选后的数据就是按照 create_time 排好序的，避免在文件排序，提高了查询效率。

这里按照(status,create_time)建立联合索引，是先按照 status 排序，然后在 status 内部按照 create_time 进行排序

使用索引的时机#

适合使用索引的场景：

  • 字段有唯一性限制的
  • 经常在 where 条件后面作为查询对象的
  • 经常在 group by 和 order by 条件后面的字段

不适合使用索引的场景：

  • 查询条件后面根本用不到的字段
  • 字段中存在大量重复的数据，即如上所说，可能会忽略索引进行全表扫描
  • 表中数据太少的时候
  • 经常需要进行更新的数据

索引的优化&索引失效#

  • 前缀索引优化：
    • 为了减少索引字段的大小(适用于长字符串的字段)，使用某个字段的前缀作为索引，(可能这样已经能够比较辨识很多字段了，这样就比较省空间/效率)
    • (Q：为什么会有这样的局限性？)局限性：order by 无法使用前缀索引，无法将前缀索引用作覆盖索引
  • 覆盖索引优化；
    • (上面也有讲到) 从二级索引就能得到的数据没必要再次回表，直接返回即可
  • 主键索引最好是自增的；
    • 使用自增的主键，每次插入数据都会按照顺序添加到当前索引节点的位置，不需要进行移动
    • 如果使用非自增主键，则可能会插入到中间位置，其他数据就需要移动来满足新数据的插入，甚至需要从一个页面复制数据到另外一个页面(即页分裂)，页分裂可能会造成大量内存碎片，从而影响效率
    • (页分裂导致碎片，碎片反过来又促使更多页分裂，产生恶性循环，写入性能降低。)
  • 索引最好设置为 NOT NULL
    • 索引列存在 NULL 会让优化器在做选择的时候更加复杂(如进行索引统计的时候，count 会忽略值为 NULL 的行)
    • NULL 是一个没有意义的值，但却会占用至少 1 字节的空间
  • 防止索引失效；(重点)
    • 索引失效的情况：
      • 使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效；
      • 查询条件中对索引列进行了任何计算，都会导致索引失效
      • 没有遵循最左匹配原则
      • where 子句中在 OR 之前的是索引列，之后的不是索引列，则索引会失效
    • 可以使用 EXPLAIN 来进行参考

Q:NULL 作为索引怎么就影响性能了，怎么就变复杂了呢？

  1. B+树中 NULL 会被认定为一个特殊值，会被排在开头/末尾的位置，位置固定且不参与普通值的比较
  2. 无法通过范围扫描快速定位(需要通过 <字段> IS NULL)
  3. 影响优化器的计划

[!NOTE] 索引失效！

  • 使用左/左右模糊匹配

  • 使用函数/表达式计算：当进行计算了，当前的值就变了，所以索引失效？

  • 隐式类型转换：(如字符串和数字的转换，MySQL 中字符串和数字的比较会将字符串转换为数字)

  • 不满足最左匹配原则

  • where 子句中在 OR 之前的是索引列，之后的不是索引列，则索引会失效

eg1：select * from t_user where phone = 1300000001; (phone 字段为字符串) 那么在这个地方会将 phone 转换为 int，即 select * from t_user where CAST(phone AS signed int) = 1300000001; 这里相当于是对字段进行了函数计算，当然会导致索引失效

eg2：select * from t_user where id = "1"; （id 字段为数字） 这里即 select * from t_user where id = CAST("1" AS signed int); 索引字段没有使用函数计算，则不会失效

MySQL 分页的性能问题：

  • 如果偏移量不大，则直接 limit，size 分页即可
  • 若偏移量非常大，则：
    1. 按照循环的思想，每次都一个一个的挪动(即开放的是上一页/下一页)
    2. 像搜素引擎一样，只展示前 X 页(20/50？)

执行计划： EXPLAIN！#

MySQL执行计划分析 | JavaGuide ↗

mysql> explain SELECT * FROM dept_emp WHERE emp_no IN (SELECT emp_no FROM dept_emp GROUP BY emp_no HAVING COUNT(emp_no)>1);
+----+-------------+----------+------------+-------+-----------------+---------+---------+------+--------+----------+-------------+
| id | select_type | table    | partitions | type  | possible_keys   | key     | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+----------+------------+-------+-----------------+---------+---------+------+--------+----------+-------------+
|  1 | PRIMARY     | dept_emp | NULL       | ALL   | NULL            | NULL    | NULL    | NULL | 331143 |   100.00 | Using where |
|  2 | SUBQUERY    | dept_emp | NULL       | index | PRIMARY,dept_no | PRIMARY | 16      | NULL | 331143 |   100.00 | Using index |
+----+-------------+----------+------------+-------+-----------------+---------+---------+------+--------+----------+-------------+
sql

对于执行计划，参数有：

  • possible_keys 字段表示可能用到的索引；
  • key 字段表示实际用的索引，如果这一项为 NULL，说明没有使用索引；
  • key_len 表示索引的长度；
  • rows 表示扫描的数据行数。
  • type 表示数据扫描类型，我们需要重点看这个。

type 字段就是描述了找到所需数据时使用的扫描方式是什么，常见扫描类型的执行效率从低到高的顺序为： (前两个尽可能避免)

  • All（全表扫描）；
  • index（全索引扫描）；不用对数据进行排序，但是开销依然很大
  • range（索引范围扫描）；
  • ref（非唯一索引扫描）；
  • eq_ref（唯一索引扫描）；(通常用于多表联查中)
  • const（结果只有一条的主键或唯一索引扫描）：(通常是与一个常量进行比较，查询效率更高)

Q:ALL 和 INDEX 到底有什么区别？

Extra： 这列包含了 MySQL 解析查询的额外信息，通过这些信息，可以更准确的理解 MySQL 到底是如何执行查询的。常见的值如下：

  • Using filesort：在排序时使用了外部的索引排序，没有用到表内索引进行排序。
  • Using temporary：MySQL 需要创建临时表来存储查询的结果，常见于 ORDER BY 和 GROUP BY。
  • Using index：表明查询使用了覆盖索引，不用回表，查询效率非常高。
  • Using index condition：表示查询优化器选择使用了索引条件下推这个特性。
  • Using where：表明查询使用了 WHERE 子句进行条件过滤。一般在没有使用到索引的时候会出现。
  • Using join buffer (Block Nested Loop)：连表查询的方式，表示当被驱动表的没有使用索引的时候，MySQL 会先将驱动表读出来放到 join buffer 中，再遍历被驱动表与驱动表进行查询。

注意：当 Extra 列包含 Using filesort 或 Using temporary 时，MySQL 的性能可能会存在问题，需要尽可能避免。

MySQL 为什么快：从页结构、索引到 B+ 树
https://astro-pure.js.org/blog/interview-mysql-1
Author 五香牛肉面
Published at 2026年3月6日
Copyright CC BY-NC-SA 4.0
Buy me a cup of coffee ☕.

并发不是开线程：从 JMM 到线程池与 CompletableFuture

MySQL 如何守住一致性：事务、锁、MVCC 与日志
Comment seems to stuck. Try to refresh?✨