宝，让我们一起，有点东西

一、MYSQL索引的底层数据结构及算法

我们经常在涉及到SQL优化的时候，总是会想到加索引。那索引究竟是个什么玩意儿？

索引是帮助MYSQL高效获取数据，并且排好序的数据结构。

我们知道MYSQL可以采用的是B+树和hash来维护索引的，hash这个结构并不常用，它虽然能够通过hash算法很快的路由到对应的数据，但是对于排序，hash就显得很鸡肋了。

树形结构在一定程度上，都是采用的二分查找，所以查询的时间复杂度都很低。但随之而来又面临一系列的问题，比如树的退化，以及随着数据的不断增加，树的高度越来越高，磁盘IO的次数越来越多，导致性能越来越低，查询的时间越来越不可控

打个比方:

1. 二叉树：在极端的情况下，二叉树会退化成链表，查询的时间复杂度也随之退化。且树的高度越来越高

2. 红黑树：它又叫二叉平衡树，虽然自旋和变色解决了退化成链表的问题，但在一定程度上，树的高度递增的问题还是没有得到解决

3. B树：它相当于是二叉树的一个进化版本，变成了多叉树，那么单个结点存储的数据就变多了，随之树的高度也得到了控制，但是B树有一个特点，它的每个结点都存储了对应行的data，那么我们可以试想一下，这个索引的内存大小会特别大，而MYSQL的内存是有限的，我们单表在大多数情况下，都不止一两个索引， 那如果每个索引树都去维护一份data, 这对于MYSQL将会是一笔巨大的开销, 且造成了资源浪费。另一方面，如果我们要对索引字段排序，B树会采取一系列的递归遍历，性能大打折扣

4. B+树：它相当于是B树的一个进化版本, 从之前的每个结点都存储data，变为只有叶子结点存储data, 且这个树的所有数据其实都在叶子结点上，并且B+树在叶子结点维护了一个单向指针（MYSQL做了优化，变为了双向指针），这个指针在很大程度上解决了我们对索引字段排序的问题

到这里，想必应该更加理解了“索引就是一个排好序的数据结构”

PS：MYSQL索引树的单个结点默认可以存储16K大小的数据，即这16K就是一个磁盘块，意味着一个磁盘块能存储大量的索引字段，从而树的高度就得到了控制，而操作系统又有一个预读取的功能，所以每次读取索引树的时候其实就是读取一个磁盘块，把某个磁盘块的数据加载到内存中进行操作。

好了，索引的数据结构我们搞明白了，那接下来我们看一下MYSQL是怎么通过这个索引树去进行快速查询的。

这里涉及到MYSQL的存储引擎，像Innodb, MyISAM, Memorry。我们就聊聊常见的Innodb和MyISAM

PS：索引的数据结构维护在MYSQL安装目录下的/data文件夹里面

1. MyISAM：索引树和数据文件是分离的(非聚集)，索引树中的data维护的只是对应数据文件的内存地址，通过内存地址找到对应的数据。

2. Innodb：它分为两种情况，一种是主键索引树（或者是唯一索引树），另一种是普通索引树(非聚集)。主键索引树中的data维护的是对应行的数据，而普通索引树中维护的是对应行的主键id，通过这个主键id,去主键索引树中进行回表查询，从而找到对应的数据。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yJYnLVC2-1626606838207)(https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/12b12bd6e6014b74a73037c459c79eb9~tplv-k3u1fbpfcp-watermark.image)]

PS：大家猜想一下，MYSQL的联合索引是怎么去比较大小从而构成树的呢？打个比方，比如(name,age)这两个字段构成一个联合索引，那么会先根据name的ASCII码比较大小，如果通过name就已经确定出大小了，则不用继续去比较age的大小了。只有当name的ASCII码相等的时候，才用去比较age的大小。

二、SQL执行计划分析

执行计划分析在sql调优中占有举足轻重的地位，通过Explain + 我们自定义的SQL便可得出该SQL的执行计划，如下：

我们来分析一下执行计划中比较重要的几列

1. id列: 它是select的序列号，有几个select就有几个id，并且id的顺序是按select出现的顺序增长的。id列越大执行优先级越高，id相同则从上往下执行，id为NULL最后执行。

2. table列: 即对应select的那个表

