前言
我们在上一篇博客聊了Mysql的整体架构分布，连接层、核心层、存储引擎层和文件系统层，其中存储引擎层作为Mysql Server中最重要的一部分，为我们sql交互提供了数据基础支持。存储引擎和文件系统执行IO交互，读取同一份原始数据(存储引擎不同，可能文件也不一样，但是都是一份数据)，然后依据各自的特性在内存中变换存放,满足自身设计。例如我们熟知的InnoDB和MyLSAM，都是将底层文件系统的物理数据读取到内存中以B+树的形式存在,只不过对于树上叶子节点中的数据会有不同的实现而已。下面我们来一一为大家解密。

1|0数据结构(b树和b+树)

千万不要问我有没有b-树，问这样问题的锤死！必须锤死！(b-树就是b树)
我们这节只讲数据库相关的一些特性，不会去深究数据结构的完整特性(太烧脑了),有需求的胖友可以自行搜索资料一起探讨。

1|1b树

图一：基于数字插入导致的B树变化

图二：3阶b树的最终效果

图三：5阶b树的最终效果

综上两图，我们可以看出b树的一些特点：

• 节点容量：每个节点，都可以容纳多个键值对(多路分支)。
• 排序方式：所有节点键值对是按key递增次序排列，并遵循左小右大原则；
• 层级结构：所有叶子节点均在同一层
• 子树指针：节点中每个键值对的两侧，都可以放置指针(不一定都有值，可以是null)，如果有值，则左边指向左子树(key都比当前key小)，右边指向右子树(key都比当前key大)。例如图2Q、T、X，叶子节点4(R、S)就是参考的父节点Q、T，这里的key也就是T

阶：在树中，一个节点可以拥有的最大子树数量称为阶(基于整棵树而言)

为了避免产生畸形树，即如下图：

我们对上述条件还得增加一些约束条件：

• 根节点至少有两颗子树
• 除根节点和叶子结点外，其他节点至少应该有m/2个子树。
• 每个节点的键值对数量k，应该m-1≥k≥ceil(m/2)-1。(ceil函数为向上取整函数，结果为趋向于正无穷的一个整数)

注意：每个节点中的键值对，value都是指向实际data的指针，如下图

b树相比二叉树(平衡二叉树)、红黑树等，实现了多分叉，这样整棵树的高度就降下来了，在数据库中，b树普遍运用在非关系型数据库索引设计上，比如Mongo DB索引，基于这种设计，树的每个层次都代表了一次和物理磁盘的IO(数据都是物理存储域磁盘上的),降低树的高度可以减少大量的磁盘IO。
对于b树节点的增删不是此次介绍重点，就不做过多描述，有兴趣的胖友可自行搜索资料一起交流。

1|2b+树

b+树为b树众多变种中最常见的一种，目前Mysql存储引擎的索引设计大多都是采用b+树设计，b树虽然解决了频繁磁盘IO的问题，但是仍然存在元素遍历效率低下的问题，b+树只有叶子节点存在关键信息，遍历只需要遍历叶子节点即可，且叶子节点保障了有序，所以b+树在减少IO的同时兼顾了元素遍历的性能问题。当然有利就有弊，缺点我们下面再说。

图一：3阶b+树

图片来源:https://blog.csdn.net/qq_27342265/article/details/113728778

相比于B树，B+树具有一下特点:

• 非叶子节点只进行数据索引，而不存放数据或者数据指针。(数据索引是为了找到真实的数据，在InnoDB中即寻找叶子结点上的聚簇索引，而在MyIsam中则为叶子节点的数据指针)
• 所有叶子节点均为从左往右、由小到大排列
• 叶子结点可对父节点进行溯源，它存放了父节点的关键指针信息
• 子节点必然包含父节点的最小或最大数据索引信息,根节点的最大值必然是整棵树的最大值。

b+树在Innodb、MyISAM存储引擎中的运用

InnoDB

在InnoDB中，我们存在两类索引：聚簇索引(聚集索引、一级索引、主键索引)和非聚簇索引(辅助索引、二级索引)，在InnoDB中每一种索引对应的都是一棵索引b+树

