Day 16

0. 索引

数据库中，索引的定义就是帮助存储引擎快速获取数据的一种数据结构，形象的说就是索引是数据的目录。

索引的分类

可以按照四个角度来分类索引。

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

1. MySQL的执行引擎有哪些？

存储引擎就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。

MySQL 存储引擎有 MyISAM、InnoDB、Memory，其中 InnoDB 是在 MySQL 5.5 之后成为默认的存储引擎。
下图是 MySQL 的结构图，索引和数据位于存储引擎中：

a) InnoDB: 默认的存储引擎，支持事务、行级锁定和外键。
b) MyISAM: 早期的默认引擎，不支持事务，但查询性能好。
c) Memory: 将数据存储在内存中，速度快但不持久。
d) Archive: 用于存储大量的历史数据，只支持插入和查询操作。
e) Blackhole: 不存储数据，主要用于复制或日志记录。

举例: 创建表时可以指定存储引擎

CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(50)
) ENGINE=InnoDB;

2. MySQL为什么使用B+树作索引？

怎样的索引的数据结构是好的？

MySQL 的数据是持久化的，意味着数据（索引 + 记录）是保存到磁盘上的，因为这样即使设备断电了，数据也不会丢失。

磁盘是一个慢的离谱的存储设备，有多离谱呢？

人家内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的，也就是说读取同样大小的数据，磁盘中读取的速度比从内存中读取的速度要慢上万倍，甚至几十万倍。

磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block）。Linux 中的块大小为 4KB，也就是一次磁盘 I/O 操作会直接读写 8 个扇区。

由于数据库的索引是保存到磁盘上的，因此当通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存，也就是说查询过程中会发生多次磁盘 I/O，而磁盘 I/O 次数越多，所消耗的时间也就越大。

所以，希望索引的数据结构能在尽可能少的磁盘的 I/O 操作中完成查询工作，因为磁盘 I/O 操作越少，所消耗的时间也就越小。

另外，MySQL 是支持范围查找的，所以索引的数据结构不仅要能高效地查询某一个记录，而且也要能高效地执行范围查找。

所以，要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：

能在尽可能少的磁盘的 I/O 操作中完成查询工作；
要能高效地查询某一个记录，也要能高效地执行范围查找；

什么是二分查找？

索引数据最好能按顺序排列，这样可以使用二分查找法高效定位数据。

假设现在用数组来存储索引，比如下面有一个排序的数组，如果要从中找出数字 3，最简单办法就是从头依次遍历查询，这种方法的时间复杂度是 O(n)，查询效率并不高。因为该数组是有序的，所以可以采用二分查找法，比如下面这张采用二分法的查询过程图：

可以看到，二分查找法每次都把查询的范围减半，这样时间复杂度就降到了 O(logn)，但是每次查找都需要不断计算中间位置。

什么是二分搜索树？

用数组来实现线性排序的数据虽然简单好用，但是插入新元素的时候性能太低。

因为插入一个元素，需要将这个元素之后的所有元素后移一位，如果这个操作发生在磁盘中呢？这必然是灾难性的。因为磁盘的速度比内存慢几十万倍，所以不能用一种线性结构将磁盘排序。

其次，有序的数组在使用二分查找的时候，每次查找都要不断计算中间的位置。

那能不能设计一个非线形且天然适合二分查找的数据结构呢？

有的，请看下图这个神奇的操作，找到所有二分查找中用到的所有中间节点，把他们用指针连起来，并将最中间的节点作为根节点。

怎么样？是不是变成了二叉树，不过它不是普通的二叉树，它是一个二叉搜索树。

二叉搜索树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点，这样在查询数据时，不需要计算中间节点的位置了，只需将查找的数据与节点的数据进行比较。

假设，查找索引值为 key 的节点：

如果 key 大于根节点，则在右子树中进行查找；
如果 key 小于根节点，则在左子树中进行查找；
如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。

二叉搜索树查找某个节点的动图演示如下，比如要查找节点 3：

另外，二叉搜索树解决了插入新节点的问题，因为二叉搜索树是一个跳跃结构，不必连续排列。这样在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。

下面是二叉搜索树插入某个节点的动图演示：

因此，二叉搜索树解决了连续结构插入新元素开销很大的问题，同时又保持着天然的二分结构。

那是不是二叉搜索树就可以作为索引的数据结构了呢？

不行不行，二叉搜索树存在一个极端情况，会导致它变成一个瘸子！

当每次插入的元素都是二叉搜索树中最大的元素，二叉搜索树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)，如下动图演示：

由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（假设一个节点的大小小于操作系统的最小读写单位块的大小），也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。

二叉搜索树由于存在退化成链表的可能性，会使得查询操作的时间复杂度从 O(logn) 升为 O(n)。

而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构。

什么是自平衡二叉树？

