什么是索引

索引是数据库表中一列或多列值的有序数据结构，用于快速定位和访问表中的数据行，从而显著提高查询效率。

为什么需要索引

索引存在的根本目的，就是解决数据量大时查询效率慢的问题。

假如有一个user表，表中存在1000万条数据，执行下面的SQL语句：

SELECT * FROM users WHERE email = 'user@example.com';

• 在email列没有索引的情况下：它会走全表扫描的方式来找到user@example.com对应的记录，这样通常会需要更多的耗时，甚至会几秒或者几十秒才能返回结果
• 在email列有索引的情况下：它会直接走索引来进行扫描，然后通过回表的方式来进行查询，此时查询的速度就会非常快，可以达到毫秒级；

索引常用的数据结构

索引是存储引擎用于快速查找数据的一种数据结构，常见的数据结构有很多，但不是很多的数据结构都是可以作为索引的。

索引的特点

一个理想的索引数据结构，必须同时满足：高效查找、支持范围查询、适应磁盘I/O、支持动态更新、支持组合索引、支持索引覆盖、支持高并发。

常用的数据结构

数据结构	查找效率	范围查询	动态更新	组合索引	覆盖索引	适用场景
B+树	O(logN)	✅ 支持	✅ 自平衡	✅ 支持	✅ 支持	数据库主流索引
Hash表	O(1)	❌ 不支持	✅ 支持	❌ 不支持	❌ 不支持	等值查询
B树	O(logN)	✅ 支持	✅ 支持	✅ 支持	❌ 不支持	文件系统、旧版本数据库
跳表	O(logN)	✅ 支持	✅ 支持	✅ 支持	✅ 支持	Redis、LevelDB
有序数组	O(logN)	✅ 支持	❌ 不支持	✅ 支持	❌ 不支持	静态数据

树形数据结构

通常来讲，都会采用树形数据结构来作为索引。相比于其它的数据结构（如数组、链表、哈希表等）在查询效率、动态更新、范围支持、磁盘友好性等方面具有综合优势。

下面的数据结构可以在数据结构可视化网站中进行演示，辅助理解。

二叉树查找树

虽然二叉树查找树是非常经典的有序树形数据结构，但是二叉树并不适合作为一个索引。仅管二叉树查找树的查询效率很高 —— $O(logN)$ ，但是它的查询次数受到了树的高度的影响，甚至在极端的场景下二叉树查找树会退化成链表，此时查询效率就变成了$O(N)$。

image.png

还有一个很关键的点在于树的高度，对于数据库系统而言，它必须要考虑数据的量级。对于一张表而言，它需要支持千万级别的数据量，对于二叉树查找树而言，此时就会导致树的高度，即使不考虑最极端的情况，树的高度也会超过20，那么对于查询效率而言，对于叶子节点的查询最少需要20次查询才可以。

所以二叉查找树就具备两个问题：数据量大的时候树的高度会很大，在极端情况下查询的效率会变得很低，也是这两个特点导致它与索引数据结构的要求大相径庭。

自平衡二叉查找树（AVL）

AVL是一种自平衡的二叉查找树，它是在二叉查找树的基础上增加了自平衡机制，可以有效的避免二叉查找树出现极端情况（退化为链表）。

image.png

仅管自平衡二叉查找树的查询效率很高，也不会出现极端情况，但是它仍然无法解决层高的问题。

树形数据结构的层级越高，就意味着查找一个节点需要遍历的数据量就越多，也就是要从磁盘中读取数据的次数就越多。磁盘I/O是一个比较耗时的操作，所以在数据库领域上需要显著降低树形数据结构的高度，才能有效降低磁盘I/O的次数。

其实使用红黑树也是一样的问题，在大数据量级的情况下会导致查找树的高度很高的问题

B树

B树（也叫B-Tree）是一种自平衡多路查找树，它能有效的降低树的高度。对于AVL而言，它一个节点里面只有一个数据，所以导致它的高度就会很高，那么B-Tree降低树高度的思路就是我一个节点存储多个键，那么树的高度是不是就降下来了。

B-Tree的节点需要满足下面的规则：

• 每个节点最多有 m 个子节点，称为 m 阶B-Tree；
• 每个节点最多存储 m-1 个键，m-1 称为B-Tree的度；
• 每个非根节点最少存储 $\frac{m}{2} -1$个键；
• 根节点至少可以存储1个键；
• 所有叶子节点在同一层；

B-Tree增加节点的的步骤：

1. 定位插入位置：从根节点开始，根据键值范围，找到应插入的叶子节点；
2. 插入键值：将新键插入该节点
3. 检查是否溢出（超过非叶子结点存储的最大键值数量）

• 如果节点键数 ≤ 最大键值数 ，插入完成
• 如果节点键数 > 最大键值数，触发分裂

1. 触发节点的分裂
2. 将满节点从中间一分为二，生成两个新节点；
3. 中间键上浮到父节点，父节点增加一个键和一个子节点指针；
4. 如果父节点也满，就会递归触发分裂，直到根节点（根节点满则树高+1）；

如下图所示为一个3阶B-Tree，特点是每个节点最多2个键，叶子节点至少要有1个键；

image.png