3. type列: 这一列表示SQL的优化程度，依次从最优到最差分别为：system>const>eq_ref>ref>range>index>ALL一般来说，得保证查询达到range级别，最好达到ref

4. key列: 实际走的索引

5. rows列: mysql内部估算的结果数或扫描数

6. Extra列：这一列展示一些额外信息，重要的信息有以下几个：

   a. Usingindex：表示使用了覆盖索引（覆盖索引的意思就是只查询索引树上的字段，减少了回表操作，从而提升了速度）

   b. Usingwhere：使用where语句来处理结果，并且查询的列未被索引覆盖

   c. Usingindexcondition：查询的列不完全被索引覆盖，where条件中是一个前导列的范围

   d. Usingtemporary：mysql需要创建一张临时表来处理查询。出现这种情况一般是要进行优化的，首先是想到用索引来优化。

   e. Usingfilesort：使用普通字段排序而不是索引排序，数据较小时从内存排序，否则需要在磁盘完成排序。这种情况下一般也是要考虑使用索引来优化的。

三、一条SQL在MYSQL中是如何执行的？

要弄懂这个问题，首先我们要搞清楚MYSQL的内部结构，如下：

SQL执行过程如下：

1. MYSQL作为服务端，我们的程序作为客户端通过TCP与MYSQL保持一个长连接。

2. MYSQL把我们的SQL作为一个key去缓存中查询（MYSQL的缓存采用的是LRU淘汰算法来实现缓存的淘汰机制的），判断是否缓存命中，如命中，则直接返回数据。如未命中，则继续下面的流程

3. MYSQL实现了一套语法分析器（C语言写的），通过这个分析器来判断我们SQL语法的正确性。

4. 语法正确之后，再通过内部实现的优化器对我们的SQL进行一些优化，包括成本Cost计算等等（这就是为什么我们觉得某个SQL理论上会走索引，但是执行计划显示却没有走索引的原因），最终生成我们SQL的执行计划。当然，我们也可以通过FORCE_INDEX(…)强制走索引

5. 优化完成之后，会进入MYSQL内部的执行器，然后通过执行器调用我们这张表对应的存储引擎，比如Innodb, MyISAM, Memory等等。

6. 执行引擎会根据优化器分析出来的结果，也就是通过最优索引去对应的索引树上找到对应的数据，同时进行索引树的维护。

四、MYSQL的锁与事务的隔离级别

我们的数据库一般都会并发执行多个事务，多个事务可能会并发的对相同的一批数据进行增删改查操作，可能就会导致我们说的脏写、脏读、不可重复读、幻读这些问题。这些问题的本质都是数据库的多事务并发问题，为了解决多事务并发问题，数据库设计了事务隔离机制、锁机制、MVCC多版本并发控制隔离机制来解决多事务并发问题。

首先，我们来了解一下事务，以及事务的ACID特性

那么什么是事务？事务是一组SQL语句要么全部执行成功，要么全部执行失败。

事务的ACID特性：

• 原子性(Atomicity)：事务是一个原子操作单元,其对数据的修改,要么全都执行,要么全都不执行。
• 一致性(Consistent)：在事务开始和完成时,数据都必须保持一致状态。这意味着所有相关的数据规则都必须应用于事务的修改,以保持数据的完整性。
• 隔离性(Isolation)：数据库系统提供一定的隔离机制,保证事务在不受外部并发操作影响的“独立”环境执行。这意味着事务处理过程中的中间状态对外部是不可见的,反之亦然。
• 持久性(Durable)：事务完成之后,它对于数据的修改是永久性的,即使出现系统故障也能够保持。

并发事务带来的问题：

• 脏写： 当多个事务对同一条数据进行操作时，最后的更新覆盖了由其他事务的更新，那么其他事务的更新数据即丢失，这种问题称为脏写。
• 脏读：事务A读到了事务B已经修改但尚未提交的数据，事务A还在这个数据基础上做了操作。此时，如果事务B回滚，事务A读取的数据无效，不符合一致性要求。
• 不可重复读：事务A内部的相同查询语句在不同时刻读出的结果不一致，不符合隔离性。
• 幻读：事务A读取到了事务B提交的新增数据，不符合隔离性。

那么MYSQL是怎么解决这些问题的呢？就是通过事务的隔离级别，有以下几种：

• 读未提交：事务A能够读取到事务B没有提交的数据。

