MySQL高阶知识点(二)：索引概述

1.深入浅出索引

索引是一种用于快速查询和检索数据的数据结构。常见的索引结构有: B 树， B+树和 Hash

通常来讲，索引就像一本中华字典的目录，通过目录可以快速定位查找某个汉字在哪一页，如果一页一页去查找某个汉字，效率之慢可想而知。我们可以通过创建索引提高查询速度，创建唯一索引保证字段唯一性，但是创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。索引需要使用物理文件存储，也会耗费一定空间。

项目推荐：基于SpringBoot2.x、SpringCloud和SpringCloudAlibaba企业级系统架构底层框架封装，解决业务开发时常见的非功能性需求，防止重复造轮子，方便业务快速开发和企业技术栈框架统一管理。引入组件化的思想实现高内聚低耦合并且高度可配置化，做到可插拔。严格控制包依赖和统一版本管理，做到最少化依赖。注重代码规范和注释，非常适合个人学习和企业使用

Github地址：https://github.com/plasticene/plasticene-boot-starter-parent

Gitee地址：https://gitee.com/plasticene3/plasticene-boot-starter-parent

微信公众号：Shepherd进阶笔记

1）索引常见的底层数据结构

常见的数据结构有：哈希表、有序数组和搜索树(B树、B+树)。

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。Java的hashMap就是典型的哈希表存储结构

hash = hashfunc(key)
index = hash % array_size

但是！哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。