往左侧的B-Tree中插入数据7，根据定位它的插入位置为 [5,6] 这个节点，而3阶B-Tee的每个节点最多存储2个键，所以 [5,6] 这个节点需要进行分裂。分裂后 6 称为新的父节点，7 插入到 6 的右子树中；

B-Tree删除节点的的步骤：

1. 从根节点开始，像搜索树一样向下遍历树，找到包含键值K的节点N；
2. 如果N是叶子节点，从叶子节点移除K；
3. 移除后叶子节点键数满足要求：删除节点结束
4. 移除后叶子节点键数不满足要求：需要进行借一个键或者进行合并
5. 如果N是非叶子节点：
6. 使用K的前驱键（左子树中最大的键）或后驱键（右子树中最小的键）代替；
7. 删除前驱键或者后驱键；（此时问题转换为删除叶子节点中的键）
8. 借一个键或合并
9. 当移除叶子节点的键后，它的左兄弟节点或右兄弟节点都没有富余的键，则与兄弟节点 + 父节点 进行合并，此时父节点内少一个键，少一个引用；
10. 当移除叶子节点的键后，它的左兄弟节点或右兄弟节点有富余的键，就进行左旋或者右旋。右旋就是指：左子树的最大的键上浮，父节点的键下沉；左旋就是指：右子树最小的键上浮，父节点下沉；

删除叶子节点，删除后节点中的键符合最少键数

如下为一颗 5 阶的B-Tree，最少键数量为2，最多键数量为4；

image.png

删除叶子节点中的键 8 得到的结果就是：

image.png

删除叶子节点，删除后节点的键不符合最少键数

删除叶子节点的 125，删除后该节点不满足最少键数的要求，就需要通过借或者合并节点的方式来保证B-Tree的平衡性。

此时它的右兄弟节点 [225,250] 没有富余的键，但是它的左兄弟节点 [0,16,32] 有富余的键，因此可以从它的左兄弟节点借一个键，然后进行右旋操作。

所以它的左兄弟节点中最大的键上浮，父节点下沉，此时：

• 父节点 [63,220] 变成 [32,220]
• 当前节点 [125,188] 变成 [63,188]
• 左兄弟节点 [0,16,32] 变成 [0,16]

image.png

删除叶子节点中的键，兄弟节点没有富余的键

删除叶子节点 188后，该节点中仅剩下键63，此时不符合最少键数。因此需要向左子节点和右子节点借一个键。

左子节点 [0,16] 与 右子节点 [225,250] 都是没有富余的节点的，所以此时可以选择跟左子节点合并，也可以选择与右子节点合并（下图为跟左子节点合并的结果）。

合并节点后，会将 [0,16] 与 [188] 和 父节点 [32] 进行合并，此时：

• 兄弟节点 [0,16] + 当前节点 [188] + 父节点 [32] 进行合并：[0,16,32,63]
• 原本的父节点：[32,220] 变成了 [220]

完成节点合并后，父节点变成了 [220] 它不满足最少键数，所以当前节点变成父节点，继续进行借或者合并的逻辑。

此时当前节点 [220] 只有右兄弟节点 [1250,3000] ，其没有富余的键，因此会采取合并的策略。

合并时当前节点 [220] 与 右兄弟节点 [1250,3000] 和 父节点 [500] 进行合并形成新的根节点：[220,500,1250,3000]

image.png

删除非叶子节点

删除键500，会选择它的前驱键250，或者后继键700来替换自己，然后再删除掉对应的前驱键或者后驱键（下图演示的是用前驱键来代替自己）。

首先选择前驱键250来替换自己，然后删除掉它的前驱键，此时：

• 当前节点：[63,500,1250,3000] 变成了 [63,250,1250,3000]
• 叶子节点：[225,250] 变成了 [225]

此时叶子节点不符合最少键数，但是它的左兄弟节点和右兄弟节点都有富余的键，下图演示为从左兄弟节点借一个键，即发生右旋的场景；

• 当前节点：[225]，左兄弟节点：[0,16,32,63]
• 右旋，左兄弟节点中最大的键 63 上浮，父节点 220 下沉
• 当前节点：[225] 变成 [220,225]
• 左兄弟节点：[0,16,32,63] 变成 [0,16,32]

image.png

B+树

B+树也是一种平衡多路查找树，它是在B-Tree上的一个变种。

B+Tree的核心特性：

• 所有的非叶子节点只有索引值和子节点指针，不存储实际的数据；
• 叶子节点存储完整数据揭露（或指向数据的指针），并按键值有序排列；
• 叶子节点之间通过双向链表连接
• 所有叶子节点都在同一层

如下图所示为一颗5阶的B+Tree：

image.png

可以看到B+Tree的叶子节点中包含了所有的键值，非叶子节点仅仅存储的使叶子节点的索引值。

B+Tree添加元素步骤：

1. 找到键K需要添加的节点N
2. 添加完成后节点N中的键，满足最多键数的要求，则添加完成
3. 添加完成后节点N中的键，不满足最多键数的要求，就需要进行分裂
4. 选择节点键值的中位数，将其上浮到父节点
5. 当前节点分裂为两个节点
6. 节点N中间的键，上浮到父节点后，需要递归判断是否满足最大键值；

如上图的B+Tree所示，添加新的键32得到的结果：