• 读已提交：事务A只能读取到事务B已提交的数据

• 可重复读：事务A在当前事务中，相同SQL读取到的数据都是一样的。

• 串行化：相当于加了事务级别的锁。事务A提交之后，其他事务才能往下执行。

下面有一张图记录了这四种隔离级别的问题：

常看当前数据库的事务隔离级别: show variables like '%isolation%';

设置事务隔离级别：set transaction_isolation='REPEATABLE-READ';

Mysql默认的事务隔离级别是可重复读，用Spring开发程序时，如果不设置隔离级别默认用Mysql设置的隔离级别，如果Spring设置了就用已经设置的隔离级别

在具体讲解这四种隔离级别之前，我们先了解一下MYSQL锁的知识，这是个大前提。

锁分类：

• 从性能上分为乐观锁(用版本对比来实现)和悲观锁
• 从对数据库操作的类型分，分为读锁和写锁(都属于悲观锁)
  • 读锁（共享锁，S锁(Shared)）：针对同一份数据，多个读操作可以同时进行而不会互相影响
  • 写锁（排它锁，X锁(eXclusive)）：当前写操作没有完成前，它会阻断其他写锁和读锁
• 从对数据操作的粒度分，分为表锁和行锁

行锁是我们开发过程中最常见的，那么我们以行锁为例， 行锁每次操作锁住一行数据，一个session开启事务更新不提交，另一个session更新同一条记录会阻塞，更新不同记录不会阻塞。开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度最高。

InnoDB与MYISAM的最大不同有两点：

• InnoDB支持事务
• InnoDB支持行级锁

对行锁有了一定了解之后，接下来我们来演示一下这四种隔离级别：

1. 读未提交

首先把隔离级别设为读未提交set transaction_isolation='read-uncommitted';，
接下来开启两个会话，如下图：

事务A读到了事务B没有提交的数据，脏写，脏读，不可重复读，幻读都可能发生。

2. 读已提交

首先把隔离级别设为读未提交set transaction_isolation='read-committed';，
接下来开启两个会话，如下图：

事务A只能读到事务B已提交的数据，不可重复读，幻读可能发生。

3. 可重复读

首先把隔离级别设为读未提交set transaction_isolation='read-committed';，
接下来开启两个会话，如下图：

按照上图序号标注的顺序，从1到6，在6查询的时候，发现确实是没有查到B事务新增的数据的，所以确实没有幻读。但是再执行7、8，会发现在8的时候，出现了幻读。

那既然MYSQL的默认隔离级别是可重复读，还会出现幻读，那么MYSQL是怎么解决幻读的呢？通过MVCC机制，下面会讲到。

4. 串行化
   首先把隔离级别设为读未提交set transaction_isolation='read-committed';，
   接下来开启两个会话，如下图：

当隔离级别是串行化的时候，事务A查询到的行会被加上行锁，事务B更新行锁上的数据会阻塞，直到事务A提交之后，事务B才能更新成功。

PS： Mysql默认级别是repeatable-read，有办法解决幻读问题吗？间隙锁在某些情况下可以解决幻读问题。

间隙锁，锁的就是两个值之间的空隙。

那么间隙就有id为(3,10)，(10,20)，(20,正无穷)这三个区间，在Session_1下面执行update account set name=‘zhuge’ where id>8 and id<18;，则其他Session没法在这个范围所包含的所有行记录(包括间隙行记录)以及行记录所在的间隙里插入或修改任何数据，即id在(3,20]区间都无法修改数据，注意最后那个20也是包含在内的。间隙锁是在可重复读隔离级别下才会生效。

五、深入理解MVCC

MVCC多版本并发控制机制，Mysql在读已提交和可重复读隔离级别下都实现了MVCC机制。

MVCC最大的优势：读不加锁，读写不冲突。在读多写少的应用中，读写不冲突是非常重要的，极大的增加了系统的并发性能

MVCC机制的实现就是通过ReadView与undo_log版本链，使得不同的事务会根据数据版本链对比规则读取同一条数据在版本链上的不同版本数据。

我们来了解一下undo_log版本链:

undo_log版本链是指某一行数据被多个事务依次修改过后，Mysql会保留修改前的数据undo回滚日志，并且用两个隐藏字段trx_id和roll_pointer把这些undo日志串联起来形成一个历史记录版本链,如下图：