Hash 索引不支持顺序和范围查询(Hash 索引不支持顺序和范围查询是它最大的缺点。但是我们在数据库中顺序查找、范围查找是一个常见的操作，这也是哈希表不适合做数据库索引的最主要原因。

有序数组在等值查询和范围查询场景中的性能都非常优秀。但是在有序数组中更新数据，比如插入一条数据，就比较麻烦了。

接下来登场的就是很重要的数据结构二叉搜索树，**二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。**但是我们知道在某些情况下，二叉搜索树会变成线性结构，导致查找变慢。

B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。

2）索引类型

每一个索引在 InnoDB 里面对应一棵 B+ 树。

根据叶子节点的内容，索引类型分为主键索引和非主键索引。主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）

基于主键索引和普通索引的查询有什么区别？

基于非主键索引的查询需要多扫描一棵索引树，因为非主键索引的叶子节点内容存的是主键的值，我们需要根据非主键索引找到对应的主键值，再根据主键去主键索引树查找一遍，这个过程叫做回表，因此，我们在应用中应该尽量使用主键查询。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

3）索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。如果插入的新值小于已存在的主键，这时候处理很简单，这时候只需要将这行数据放入当前索引最后一行数据所在数据页中，假如数据页已满，就新增一个数据页即可，但是插入新值得顺序在中间的话就比较麻烦了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

索引只能定位到page数据页，page内部有个有序数组，通过二分法快速查找定位到行

覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了， 而无需回表查询。

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。即最左前缀匹配原则。

最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引的时候，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用。

对于b树，b+树的详解请参考：b+树详解

2.唯一索引和普通索引怎么选？

唯一索引能保证字段的唯一性，在查找上，唯一索引在索引b+树找到满足条件的记录就不在查找了，因为是唯一的。普通索引需要查找下一个记录，直到碰到第一个不满足 条件的记录。

我们知道InnoDB 的数据是按数据页为单位来读写的。也就是说，当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。在 InnoDB 中，每个数据页的大小默认是 16KB。

那么，对于普通索引来说，要多做的那一次“查找和判断下一条记录”的操作，就只需要一次指针寻找和一次计算。当然，如果这个记录刚好是这个数据页的最后一个记录，那么要取下一个记录，必须读取下一个数据页，这个操作会稍微复杂一些。但是出现这个情况的概率不大，因为一个数据页会存储很多条数据，一般情况满足条件的上下数据都在一页中的。

所以普通索引和唯一索引在查询性能差不多。

在执行更新操作(插入或者更新)就两者差异就很大了，在讲述差异之前先介绍一下change buffer。

当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InnoDB 会将这些更新操作缓存在 change buffer 中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行 change buffer 中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。

需要说明的是，虽然名字叫作 change buffer，实际上它是可以持久化的数据。也就是说，change buffer 在内存中有拷贝，也会被写入到磁盘上。将 change buffer 中的操作应用到原数据页，得到最新结果的过程称为 merge。除了访问这个数据页会触发 merge 外，系统有后台线程会定期 merge。在数据库正常关闭（shutdown）的过程中，也会执行 merge 操作。显然，如果能够将更新操作先记录在 change buffer，减少读磁盘，语句的执行速度会得到明显的提升。而且，数据读入内存是需要占用 buffer pool 的，所以这种方式还能够避免占用内存，提高内存利用率。

什么条件下可以使用 change buffer 呢？

对于唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束。比如，要插入 一条记录，就要先判断现在表中是否已经存在唯一索引字段的记录，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用 change buffer 了。因此，唯一索引的更新就不能使用 change buffer，实际上也只有普通索引可以使用。change buffer 用的是 buffer pool 里的内存，因此不能无限增大。change buffer 的大小，可以通过参数 innodb_change_buffer_max_size 来动态设置。这个参数设置为 50 的时候，表示 change buffer 的大小最多只能占用 buffer pool 的 50%。

一个更新语句在inbodb的执行流程有两种情况：

1. 这个记录要更新的目标页在内存中。普通索引和唯一索引只需要找到更新的位置操作即可，只是唯一索引多一步判断是否冲突的步骤。
2. 这个记录要更新的目标页不在内存中。对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；对于普通索引来说，则是将更新记录在 change buffer，语句执行就结束了。将数据从磁盘读入内存涉及随机 IO 的访问，是数据库里面成本最高的操作之一。change buffer 因为减少了随机磁盘访问，所以对更新性能的提升是会很明显的。

**注意：**如果把某个普通索引改成了唯一索引，当后续有大量插入数据的操作时，就会很慢，最终导致更新语句堵住，整个系统处于阻塞状态。

change buffer 的使用场景：通过上面的分析，你已经清楚了使用 change buffer 对更新过程的加速作用，也清楚了 change buffer 只限于用在普通索引的场景下，而不适用于唯一索引。

那么，现在有一个问题就是：普通索引的所有场景，使用 change buffer 都可以起到加速作用吗？

因为 merge 的时候是真正进行数据更新的时刻，而 change buffer 的主要目的就是将记录的变更动作缓存下来，所以在一个数据页做 merge 之前，change buffer 记录的变更越多（也就是这个页面上要更新的次数越多），收益就越大。因此，对于写多读少的业务来说，页面在写完以后马上被访问到的概率比较小，此时 change buffer 的使用效果最好。这种业务模型常见的就是账单类、日志类的系统。反过来，假设一个业务的更新模式是写入之后马上会做查询，那么即使满足了条件，将更新先记录在 change buffer，但之后由于马上要访问这个数据页，会立即触发 merge 过程。这样随机访问 IO 的次数不会减少，反而增加了 change buffer 的维护代价。所以，对于这种业务模式来说，change buffer 反而起到了副作用。

通过上面我们知道change buffer的作用，这里个人觉得change buffer和之前讲的**redo log(重做日志)**会容易造成混淆，接下来我这边详解讲述一下两者的区别。

这里假如我们需要插入两条数据，一条插入落在数据页page1，一条插入落在数据页page2上，page1在内存中，page2不在内存中。插入流程如下：

Page 1 在内存中，直接更新内存；

Page 2 没有在内存中，就在内存的 change buffer 区域，记录下“我要往 Page 2 插入一行”这个信息

将上述两个动作记入 redo log 中。

读取流程如下：

读 Page 1 的时候，直接从内存返回。有几位同学在前面文章的评论中问到，WAL 之后如果读数据，是不是一定要读盘，是不是一定要从 redo log 里面把数据更新以后才可以返回？其实是不用的。虽然磁盘上还是之前的数据，但是这里直接从内存返回结果，结果是正确的。要读 Page 2 的时候，需要把 Page 2 从磁盘读入内存中，然后应用 change buffer 里面的操作日志，生成一个正确的版本并返回结果。可以看到，直到需要读 Page 2 的时候，这个数据页才会被读入内存。所以，如果要简单地对比这两个机制在提升更新性能上的收益的话，redo log 主要节省的是随机写磁盘的 IO 消耗（转成顺序写），而 change buffer 主要节省的则是随机读磁盘的 IO 消耗

如果某次写入使用了 change buffer 机制，之后主机异常重启，是否会丢失 change buffer 和数据？

这个问题的答案是不会丢失，留言区的很多同学都回答对了。虽然是只更新内存，但是在事务提交的时候，我们把 change buffer 的操作也记录到 redo log 里了，所以崩溃恢复的时候，change buffer 也能找回来。

3.优化器有时候为什么会选择错索引？

优化器选择索引的目的，是找到一个最优的执行方案，并用最小的代价去执行语句。在数据库里面，扫描行数是影响执行代价的因素之一。扫描的行数越少，意味着访问磁盘数据的次数越少，消耗的 CPU 资源越少。当然，扫描行数并不是唯一的判断标准，优化器还会结合是否使用临时表、是否排序等因素进行综合判断。

对于由于索引统计信息不准确导致的问题，你可以用 analyze table 来解决。而对于其他优化器误判的情况，你可以在应用端用 force index 来强行指定索引，也可以通过修改语句来引导优化器，还可以通过增加或者删除索引来绕过这个问题。

4.索引失效的情况

注意：优化器并不是要放弃使用这个索引。在某些情况下，放弃了树搜索功能，优化器可以选择遍历主键索引，也可以选择遍历当前索引 ，优化器对比索引大小后发现，当前索引更小，遍历这个索引比遍历主键索引来得更快。因此最终还是会选择当前索引，但是扫描的行数却是全部数据。

1. 对条件字段进行函数操作、计算操作。

   select * from `user` where MONTH(create_time)=2;
   
   select * from `user` where age+1=20;
   

2. 隐式类型转换：user表的user_no是varchar(32)

   select * from `user` where user_no=110717;
   -- 等价于下面
   
   mysql> select * from `user` where  CAST(user_no AS signed int) = 110717;
   

3. 隐式字符编码转换

   使用两张表关联查询时，因为这两个表的字符集不同，一个是 utf8，一个是 utf8mb4，所以做表连接查询的时候用不上关联字段的索引。因为在查询过程中会隐式的使用convert()函数进行转换。字符集不同只是触发条件，最终连接过程中要求在被驱动表的索引字段上加函数操作，是直接导致对被驱动表做全表扫描的原因。