键32会存储在节点 [0,16,225,250] 这个节点中，添加到该节点后 [0,16,32,225,250]。新节点不满足最大键值（5阶B+Tree，最多存储4个键），所以需要进行分裂。选择新节点的中间键 32 上浮到父节点，并将当前节点进行分裂；

• 父节点 [500,1000] 变成 [32,500,1000]
• 原节点 [0,16,32,225,250] 分裂成 [0,16] 和 [225,250] 两个节点分别作为键32的左子树或右子树；

image.png

B+Tree删除元素的步骤：

与B-Tree的相比B+Tree的删除元素的步骤会更加的复杂，因为它不仅需要删除叶子节点中对应的键，还要处理非叶子节点中的键。

1. 首先从根节点往下遍历，找到要删除的键K，以及它所在的叶子节点L和非叶子节点N；
2. 对于叶子节点L而言，删除掉它其中的键K
3. 删除键K后叶子节点L仍然满足最小键数，删除结束；
4. 删除键K后叶子节点L不满足最小键数，就需要进行借或合并；
5. 对于非叶子节点N而言，用叶子节点L中最小的键值来替换键K；（因为对于非叶子节点而言，它不会的删除键，所以它的键数肯定会满足最小键数的要求，因此需要关注的就是因为合并）
6. 对于借或合并，它与B-Tree的思路都是一样的，根据左兄弟节点和右兄弟节点键的数量来进行左旋或者右旋。

相比于B-Tree而言，因为它的叶子节点存储了完整的数据，并且是双向链表的数据结构，所以它对于范围查询的支持度更高，效率也更好。所以在MySQL中索引的数据结构选择的是B+Tree这种数据结构。

MySQL中的索引数据结构

在上面我们对常见的可以作为索引的数据结构进行了认识，其实对于关系型数据而言，大多数的索引采取的都是多路查找树，然后会根据它的使用场景来选择B-Tree或者是B+Tree。

虽然在有些场景下会采取Hash表来作为索引，Hash表作为索引的时候，它的查询效率虽然是$O(1)$，但是它不支持范围查询，只支持=和in的查询，所以相对来讲它的应用场景局限性也比较大。

在MySQL中索引采用的数据结构是B+Tree，对于B+Tree而言，它有以下几个显著的优点：

1. 对于B-Tree而言，节点需要存储数据和键，而B+Tree只有叶子节点存储数据，所以对于非叶子节点而言，B+Tree单个节点可以存储更多的键，这可以有效的降低索引树的高度，这是索引数据结构非常重要的一点，因为它意味着可以减少磁盘I/O的次数；
2. 对于B+Tree而言，它的叶子节点存储了全部的数据，还是双向链表的数据结构，所以它对于范围查询具有更高的效率。

在MySQL中，B+Tree的节点大小通常与磁盘块（Page）对齐（如16KB），每次I/O读取一个完整节点，最大化利用磁盘预读能力。

与B-Tree相比，B+Tree的问题也有一些，但是对于它的优点而言，它的缺点带来的问题是可以接受的。例如：

1. B+Tree的删除操作相对于B-Tree而言具有更多的复杂度，因为不仅需要删除叶子节点中的键，还需要删除非叶子节点中的键；
2. B+Tree的非叶子不存储数据，所以对于空间利用率而言，相对于B-Tree，它是更低的；
3. 在精确查询的场景下，B+Tree对于B-Tree而言不会有更好的效率，因为B+Tree必须要遍历到叶子节点，而B-Tree它不需要遍历到叶子节点就可能找到了目标键。但是B+Tree对于B-Tree而言，它的索引树的高度会可能会更低，所以综合各种因素之后，B+Tree与B-Tree并没有太大的差异；

MysQL中B+Tree的索引数据结构：

image.png

可以看到上面的索引的结构就是典型的B+Tree的结果，其中每一个节点都是一个数据页（默认是16KB）。

MySQL的单表建议的存储数据量

假设我们数据的主键是BigInt类型的，它的大小是8个字节，非叶子节点中指针的大小为4个字节。所以对于一个非叶子节点而言，它可以存储的键数为：

$\frac{16 \times 1024 - 1000 }{8 + 4} \approx 1282$

但是数据页中并不是完全都是存储键值对的（还会有1KB的元数据），所以理论上一个节点可以存储1282个键，但是由于避免节点的频繁分裂，MySQL并不会将每个节点都填充满，大概率会在90% ~ 95% 之间。根据经验而言，对于BigInt类型的主键，一个节点大概会在1173个键。

在数据行大小为1KB的条件下，一个三层索引树，它大概可以存储 $1173\times 1173 \times 16 = 22014864$ 行数据，而查询一个数据最多只需要读取三个数据页，也就是只需要三次磁盘I/O操作，这个效率是非常高的。

所以这也是为什么建议一张表中的数据尽量不要超过2千万行（根据单行数据大小进行调整），因为它会导致索引树的层高增加，磁盘I/O次数增加，查询效率会显著下降。

MySQL中索引的类型

非聚集索引和聚集索引

在MySQL中根据B+Tree叶子节点存储的数据的不同，将索引分为聚集索引和非聚集索引。

• 聚集索引：叶子节点存储的一行完整的记录；
• 非聚集索引：叶子节点存储的是行记录的主键；