可以理解为一个单链表，表尾的数据为最新的数据，而表头的数据为最古老的数据。

说了版本链我们再来看看ReadView。已提交读和可重复读的区别就在于它们生成ReadView的策略不同, 已提交读的事务中的每一次查询都会生成一个新的ReadView，而可重复读的事务中则不会。

那么究竟什么是ReadView呢？

通俗点说，就是在已提交读或者可重复读的隔离级别下，我们执行查询的时候，MYSQL内部会给我们维护一份活跃的事务列表，即begin了但还没有conmmit的事务id，比如ReadView为[30,60],那么说明30之前的事务都是已经提交的，60之后的事务是在当前ReadView生成之后才begin的。

举个例子 ，在已提交读隔离级别下：

比如此时有一个事务id为100的事务，修改了name,使得的name等于小明2，但是事务还没提交。则此时的版本链是：

那此时另一个事务发起了select 语句要查询id为1的记录，那此时生成的ReadView 列表只有[100]。那就去版本链去找了，首先肯定找最近的一条，发现trx_id是100,也就是name为小明2的那条记录，发现在列表内，所以不能访问。这时候就通过指针继续找下一条，name为小明1的记录，发现trx_id是60，小于列表中的最小id,所以可以访问，直接访问结果为小明1。

那这时候我们把事务id为100的事务提交了，并且新建了一个事务id为110也修改id为1的记录，并且不提交事务

这时候版本链就是

这时候之前那个select事务又执行了一次查询,要查询id为1的记录。

这个时候关键的地方来了

如果你是已提交读隔离级别，这时候你会重新一个ReadView，那你的活动事务列表中的值就变了，变成了[110]。

按照上的说法，你去版本链通过trx_id对比查找到合适的结果就是小明2。

如果你是可重复读隔离级别，这时候你的ReadView还是第一次select时候生成的ReadView,也就是列表的值还是[100]。所以select的结果是小明1。所以第二次select结果和第一次一样，所以叫可重复读！

也就是说已提交读隔离级别下的事务在每次查询的开始都会生成一个独立的ReadView,而可重复读隔离级别则在第一次读的时候生成一个ReadView，之后的读都复用之前的ReadView。

这就是Mysql的MVCC,通过版本链，实现多版本，可并发读-写，写-读。通过ReadView生成策略的不同实现不同的隔离级别。

六、Innobd的核心之BurfferPool缓存机制

为什么Mysql不直接更新磁盘上的数据而是设置这么一套BurfferPool机制来执行SQL呢？

• 因为来一个请求就直接对磁盘文件进行随机读写，然后更新磁盘文件里的数据性能可能相当差。
• 因为磁盘随机读写的性能是非常差的，所以直接更新磁盘文件是不能让数据库抗住很高并发的。Mysql这套机制看起来复杂，但它可以保证每个更新请求都是更新内存BufferPool，然后顺序写日志文件，同时还能保证各种异常情况下的数据一致性。更新内存的性能是极高的，然后顺序写磁盘上的日志文件的性能也是非常高的，要远高于随机读写磁盘文件。正是通过这套机制，才能让我们的MySQL数据库在较高配置的机器上每秒可以抗下几干的读写请求。

下面我们看一下BurfferPool缓存机制的流程图：

1. 比如我们的SQL是一个update语句，实际上，MYSQL在更新之前会先进行查询。经过MYSQL优化器优化之后得到最终的执行计划，然后执行器会先去磁盘中找到对应的数据，因为数据在磁盘上是以页的形式存储的，根据操作系统的预读取功能，会加载一整页的数据到BufferPool缓存池中。
2. 将更新之前的数据写入undo_log，方便回滚操作。
3. undo_log写入成功之后，然后在BufferPool缓存池中进行数据更新。
4. BufferPool数据更新成功之后，会将最新的数据写入Redo_log_buffer。
5. 在提交事务的时候，会将Redo_log_buffer中的数据写入Redo_log，主要作用是用于恢复BufferPool的数据
6. 在操作5进行的同时，会异步开一个线程去将bin_log日志写入bin_log文件
7. bin_log文件写入成功之后，最后会在redo_log文件中对应的数据打上一个commit的标记，为了保证事务提交后，redo_log和bin_log的数据一致性。