聚簇索引

聚簇索引表示为主键，InnoDB规定一张表中必须有且仅有一个主键,如果用户没有显式设置且没有UNIQE索引(此索引列均为NOT NULl)，则会自动生成一个6字节大小的长整型主键，数据则为主数据的一部分。
聚簇索引中不仅存放索引值，还包括事务id、回滚指针等等
InnoDB中聚簇索引和行数据绑定在一起(逻辑上一起)，这样做的好处就能快速通过聚簇索引检索整行数据出来。

辅助索引

辅助索引就包括：唯一索引、联合索引、普通索引等

介绍完两种索引后，我们就应该能想到两种场景：

表中只有主键索引时：非叶子节点存储的是聚簇索引的数据，叶子节点存储的则是整行记录数据，一次查询表中存在辅助索引时：非叶子节点存储的是辅助索引的数据,叶子节点存储的是聚簇索引的数据,然后再通过主键索引找到整行数据(回表)，二次查询

MyISAM

在MyISAM中，存在主/辅索引(相比InnoDB，可以不存在主键)。区别就是辅助索引的key值可以重复，主索引key不能重复。MyISAM的索引方式也叫“非聚集”，是为了与InnoDB的聚集索引区别。

表中存在索引时：非叶子结点存储的是索引相关数据，叶子节点存储的则是数据文件指针
表中不存在索引时：连树都没有，直接读取磁盘数据文件

2|0InnoDB内部架构

2|1架构图