在查询的时候，如果使用的是非聚集索引（无法实现索引覆盖时），就会先根据非聚集索引查询到主键索引，然后再利用主键索引查找到对应的数据，这个就是常说的“回表”。

在Innodb存储引擎中，它的主键索引就是聚集索引，而非主键索引（也称为二级索引）都是非聚集索引。

在MyISAM中，它不支持非聚集索引，所以它的主键索引和二级索引都是聚集索引。

聚集索引

image.png

可以看到在聚集索引中，叶子节点存储的是整行的数据。

非聚集索引

假如我们以age建立索引的时候，它存储的就是主键id。

image.png

所以当我们在使用age索引来查询的时候， 它会根据age的值找到该行记录的主键id，然后再进入聚集索引中根据主键id找到对应的记录。

这里不考虑索引覆盖的场景，后续会针对索引覆盖的场景进行单独的讲述

主键索引

在MySQL中，所有的表都必须有一个主键，如果用户在创建表的时候没有通过primary key显式指定一个主键，它会根据列的顺序选择第一个非空唯一索引作为这个表的主键。

如果这个表没有非空的唯一索引，他就会默认添加一个隐藏字段row_id（6个字节）作为这个表的隐藏式主键。

唯一索引

唯一索引是二级索引，它的特点是针对这个索引的中的记录是没有重复的，也就是每行记录都是不同的，所以唯一索引有很高的区分度。

唯一索引是允许列的值为NULL的，在MySQL中他默认NULL和所有的值都是不想等的，而且NULL和NULL也是不想等的。

普通索引

普通索引和唯一索引的区别在于该列的值是否允许重复，除此之外没有都是一样的。

因为唯一索引的特性，决定了它就是会具有很高的区分度，但是普通索引曲却不行。所以，在建立普通索引的时候要合理的分析数据分布情况，结合会用到的查询场景，尽可能选择区分度较高的列作为索引，这样可以显著发挥出索引的效果。

联合索引

联合索引就是允许多个字段共同组成有一个索引，例如：[name，phone，age]，三个字段就可以组成一个联合索引。

联合索引需要符合最左前缀原则，这个根据联合索引的结构就可以知道。

唯一索引和普通索引的索引树结构，其实都是一样的，但是联合索引这里会有一点不同。

如下图所示，以 [age,phone] 来建立联合索引，让会先按照age字段来进行排序，当age字段的值相等的时候，会按照phone字段来进行排序。

image.png

最左前缀原则

最左前缀原则时联合索引能够被正确使用的基本指导原则，当查询条件匹配了联合索引的左边连续一列或多列时，这个索引才能被有效的利用的。

select * from person where phone = 4122534;

上面的SQL语句其实是没有办法利用到联合索引的，其实我们观察索引的结构也能看出来。我们如果要想使用phone = 4122534这个条件在索引中查找的时候，你会发现无从下手的，因为在每一个索引节点，我们不知道它的前驱节点中的phone是否小于它，它的后继节点中的phone是否大于它。那么，我们根本就没有办法从根节点通过遍历这个联合索引来查找到对应的主键ID。

select * from person where age = 22;
select * from person where age = 22 and phone = 4122534;

上面的SQL是可以走这个联合索引的，一样是看这个索引，age字段它是有顺序的，因此我们根据根节点可以找到这个联合索引对应的主键ID。

其实联合索引是非常理解的，大伙儿在高中肯定都用过《牛津英汉大词典》。以查找单词java为例：

1. 我告诉你第一个字母是j，第二个字母是a，你帮我找到java，是不是很快；
2. 我告诉你第二个字母是a，第三个字母是v，你怎么找，你只能从来开始搜索； 所以，在思考最左前缀原则的时候，脑海里面构思好这个场景，就很好理解了。

MySQL中order by 的原理

在MySQl中，通常使用ORDER BY子句来进行数据排序，基本语法如下：

 SELECT column11,column2 FROM table_name ORDER BY column1 [ASC|DESC],column[ASC|DESC];

MySQL中对于排序，在不同的场景下会出现两种排序的实现方式：

• 索引排序：直接利用索引顺序获取已排序的数据；
• 文件排序：当无法使用索引排序时，MySQL创建临时结果集进行排序；

索引排序

当查询语句中的ORDER BY子句所涉及的字段与某个索引的列顺序完全匹配，并且索引的排序方向（升序或降序）业余ORDER BY要求一致时，MySQL便可以利用该索引来完成排序操作。

因为索引本身就是按照特定的顺序规则进行排序的，所以借助索引能够避免对数据进行额外的读取与复杂排序运算，从而显著提升查询效率。

在MySQL执行计划的Extra列中，如果没有出现Using filesort，且ORDER BY字段在索引中按顺序出现，那么就是利用了索引排序，性能最优。

假设联合索引：[name,age]

-- order by age 与索引 (name,age)的第二列的顺序是一致，所以会利用索引排序
select name,age from users where name = '张三' order by age;
-- order by name,age 与索引 （name,age) 完全一致，可以直接利用索引排序
select name,age from users order by name,age;
-- 虽然order by age 与索引列完全一致，但方向不匹配，可能触发filesort，取决与MySQL的版本和优化器决策
select name,age from users where name = '张三' order by age desc;
-- order by 的列不在索引中，直接filesort
select name,age from users order by city;