为了解决二叉搜索树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉搜索树（AVL 树）。

主要是在二叉搜索树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。

下图是每次插入的元素都是平衡二叉搜索树中最大的元素，可以看到，它会维持自平衡：

除了平衡二叉查找树，还有很多自平衡的二叉树，比如红黑树，它也是通过一些约束条件来达到自平衡，下面是红黑树插入节点的过程，这左旋右旋的操作，就是为了自平衡。

不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。

比如，下面这个平衡二叉查找树的高度为 5，那么在访问最底部的节点时，就需要磁盘 5 次 I/O 操作。

根本原因是因为它们都是二叉树，也就是每个节点只能保存 2 个子节点，如果把二叉树改成 M 叉树（M>2）呢？

比如，当 M=3 时，在同样的节点个数情况下，三叉树比二叉树的树高要矮。

因此，当树的节点越多的时候，并且树的分叉数 M 越大的时候，M 叉树的高度会远小于二叉树的高度。

什么是 B 树

自平衡二叉树虽然能保持查询操作的时间复杂度在 O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。

为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。

B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。

假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1 个）数据和最多有 3 个（M 个）子节点，超过这些要求的话，就会分裂节点，比如下面的的动图：

一棵 3 阶的 B 树的查询过程：

假设在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步：

与根节点的索引 (4，8）进行比较，9 大于 8，那么往右边的子节点走；
然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走；
走到索引为 9 的节点，然后找到了索引值 9 的节点。

可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3，所以在查询过程中会发生 3 次磁盘 I/O 操作。

而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。

但是 B 树的每个节点都包含数据（索引 + 记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到有用的索引数据。

而且，在查询位于底层的某个节点（比如 A 记录）过程中，非 A 记录节点里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，只是想读取这些节点的索引数据来做比较查询，而非 A 记录节点里的记录数据对是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。

什么是 B+ 树？

B+ 树就是对 B 树做了一个升级，MySQL 中索引的数据结构就是采用了 B+ 树，B+ 树结构如下图：

B+ 树与 B 树差异的点，主要是以下这几点：

叶子节点（最底部的节点）才会存放实际数据（索引 + 记录），非叶子节点只会存放索引；
所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
非叶子节点中有多少个子节点，就有多少个索引；

下面通过三个方面，比较下 B+ 和 B 树的性能区别。

1、单点查询

B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。

但是 B 树的查询波动会比较大，因为每个节点既存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。

B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比既存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更矮胖，查询底层节点的磁盘 I/O 次数会更少。

2、插入和删除效率

B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快

比如下面这个动图是删除 B+ 树 0004 节点的过程，因为非叶子节点有 0004 的冗余节点，所以在删除的时候，树形结构变化很小：

注意，：B+ 树对于非叶子节点的子节点和索引的个数，定义方式可能会有不同，有的是说非叶子节点的子节点的个数为 M 阶，而索引的个数为 M-1（这个是维基百科里的定义），因此我本文关于 B+ 树的动图都是基于这个。但是我在前面介绍 B+ 树与 B+ 树的差异时，说的是非叶子节点中有多少个子节点，就有多少个索引，主要是 MySQL 用到的 B+ 树就是这个特性。

下面这个动图是删除 B 树 0008 节点的过程，可能会导致树的复杂变化：

甚至，B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形，比如下面这个动图是删除 B+ 树根节点的过程：

B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，比如删除根节点中的数据，可能涉及复杂的树的变形，比如下面这个动图是删除 B 树根节点的过程：

B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。

因此，B+ 树的插入和删除效率更高。

3、范围查询

B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。

因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助，比如说想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月 12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。

而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的 MongoDB。

MySQL 中的 B+ 树

MySQL 的存储方式根据存储引擎的不同而不同，最常用的就是 Innodb 存储引擎，它就是采用了 B+ 树作为了索引的数据结构。

下图就是 Innodb 里的 B+ 树：

但是 Innodb 使用的 B+ 树有一些特别的点，比如：

B+ 树的叶子节点之间是用双向链表进行连接，这样的好处是既能向右遍历，也能向左遍历。
B+ 树点节点内容是数据页，数据页里存放了用户的记录以及各种信息，每个数据页默认大小是 16 KB。

Innodb 根据索引类型不同，分为聚簇和二级索引。他们区别在于，聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。

因为表的数据都是存放在聚簇索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚簇索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个，而二级索引可以创建多个。

总结

MySQL 是会将数据持久化在硬盘，而存储功能是由 MySQL 存储引擎实现的，所以讨论 MySQL 使用哪种数据结构作为索引，实际上是在讨论存储引擎使用哪种数据结构作为索引，InnoDB 是 MySQL 默认的存储引擎，它就是采用了 B+ 树作为索引的数据结构。

要设计一个 MySQL 的索引数据结构，不仅仅考虑数据结构增删改的时间复杂度，更重要的是要考虑磁盘 I/0 的操作次数。因为索引和记录都是存放在硬盘，硬盘是一个非常慢的存储设备，在查询数据的时候，最好能在尽可能少的磁盘 I/0 的操作次数内完成。

二分查找树虽然是一个天然的二分结构，能很好的利用二分查找快速定位数据，但是它存在一种极端的情况，每当插入的元素都是树内最大的元素，就会导致二分查找树退化成一个链表，此时查询复杂度就会从 O(logn) 降低为 O(n)。

为了解决二分查找树退化成链表的问题，就出现了自平衡二叉树，保证了查询操作的时间复杂度就会一直维持在 O(logn) 。但是它本质上还是一个二叉树，每个节点只能有 2 个子节点，随着元素的增多，树的高度会越来越高。

而树的高度决定于磁盘 I/O 操作的次数，因为树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作，也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。

B 树和 B+ 都是通过多叉树的方式，会将树的高度变矮，所以这两个数据结构非常适合检索存于磁盘中的数据。

但是 MySQL 默认的存储引擎 InnoDB 采用的是 B+ 作为索引的数据结构，原因有：

B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比既存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更矮胖，查询底层节点的磁盘 I/O 次数会更少。
B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；
B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

举例: 假设有一个包含100万条记录的用户表，使用B+树索引可以在2-4次磁盘I/O内找到目标数据。

3. 说一下索引失效的场景？

索引失效是指在查询过程中，原本应该使用的索引没有被使用，导致数据库系统退化为全表扫描，从而影响查询性能的现象。

当我们创建了索引，但在某些查询中无法利用这些索引时，就发生了索引失效。这意味着数据库系统不得不回退到全表扫描的方式来查找数据，这会显著降低查询性能，尤其是在大型数据表中。

索引可能在以下情况下失效:

当使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx%这两种方式都会造成索引失效；
当在查询条件中对索引列使用函数，就会导致索引失效。
当在查询条件中对索引列进行表达式计算，也是无法走索引的。
MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。

举例:

对索引使用左或左右模糊匹配

假设有一个 t_user 表，name 字段为二级索引。

// 会导致索引失效
select * from t_user where name like '%林';

// 可以使用索引
select * from t_user where name like '林%';

第一个查询会导致全表扫描（type=ALL），而第二个查询可以使用索引扫描（type=range）。

对索引使用函数

1 2	// name 为二级索引，会导致索引失效 select * from t_user where length(name) = 6;

这个查询会导致全表扫描。但是，从 MySQL 8.0 开始，可以创建函数索引来解决这个问题：

1	alter table t_user add key idx_name_length ((length(name)));

创建函数索引后，上述查询就可以使用索引了。

对索引进行表达式计算

// id 为主键索引，会导致索引失效
explain select * from t_user where id + 1 = 10;

// 改写后可以使用索引
explain select * from t_user where id = 10 - 1;

第一个查询会导致全表扫描（type=ALL），而第二个查询可以使用索引扫描（type=const）。

对索引隐式类型转换

假设 t_user 表中 phone 字段是 varchar 类型的二级索引：

// 会导致索引失效
select * from t_user where phone = 1300000001;

// 不会导致索引失效
select * from t_user where id = '1'; // 假设 id 是整型主键

第一个查询会导致全表扫描，因为 MySQL 会将 phone 字段隐式转换为整型。第二个查询不会导致索引失效，因为 MySQL 会将字符串 ‘1’ 转换为整型。

联合索引非最左匹配

假设有一个联合索引 (a, b, c)：

// 可以使用索引
select * from t_user where a = 1;
select * from t_user where a = 1 and b = 2;
select * from t_user where a = 1 and b = 2 and c = 3;

// 无法使用完整索引，可能部分失效
select * from t_user where b = 2;
select * from t_user where c = 3;
select * from t_user where b = 2 and c = 3;

WHERE 子句中的 OR

1 2	// 假设 id 是主键，age 不是索引 select * from t_user where id = 1 or age = 18;

这个查询会导致全表扫描。解决方法是为 age 字段也创建索引：

1	alter table t_user add index idx_age (age);

创建索引后，查询优化器会使用 index merge 策略，分别扫描 id 和 age 的索引，然后合并结果。

总的来说，为了避免索引失效，应该：

使用前缀匹配而不是后缀或全模糊匹配
避免在索引列上使用函数或进行计算
注意数据类型的一致性
遵守最左匹配原则
在 OR 条件的所有列上创建索引

同时，也可以利用 MySQL 8.0 的函数索引特性和 MySQL 5.6 之后的索引下推功能来优化某些特殊查询。理解这些概念和实践可以帮助更好地设计查询和索引，从而提高数据库性能。

Channing's Blog