(图片来源：http://www.linkedkeeper.com/1500.html)

从上图我们可以看出InnoDB包含两部分：

内存模块(左)：包含一系列的Buffer(缓冲), Buffer Pool、Log Buffer等
磁盘模块(右)：包含左边Buffer区映射到磁盘上的一些文件、数据文件、redo Log等等

1、Buffer Pool

众所周知，内存读写和磁盘读写效率一个天一个地。buffer Pool是通过缓存热点数据，实现加速读和加速写！

加速读:当需要访问一个数据页面的时候，如果这个页面已经在缓存池中，那么就不再需要访问磁盘，直接从缓冲池中就能获取这个页面的内容。
加速写:当需要修改一个页面的时候，先将这个页面在缓冲池中进行修改，记下相关的重做日志(redo log)，这个页面的修改就算已经完成。后续还会有时机将结果同步到磁盘物理文件上(刷盘)

同时，为了提高缓存的的命中效率，Buffer Pool还提供了LRU最近最少使用列表算法来提高缓存命中的效率，值得一提的是，它还将整个列表分为了young池子和old池子，如果有想详细了解的可以参考：https://zhuanlan.zhihu.com/p/65811829

ps:由于Buffer Pool为纯内存的，所以一旦宕机，还未来得及刷盘持久化的写入操作就有可能被丢失，由此，引入我们的redo log

2、Redo Log

讲Redo Log之前我们先来说一下事务的四大特性

• 原子性(Atomic)
• 一致性(Consistency)
• 隔离性(Isolation)
• 持久性(Duration) 事务的隔离性由锁机制和MVCC实现，原子性(Atomic)由Undo Log实现，持久性由Redo Log实现，一致性由Undo Log和Redo Log共同实现(即：数据库总是从一个一致状态转移到另一个一致状态)。

ps:mvcc和undo Log会在下面着重说，这里咱们先讲持久性实现的核心--Redo Log

问:redo Log怎么解决事务的持久性呢？

• 当数据修改时，首先写入Redo Log(记录的是数据修改之后的信息)，再更新到Buffer Pool，保证数据不会因为宕机而丢失，保证持久性。
• 当事务提交时会调用fsync将redo log刷至磁盘持久化。MySQL宕机时，通过读取Redo Log中的数据，对数据库进行恢复。

问:Redo Log也是记录在磁盘中，为什么会比直接将Buffer Pool写入磁盘更快？

• Buffer Pool刷盘是随机IO，每次修改的数据位置随机，而Redo Log永远在页中追加，属于顺序IO。
• Buffer Pool刷盘是以数据页为单位，每次都需要整页写入。而Redo Log只需要写入真正物理修改的部分，IO数据量大大减少。

2.1 重做日志的内存结构

redo log由两部分组成：

内存中的重做日志缓冲(redo log buffer)重做日志文件(redo log file)
注意：InnoDB通过Force Log at Commit机制保证持久性：当事务提交(COMMIT)时，必须先将该事务的所有日志缓冲写入到重做日志文件进行持久化，才能COMMIT成功。

为了确保每次日志都写入重做日志文件，在每次将重做日志缓冲写入重做日志文件后，InnoDB存储引擎都需要调用一次fsync操作。
这里有两个注意的点：

2.1.1、重做日志缓存写入物理文件的时机

• 事务提交的时候
• log checkpoint(刷盘检查点)时,比如说buffer空间使用一半以上的时候的，就是一个检查点，这时就会通知buffer需要写磁盘了

3. MVCC(多版本并发控制)

mysql事务隔离级别

在讲MVCC之前我们先讲讲事务的隔离级别：

前面有提到，MVCC解决了事务隔离性的问题。那是因为MVCC以写事务提交未时间节点，将行数据分离成了一个新版本和一个旧版本,当相关数据存在其他事务活跃状态的时候，读的时候就返回旧版本数据，否则就返回新版本数据，保证了在某个时间点开启的事务可以获取到一致的数据库状态,从而达到一个并发访问的事务隔离。

各种隔离级别下对于脏读、不可重复读、幻读的抵抗程度,参照下表(x：代表未解决，√：代表解决)：

与其他主流数据库不一样的是，Mysql默认RR级别的事务隔离级别，其他大多都是RC的事务隔离级别

Mysql锁

按照粒度分：页级锁、表级锁、行级锁
按照类型分：读锁(共享锁、S锁)、写锁(排它锁、X锁)、间隙锁(RR)、意向锁

InnoDB加锁的粒度和是否索引有很大关系，使用索引走行锁，不使用可能就走表锁了。
间隙锁只作用于RR级别，它通过锁定一个范围的记录(左开右闭)，对于中间数据既不能update也不能insert。解决幻读的问题，Mysql通过间隙锁(Gap)在其他事务执行的时候锁定住自身事务操作的一个范围,使得其他事务无法在此范围内插入数据，从而解决了幻读的问题.
共享锁称之为读锁，S锁，它允许其他事务追加S锁，但是不允许添加X锁(排它锁)。排它锁称之为写锁、x锁，顾名思义，有他在的地方禁止其他锁添加
意向锁：表级锁，同样有X、S之分，InnoDB自动控制，主要为了行锁和表锁的平衡共存，加X锁先得取得意向X锁(IX)，加S锁先得取得意向S锁(IS)

MVCC原理

MVCC主要是和RC和RR两个隔离级别打交道，因为脏读下事务总会看到其他事务未提交的数据，这本身就和MVCC理念相悖，而序列化旨在给每一行数据都加锁，MVCC也就没有意义了。

快照读和当前读

快照读

在RC和RR隔离级别下，MVCC作用下我们查询数据读取到只是一个数据的内存快照(不一定是最新的版本)，这个称谓快照读

当前读

在查询的时候添加锁(for Update(排它锁)|LOCK IN SHARE MODE(共享锁)),读取数据的最新版本，称之为当前读。

InnoDB隐藏字段

MVCC实现主要依靠Undo Log事务版本链，也就是行记录中不可见的三个系统字段(包含我们前面提到过的，InnoDB如果未设置主键且无其他唯一索引，会自动增加一个6字节长整型的默认主键)

DB_TRX_ID:记录此版本最近提交事务的ID(事务下必有)DB_ROLL_PTR:回滚指针，指向Undo Log里面rollback segment的数据(事务下必有)DB_ROW_ID：隐式自增主键。这就是我们之前提到过的，为了保障InnoDB引擎表必须有主键作为聚簇索引的一个兜底实现。(可选)
具体使用可以参照下面Undo Log部分

Read View和可见性判断

当我们数据存在多个版本的时候，如何判断哪个版本对当前事务可见呢？

事务执行的时候，InnoDB会生成一个Read View,他有四个比较关键的属性:

• m_ids：在生成 ReadView 时当前系统中活跃的事务的事务ID列表。
• min_trx_id：生成 ReadView 时当前系统中活跃的事务中最小的事务ID，也就是m_ids中的最小值。
• max_trx_id：生成 ReadView 时系统中分配给下一个事务的ID值，就是全局事务ID（Max Trx Id），注意并不是m_ids中的最大值。
• creator_trx_id：生成该 ReadView 的事务的事务ID。事务中只有在执行了增删改操作时才会分配一个事务ID，如果是一个只读事务，那 creator_trx_id 默认就为0。

可见性判断

声明：此章节节选自博客：https://juejin.cn/post/6978632592140533796
有了ReadView后，在事务中查询的时候，就可以沿着 undo 版本链查找当前事务可见的版本。这时 undo log 中的隐藏列 trx_id 就派上用场了，它表示产生这条 undo log 时的事务的事务ID。判断此版本是否可访问的依据就是用 undo log 中的 trx_id 属性值与 ReadView 中的各个属性做比较。
通过如下步骤来判断版本是否可被访问：

• 如果 trx_id 等于 creator_trx_id ，说明当前事务在访问它自己修改过的记录，所以该版本可以被当前事务访问。
• 如果 trx_id 小于 min_trx_id，说明生成该版本的事务在当前事务生成 ReadView 前已经提交，所以该版本可以被当前事务访问。
• 如果 trx_id 大于或等于max_trx_id，说明生成该版本的事务在当前事务生成 ReadView 后才开启，所以该版本不可以被当前事务访问。
• 如果 trx_id 在 min_trx_id 和 max_trx_id 之间，此时再判断一下 trx_id 是不是在 m_ids 列表中，如果在，说明创建 ReadView 时生成该版本的事务还是活跃的，该版本不可以被访问；如果不在，说明创建 ReadView 时生成该版本的事务已经被提交，该版本可以被访问。

流程图

4. Undo Log

undo log 是事务原子性实现的依据，为什么这么说呢？那你首先得了解undo log是什么？
redo Log是物理日志，而undo log则是一条逻辑日志，它记录的是你动作的相反操作，比如你执行一个DELETE操作，他就生成一个INSERT操作；你执行UPDATE操作，它记录一个相应UPDATE操作用来恢复你执行UPDATE之前的数据。
undo Log包含三部分单据，包括Insert UndoLog、Delete UndoLog、Update UndoLog三部分

Insert UndoLog:insert反向就是delete。所以 insert对应的undo log主要是把这条记录的主键记录上，后面可以根据相应主键进行删除回滚Delete UndoLog:
先是把记录头信息里面delete_mask标记为1，后面事务提交后通过purge线程执行真正操作。
Delete的恢复是通过隐藏记录列里面的DB_TRX_ID和DB_ROLL_PTR实现的，前者可以保障找到正确的事务版本链，后者则可以从Undo Log里找到对应反向的Insert 日志进行恢复Update UndoLog:这里分情况说明
更新主键：先删后增，也就是我们对于更新主键的行为会记录两条undo log(单行数据),一条记录删除的undo Log，一条记录新增的undo Log。
不更新主键:记录一条相反的更新undo Log(其实这里还会根据更新值前后所占空间大小变化调整策略，有兴趣的朋友可以参考博文：
https://juejin.cn/post/6977166688357711886)

4.1 Undo Log事务回滚恢复

前面说到每一次写入操作都会生成一条或多条相反的Undo Log，我们称之为Undo Log的版本链。事务回滚后我们可以通过版本链顺序的执行Undo Log中的逻辑日志信息，将数据恢复事务开启前的状态。

注意：undo log 是逻辑日志，只是将数据库逻辑地恢复到原来的样子。所有修改都被逻辑地取消了，但是数据结构和页本身在回滚之后可能大不相同。因为同时可能很多并发事务在对数据库进行修改，因此不能将一个页回滚到事务开始的样子，因为这样会影响其他事务正在进行的工作

链接：
https://www.cnblogs.com/qiuzhiqiang/p/16050432.html