文件排序

当查询条件无法利用索引进行排序时，MySQL就要使用文件排序。文件排序的意思就是MySQL需要将数据读取到内存中处理，如果内存空间不足以容纳所有待排序的数据，就可能会借助磁盘临时表来辅助完成排序任务。

单路排序算法

将查询所需的列一次性地读取到内存中的排序缓冲区。在缓冲区内，MySQL使用高效的排序算法对数据进行排序操作。

这种方式在内存资源较为充足且待排序的数据量相对不大的情况下，能够展现出较高的效率。因为它避免了多次数据读取的操作，减少了磁盘IO的操作以及数据在内存与磁盘之间传输的延迟；

双路排序算法

仅读取查询所需列的索引数据以及对应的主键到排序缓冲区进行排序。在完成初步排序后，再根据主键值回表读取剩余列的数据。

在内存有限的情况下，可以有效减少排序缓冲区中数据的占用量，因为只读取了索引列和主键值，而不是全部列数据，但是额外的代价就是需要回表。

归并排序算法

当需要排序的数据量级极为庞大，以至于无法再内存中一次性完成整个排序过程时，MySQL会启用归并排序算法。

归并排序算法会将大规模的数据划分为多个较少的子数据集，然后再内存中分别对这些子数据集进行排序。排序完成后，再逐步将这些有序子数据集合并成最终有序结果集。

在归并排序算法中，如果内存不足以容纳所有的子数据集，MySQL会借助磁盘临时表来存储中间结果，这就不可避免地会带来磁盘IO开销。不过，归并排序具有良好的稳定性和时间复杂特性，能够在处理大规模数据排序时保持相对较高的性能表现。

排序的优化思路

排序优化的目标就是让ORDER BY的字段顺序与某个索引的列顺序完全匹配或前缀匹配，且查询能够使用该索引，无需借助文件排序。

• 为ORDER BY字段建立合适的索引
• 利用联合索引的前缀匹配特性

-- 索引：(name, age, created_at)
SELECT * FROM users WHERE name = '张三' ORDER BY age, created_at;
-- 可用索引排序：因为 name 是等值条件，age 和 created_at 是索引后续列

• 避免在ORDER BY中使用函数、表达式或计算字段；
• 避免 select * ，只查询必要的字段，配合索引覆盖；
• 避免ORDER BY与GROUP BY混合导致双重排序，因为GROUP BY通常会隐式排序，如果再加ORDER BY会触发两次排序；

MySQL中join的原理

JOIN本质是通过关联条件，将两个或多个表的记录组合成新记录的过程。MySQL执行JOIN时，会将表分为驱动表（外表）和被驱动表（内表）。

• 驱动表：首先执行的表，用于生成基础数据集合，MySQL会优先选择数据量小、过滤条件充分的表作为驱动表（通过EXPLAIN的type列前的表即为驱动表）；
• 被驱动表：以驱动表的结果为依据，通过关联条件匹配的表，需要为关联字段建立索引以提升匹配效率；

核心原则：小表做驱动，大表建索引。驱动表数据量越小，基础集合越小，被驱动表的匹配次数就越少；被驱动表的关联字段有索引，可将“全表扫描”转为“索引查找”，效率提升10倍以上。

四种常见JOIN类型

|JOIN类型|核心逻辑|示例SQL| |-|-|-| |INNER JOIN|仅保留两表中满足关联条件的记录|select * from user u inner join order o on u.id = o.userid| |LEFT JOIN|保留左表所有记录，右表匹配不到则补NULL|select * from user u left join order o on u.id = o.userid| |RIGHT JOIN|保留右表所有记录，左表匹配不到则补NULL|select * from user u right join order o on u.id = o.user_id| |FULL JOIN|保留两表所有记录，一方无匹配则补NULL|MySQL无原生FULL JOIN，需要UNION实现：LEFT JOIN + RIGHT JOIN|

MySQL的四种JOIN算法

MySQL的JOIN执行依赖三种算法：嵌套循环（Nested Loop Join）、索引嵌套循环连接（Index Nested Loop Join）、块嵌套循环连接（Block Nested Loop Join）。

嵌套循环（Nested Loop Join）

嵌套循环是最基本的JOIN算法，它通过两层或多层嵌套的循环来完成表连接操作。基本步骤如下：

1. 外层循环遍历表A中的每一行记录；
2. 对于表A中的每一行记录，内层循环表遍历表B中的每一行记录，并检查这两行记录是否满足JOIN条件。如果满足条件将这两行记录组成结果集的一部分；

SELECT * 
FROM tableA 
JOIN tableB 
ON tableA.column = tableB.column;

在这个查询中，MySQL可能会采用嵌套循环算法。先从tableA取出一行，然后逐行扫描tableB，查找满足 tableA.column = tableB.column 条件的记录，将匹配的记录组合后输出。

使用嵌套循环算法时，事件复杂度为：$A * B$，其中A是表A的行数，B是表B的行数。

索引嵌套循环连接（Index Nested Loop Join）

索引嵌套循环连接是嵌套循环连接优化版本。当被驱动表（通常是内层循环的表）上有与JOIN条件相关的索引时，MySQL会使用该索引来加速查找匹配的记录，而不是全表扫描。基本步骤如下：

1. 外层循环遍历驱动表（通常是行数较少的表）中的每一行记录；
2. 对于驱动表中的每一行记录，利用被驱动表上的索引快速定位满足JOIN条件的记录，而不需要逐行扫描被驱动表；

SELECT * FROM users u JOIN orders o on u.id = o.user_id where u.name = '张三';

对于上面的SQL，它的执行步骤为：

1. 先从users表中查询出复合条件u.name = '张三'的数据；
2. 然后再从查询出来的结果集中每一行都去orders表的 user_id 索引中进行查找，找到符合连接条件的数据，这样就可以不对 orders 表进行全表扫描；

块嵌套循环连接（Block Nested Loop Join）

块嵌套循环连接是嵌套循环连接的一个变体，用于改进某些情况下的查询性能。与传统的嵌套循环相比，块嵌套循环连接通过减少内部表的重复扫描次数来提高效率。

块嵌套循环JOIN是MySQL无法使用索引进行连接时，采用的一种“内存优化版”的嵌套循环JOIN算法，它利用JOIN BUFFER来减少对被驱动表的重复扫描。

select * FROM users u join order o on u.id = o.user_id;

对于上述的SQL语句执行块嵌套循环连接的流程是：

1. 读取驱动表user的一部分数据（一个块），放join buffer（默认大小为128K，可调）；
2. 从被驱动表order中取一条数据，跟join buffer中的所有数据进行比较，匹配则输出；
3. 当前块匹配完毕后，从驱动表user中加载下一个块的到join buffer，继续与被驱动表进行匹配；

所以对于块嵌套循环连接而言，它扫描被驱动表的次数是被大大减少的，因为它是：$A \times Blocks$，其中A标识驱动表的行数，Blocks代表室加载到join buffer中块的次数。

块嵌套循环与嵌套循环的区别就是，通过引入join buffer来减少对被驱动表的全表扫描次数，而且他们都是适用于连接的字段上没有索引。如果连接的字段有索引的话，他就会走索引嵌套循环连接。

哈希连接（Hash Join）

Hash Join是MySQL 8.0版本引入的一种表连接算法，用于优化多表查询的性能。它主要分为两个核心节点：

1. 哈希表的构建

   选择较小的表作为构建表，将其连接通过哈希函数映射到内存的哈希表。哈希表键值对：键是连接列的哈希值，值是对应行数据或行标识（主键）；

2. 数据探测阶段

   较大的表作为探测表，逐行扫描其连接键，计算哈希值后到哈希表中查找匹配项。若哈希值匹配，进一步验证实际连接操作（避免哈希冲突导致的误匹配）。

在使用EXPLAIN查看执行计划时，如果在EXTRA列出现Using join buffer（hash join）提示，说明出现了哈希连接。哈希连接适用于等值比较，不支持范围查询（如>或<）。

当连接表数据量较大且无法通过索引优化时，哈希连接通常比嵌套循环连接（Nest Loop join）更高效，但是对于内存的要求也会更大，因为它创建的临时哈希表是存储在内存中的，如果哈希表的内存不够的时候，会采取分区表的方式来将一个大的哈希表拆分成多个小的哈希表。

MySQL数据库优化的措施

覆盖索引

一个索引包含了查询语句中所有需要返回的字段。当查询能够完全通过扫描索引来获取数据，而无需回表查询数据行时，我们就这个索引覆盖了查询。

覆盖索引的好处在于，减少了磁盘I/O的操作，因为它不用回表。避免回表，就意味着减少了对磁盘上数据文件的随机读取。所以文件通常比数据文件少得多，全部在索引中操作，I/O效率极高。

由于减少了磁盘访问次数，查询速度会有显著提升，尤其是当数据量很大时；InnoDB的二级索引叶子节点直接存储了主键值，如果查询字段包含在：索引列 + 主键 中，就很容易实现覆盖索引。

-- 不会走覆盖索引，因为要查询的列除了 id 和 name 以外，还有其它的列
select * from user where id = 1 and name = '张三';
-- 会走覆盖索引，因为查询的列 id 和 name 可以直接在 二级索引 name 中找到
select id,name from user where id = 1 and name = '张三';

在实际编写SQL语句的时候，不要习惯使用*来表示要查询的列，最好是指明要查询的列。这样便于，在对应的场景中，我们可以减少查询的列，没有必要每次都查询出所有的列，这样可以实现覆盖索引，提升查询的效率。

索引下推

索引下推是MySQL 5.6 引入的一项优化，它的全称是 Index Condition Pushdown。

将一部分原本在MySQL服务层进行的数据过滤操作，下推到存储引擎层的索引遍历过程中去执行。简单来说，就是在遍历索引时，顺便把能提前做的筛选都做了，减少不必要的回表次数。

在使用EXPLAIN命令查看执行计划时，如果Extra列包含了Using index Condition 就表示这个查询使用了索引下推优化。

假设我们现在有一张 user 表，并在（name，age）上建立了联合索引 idxnameage 。

SELECT * FROM users WHERE name LIKE '张%' AND age = 20;

在没有索引下推的情况下：

存储引擎会根据联合索引 idxnameage，找到所有满足 name like '张%'的索引条目。因为索引是先按name排序的，所以可以快速定位到所有姓张的人；

对于每一个找到的索引条目，即每一个姓张的人，存储引擎都立即回表，根据主键去读取整行数据。

存储引擎将读取到的完整行数据返回给MySQL服务层，服务层再检查这些行数据是否汉族第二个条件 age = 20 。如果满足，则保留；不满足，则丢弃。

问题在于存储引擎盲目的将所有姓张的人的数据行（1000个）都读取出来了，但其中可能只有10个人的年龄是20岁，这导致了990次不必要的回表操作，性能浪费严重。

在有索引下推的情况下：

存储引擎会根据联合索引 idxnameage 找到所有满足name like '张%'的索引条目，此时存储引擎不会立即回表，它会检查索引条目中是否包含age字段的值，因为age是联合索引的一部分。然后它直接在索引层面对age=20这个条件进行过滤。只有同时满足两个条件，存储引擎才会对其进行回表操作，读取完整的数据行。

将读取到的行返回给服务器层，服务器层不再需要过滤，因为存储引擎已经帮它完成了。

索引跳跃扫描

索引跳跃扫描是MySQL 8.0.13版本引入的一项重要查询优化技术，它允许优化器在复合索引中，即使WHERE条件没有使用最左前缀列，也能跳过某些值，高效地利用索引进行查询。

假如有一个联合索引：[name,age]，下面的查询：

select * from users where age > 20;

在没有索引跳跃扫描的场景下，它不会使用联合索引，如果age没有独立的索引的话，有可能会出现全表扫描的情况。

在有索引跳跃扫描的场景下，会枚举出users表中所有的name字段不重复的值（假设有：lisi 和 zhangsan），此时会构造一个虚拟条件：

select * from users where name = 'lisi' and age > 0;
select * from users where name = 'zhangsan' and age > 0;

需要注意的是索引跳跃扫描仅仅适用于name列的所有不重复值的数量比较少的情况，如果name列中不重复的值太多了（默认阈值是200），MySQL会认为走全表扫描更快的话，它也不会去走索引跳跃扫描了。

简单理解就是：索引跳跃扫描是在联合索引中最左列的枚举值较少的场景下，自动为查询带上最左列，让他复合最左前缀原则，也能用上联合索引；

MySQL的执行计划

在了解MySQL索引的优化措施之前，我们必须先能分析出SQL有什么问题，所以必须了解MySQL的执行计划。

使用Explain关键字模拟优化器执行SQL语句，分析你的查询语句或是结构的性能瓶颈。

image.png

利用MySQL的执行计划，就可以有效的分析这个SQL执行的效率，以及索引的使用情况。

对于执行计划，还有一个变种的使用方法：

explain format = json select * from actor where id = 1;

此时他会输出下面的内容，其中对于cost_info这个属性是一个很重要的参考价值，后续会对这个值的含义进行讲解。

{
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "1.00"
    },
    "table": {
      "table_name": "actor",
      "access_type": "const",
      "possible_keys": [
        "PRIMARY"
      ],
      "key": "PRIMARY",
      "used_key_parts": [
        "id"
      ],
      "key_length": "8",
      "ref": [
        "const"
      ],
      "rows_examined_per_scan": 1,
      "rows_produced_per_join": 1,
      "filtered": "100.00",
      "cost_info": {
        "read_cost": "0.00",
        "eval_cost": "0.10",
        "prefix_cost": "0.00",
        "data_read_per_join": "200"
      },
      "used_columns": [
        "id",
        "name",
        "update_time"
      ]
    }
  }
}

id

id表示select查询的序号，表示查询的执行顺序。

• id相同：执行顺序从上到下；
• id不同：如果是子查询，id序号会递增。id值越大，优先级越高，越先执行；
• id为NULL：通常表示一个联合结果（如UNION）；

select_type

查询的类型，主要用于区分普通查询、联合查询、子查询等。

• SIMPLE：简单的SELECT，不包含子查询或UNION；
• PRIMARY：查询中若包含任何复杂的子部分，最外层的SELECT被标记为PRIMARY；
• DERIVED：在FORM列表中包含的子查询被标记为DERIVED（衍生表），MySQL会递归执行这些子查询，把结果放在临时表中；
• UNION：UNION中的第二个或后面的SELECT语句；
• UNION RESULT：从UNION表获取结果的SELECT；

type（SQL性能的核心指标）

这是判断查询效率最重要的字段，从好到坏依次为：

• system：表只有一行记录（等于系统表），这是const类型的特例，几乎不会出现；

• const：通过索引一次就找到了，用于比较主键索引或唯一索引的所有列与常量值的比较。因为只匹配一行数据，所以非常快。

• eq_ref：在连接查询时，使用主键或唯一索引进行关联。对于前表的每一行，后表只有一行与之匹配。这是除了system和const之外最好的连接类型；

  常见于连接查询，其中 B.id 是主键或者是唯一键：

select * from A LEFT JOIN B ON A.id = B.id

• ref：使用非唯一索引进行扫描，返回匹配某个单独值的所有行

-- name 列有普通索引
select * from users where name = '张三';

• range：只检索给定范围的行，使用一个索引来选择行。一般出现在 BETWEEN、<、>、IN等操作中。
• index：全索引扫描。遍历整个索引树来获取数据。虽然比全表扫描好，但效率依然不高；
• all：全表扫描，性能最差，需要检查表中的每一行。在数据量大的情况下必须优化。

优化目标至少要让type达到range级别，最好能达到ref或const。

这里需要说一下 ref 与 index 的区别：ref 指的是从的索引的根节点来查询对应的记录，index指的是从索引的叶子节点来进行遍历找到对应的记录，所以ref的性能与index性能相比会有一定的差距。

possible_keys 和 key

possible_keys 是指查询可能使用的索引，如果为NULL，表示没有可能的索引；

key 查询时实际使用的索引。如果为NULL，则表示没有使用索引；

possible_keys 不是 NULL，但是 key 是NULL，说明MySQL认为全表扫描比使用索引更快（通常发生在小表或需要检索大部分数据时）。

key_Len

表示索引中使用的字节数，可以通过该列计算查询中使用的索引长度。它的作用是判断索引是否被充分使用了，特别是在联合索引中，key_len 越长，说明使用索引的部分越多。

对于一个联合索引（name，age），name是 varhcar(20)，age是INT

• 如果查询只用到了name，key_len可能是 $20 \times3+2=62$ 字节（utf8mb4字符集，一个字符最多3个字节，VARCHAR类型有2个字节表示长度）；
• 如果查询同时用到了name和age，key_len会是：$62 + 4 = 66$ 字节（INT占据4个字节）；

rows

MySQL认为它必须检查以执行查询行数的估计值。这是一个预估值，不一定完全准确，但是它是衡量性能的关键指标。

这个值越少越好，如果这个值非长达，说明你的查询可能需要优化（比如：添加索引）。

Extra

此列包含MySQL解决查询的额外信息。以下是一些常见且重要的值：

• Using index：表示出现了覆盖索引，查询的列都包含在索引中，无需回表查询数据行；
• Using where：表示存储引擎返回的行后，MySQL服务器层还需要进行条件过滤。如果type是ALL或INDEX，这通常表示效率不是很高；
• Using temporary：表示MySQL需要使用临时表来存储结果，常见于 ORDER BY 或 GROUP BY 操作，且无法利用索引完成排序；
• Using filesort：表示MySQL无法利用索引完成排序，需要额外的排序操作。如果数据量大，会在磁盘上完成，非常耗时；
• Using join buffer（Block Nested Loop）：表示在连接查询时，被驱动表没有使用索引，需要用到连接缓冲区；
• Impossible Where：Where子句的值总是false，无法选取任何行；
• Using index Condition：表示这个查询使用了索引下推来进行优化；

MySQL索引的选择规则

其实MySQL的索引选择规则没有一个具体的逻辑规则，甚至在不同的版本它的表现也是不同的。在MySQL中，它会根据实际的开销来选择是否要走索引。

像执行计划中 possible_keys 有值，但是 key 的值为NULL的时候，则表示MySQL在可以走索引的时候并没有选择走索引。

这种现象出现的原因是，在执行SQL语句的时候，MySQL服务层的执行优化器对SQL语句进行解析和优化后认为不走索引会更快。比如，现在有一张表，数据量很少，只有5条记录，我们根据name索引查找的时候，能查找到其中3条数据。因为name是二级索引，它是非聚集索引，当使用name来查询的话它需要回表三次，MySQL认为回表的开销会更大，比如全表扫描更快。

仅管我们可以通过force index关键字来强制执行MySQL使用哪个索引，但是一般不推荐这样子使用。我们要做的是，尽可能通过合理的索引设置，高效的SQL查询语句来尽可能引导MySQL走所以来执行。

在讲解 EXPLAINE FORAMT = JSON 来查看SQL的效率时，它的costinfo里面会展示这个SQL的查询耗时，它是一个相对值，没有单位，值越大表示消耗越大。MySQL会根据这个costinfo的值来选择它具体的执行路径。

SQL优化的一些原则

1. 最左前缀法则：如果索引了多列，要遵守最左前缀法则。指的是查询从索引最左列开始并且不跳过索引中的列；
2. 不在索引列上做任何操作（计算、函数、自动或手动类型转换），会导致索引失效而转向全表扫描；
3. 存储引擎不能使用索引范围条件右边的列（索引下推是MySQL 5.6版本才开始支持的）；
4. 尽量使用覆盖索引（只访问索引的查询），减少select * 语句；
5. MySQL在使用不等于、not in、not exists 的时候无法使用索引会导致全表扫描；MySQL内部优化器会根据检索比例，表大小等多个因素来整体评估是否使用索引；
6. is null，is not null 一般情况下也无法使用索引；
7. like以通配符开头，MySQL索引失效会变成全表扫描操作；
8. 使用覆盖索引，查询字段必须是建立覆盖索引的字段
9. 如果不能使用覆盖索引，则可能需要借助搜索引擎
10. 字符串不加单引号，触发了自动类型转换，导致索引失效；
11. 少用 or 或 in，用它查询时，MySQL不一定使用索引，MySQL内部优化器会根据检索比例，表大小等因素整体评估是否使用索引，详情范围查询优化；
12. 范围查询优化，可以将大范围查询拆分成多个小范围；