Mysql原理简介

行格式

InnoDB有四种行格式，或者是记录格式，分别是Compact，Redundant，Dynamic，Compressed，1，3，4是比较相似的，区别在于页溢出的处理方式。

c1(VARCHAR(10)	c2(VARCHAR(10) NOT NULL)	c3(CHAR(10))	c4(VARCHAR(10))
aaaa	bbb	cc	d
eeee	fff	NULL	NULL

变长字段长度列表

在变长字段长度列表里面逆序存储 变长列的真实数据的字节长度。类似VARCHAR(M)这样的变长字段。
举例：

现在列中的内容长度比较短，长度可以使用一个字节来表示，如果长度很长，可以使用两个字节来表示。具体使用一个还是两个，you有具体的算法。
变长字段长度列表中不存储null 的列。

Null 值列表

如果表中没有允许存储 Null 的列，那么 Null 值列表也不存在。使用二进制按照列的顺序逆序排列，1:表示该列的值为 Null，0表示该列的值不为Null。同时必须是整数个字节的位，否则高位补0。
以第二条记录为例，011，逆序就是110，高位补5个0，十进制为6。

记录头信息

包括改记录是否被删除，当前记录的类型，下一条记录的相对位置等等。

真是数据

会添加隐藏列，如果没有合适的作为主键的列，会添加 row_id,(先寻找自定义的主键，没有的话寻找非 null, nuique的键),transaction_id,roll_pointer 的三个隐藏列。

如果使用的变长字符集，c3列也会加入到变长字段长度列表中。

行溢出数据

MySQL 对一条记录占用的最大存储空间是有限制的，除了blob或者text类型的列之外，其他的列占用的字节长度之和不能超过65535个字节。

数据页结构

页是 innodb 管理存储的基本单位，一个页的大小一般是16kb。为了不同的目的，设计了很多种不同的页。存放记录的页就 index 页，暂时称为数据页。

行记录

插入行记录时先去free space申请空间。每一行记录的记录头信息中包含heap_no：在页中的位置，在infimum+supremum中存储这自动生成的两个隐藏行，最小最大行，分别是0和1。next_record：下一条记录的真实数据的地址偏移量，可以简单的理解成链表。

页目录

是为了更快的查找页中的记录，将页中的记录分组，在分组的最后一条记录的头信息中记录当前组的记录条数。最小组只能有1条记录，最大组在1-8条，剩下的在4-8条。

查找的时候使用二分查找查找槽，对比查找到的槽对应的记录的主键大小，决定查找的方向。因为页中的记录是单链表，所以找到槽之后，找上一个的槽，然后找这个槽对应的记录向下找。

Page Header页面头部

数据页专属，记录存储了多少记录，多少槽，第一条记录的地址等。

File Header文件头部

页通用的部分，包括页校验和，页号(使用这个定位页),前一个页和后一个页的(页号)”指针”，页类型

File Trailer

存储的时候校验页的完整性，和 header中的校验和进行对比

B+树索引

非叶子节点使用的是和存放记录的页一样的数据页，但是其中的记录只有两列，对应子节点的最小主键和对应的子节点的页号。还有就是头信息中的record_type=1,正常的是0。

查找的过程，先从根页面开始，在页面的槽中进行二分查找，找对对应的下一级页号，在循环执行上面的操作，找到叶子节点，在叶子节点中寻找真实的记录。页中的记录是按照主键大小从小到大。页与页之间形成了双向链表。这叫聚簇索引。

二级索引

非叶子节点也是类似聚餐索引，按照列的顺序，不过叶子节点中的记录只有对应列的值和主键，然后在进行回表，进行聚簇索引的查找。为了保证b+树的同一层内节点的目录项记录除了页号以外的唯一性，会加入主键作为一列。也就是会有三列，索引列，主键，页号。

联合索引

规则也是类似上面，不过页中的记录存放的联合索引的所有列，按照索引中的顺序进行先后排序。这也能很好的理解联合索引中的最左匹配原则。因为页中的记录是要有序排列的。

建索引的时候，先创建根节点，然后随着记录的插入，进行页分裂。也就是索引一旦建立，根节点就确定了，不会再移动，这也方便了根节点的查找。根节点的页面信息存储在数据字典中。

MyISAM的索引

索引和数据是分开的，也就是所有的索引都相当于二级索引。先在索引文件中根据主键或索引列找到对应的行号，再去数据文件中根据行号找到完整的记录。

索引使用注意

表空间

区：连续的64个页
组：256个区

第一个组的前三个页面是固定的：
FSP_HDR：表空间的整体属性和本组的所有区的属性，一个表空间就这一个
IBUF_BITMAP：存放本组的区的所有页面关于INSERT BUFFER的信息
INODE：存放INODE类型

每组最开始的两个页是固定的：
XDES：记录本组区的熟悉
IBUF_BITMAP：同上

区的概念的引入是为了让相邻的页尽可能的在一起，顺序I/O。当数据量很大的时候，以区为单位分配空间。

为了区分叶子节点和非叶子节点，提出了段的概念：叶子节点所在的区放在一个段里面，非叶子节点所在区放到一个段里面，也就是一个索引有两个段。

为了在数据量较少的时候节约空间，提出碎片区的概念，这里面的页面可以属于不同的段。碎片区属于表空间。先向碎片区中以页面为单位分配空间，当一个段中有32个碎片页面的时候，就以完整的区分配空间。后面再有数据来，就不在属于表空间的碎片区中找了，就去段的那三个链表中找页面。

为了管理区，设计了XDES Entry的结构，存储了区的信息。

Page State Bitmap存储区中的页面是否空闲

这个结构的双向链表的作用：空闲区组成一个链表，有空间的碎片区组成一个链表，满的碎片区组成一个链表。为了插入数据的时候更快的找个应该插入的区。

上面说的都是针对属于表空间的碎片区。为了更好的管理属于段的区，每个段也有三个链表。

也就是一个索引，有两个段，每个段有三个链表。还有属于表空间的三个链表。

为了找到这些链表的头结点或者尾节点，设计了List Base Node的结构。包括链表长度，首尾指针的位置。

类似区有对应的XDES Entry结构，段也有INODE Entry的结构用来表示段的信息。有段号，三个链表的List Base Node，碎片页面的信息。

前面说的，表空间的第一个页面FSP_HDR，存储了表空间的整体熟悉和第一个组的256个区对应的XDES Entry信息。

所以属于表空间的三个链表的基节点可以在这里找到。后两个是段对应的INODE Entry构成的链表的基节点。

而索引的根节点的头信息中有对应的段信息，所有就把根节点和段映射到了一起。

系统表空间

单表查询

const:通过主键或者唯一二级索引
ref:使用普通二级索引进行等值比较
ref_or_null:普通二级索引进行等值比较或者 null
range:范围匹配
index:匹配规则不是联合索引的最左索引列，可以遍历索引叶子节点。
all:全表扫描

一般只能使用单个二级索引进行查询，也就是会选择最优的索引。

索引合并的情况可以使用到多个二级索引。(1，二级索引是等值匹配;2,主键列可以是范围匹配)
Intersection合并:交集合并
Union合并:并集合并
Sort-Union合并:排序并集合并

连接的原理

驱动表:首先查询的表
被驱动表:根据驱动表查询出来的数据进行查询的表
内连接:驱动表中找不到的数据不会加入结果集
外连接:驱动表中的找不到的数据仍然加入结果集
左外连接:左边的表作为驱动表
右外连接:右边的表作为驱动表

1嵌套循环连接:最简单粗暴的循环查询，在被驱动表使用合适的索引加速
1基于块的嵌套循环连接:设计了内存的join buffer，将驱动表的结果集放到这里，搜索被驱动表的每一条记录时，在内存中与这些记录比较。

基于成本的优化

读取一个页的成本:1.0
读取以及检测一条记录:0.2

找执行计划的步骤：
1.根据搜索条件，找出所有可能的使用的索引
2.计算全表扫描的代价
3.计算使用不同索引执行查询的代价
4.对比各种方案，找出陈本最低的那个

计算全表扫描的代价时，页面数和记录数是由mysql为每个表维护了一份统计数据。

当计算成本的代价很大时候，使用索引统计数据计算代价。

连接的查询成本，驱动表的访问成本+驱动表的扇出数*被驱动表的访问成本

外链接驱动表固定，方便计算。内连接需要将两个表分别作为驱动表计算成本。

如何收集统计数据

以表为单位收集和存储统计数据，数据可以持久化也可以只在内存中。

分为表统计数据和索引统计数据，分别保存在两个表中。

表有多少行记录的估计值。按照一定的算法选取几个叶子节点页面(默认20个)，计算每个页面中的主键值记录数，然后计算平均一个页面中主键值的记录数量乘以全部叶子节点的数量。

更新统计数据可以自动的异步更新，也可以手动触发更新

有个变量决定在统计索引列不重复值的数量时如何对待Null。最好不要在索引列放Null

基于规则的优化

• 移除不必要的括号
• 常量传递
• 等值传递
• 移除没用的条件
• 表达式计算
• HAVING子句和WHERE子句的合并
• 常量表检测
• 外连接消除(符合null值拒绝)

  子查询优化

  标量子查询和行子查询就是想象的那样
  in查询条件少时，也是类似上面，条件多的时候会创建临时表，叫做物化表。还有进一步的semi-join半连接(有规则限制)。

Explain 详解

• table表名
• id分配的唯一id。连接的时候，每个表对应一条记录，id相同；前面的驱动表，后面的被驱动表；当优化器重写了子查询，可能转换成连接，id也是一样。
• select_type查询的类型，有SIMPLE，PRIMARY等等
• type执行查询的访问方法。前面有介绍，有const，ref等等
• possible_keys和key可能用到的索引和实际使用的索引
• key_len使用的索引记录的最大长度，一般用在联合索引中
• ref当使用索引列等值匹配的条件去执行查询时，展示与索引列作等值匹配的东东是个啥
• rows全表扫描时表示要扫描的行数，索引时表示预计扫描的索引记录行数
• filtered单表查询没什么意义，用在连接查询中。
• Extra额外信息

Buffer Pool

从磁盘中加载记录是以页为单位。缓存池就是在内存中缓存从磁盘上加载的页。
为了控制缓存池中的页，每个页有对应的控制块。是连续的一块内存。

为了记录缓存池中那些页是可用的，设计了free链表。

为了找到缓存池中的页，使用表空间号+页号作为 key，页作为 value，加入到哈希表中。

为了记录缓存池中那些页是脏页，也就是修改了的页，设计了flush链表，结构类似上面。

缓存池的大小有限制，设计了lru链表来控制页的淘汰。

因为innodb有线性预读和l随机预读的功能，为了防止预读的页加入到lru链表头部而降低缓存命中率，将lru链表分成了toung和old区域，比例是3/8。

当页第一次从磁盘加载到缓存中，放到old的头部。后面访问到再放到jian'gejiangey young`的头部。

为了防止全表扫描时大量使用频率低的页加入到young的头部。规定在对处于old的页第一次访问时候，记录下访问时间，如果下次访问时间和第一次的在某个时间间隔以内，不会加入到young的头，否则加入。

脏页的刷新分为把lru的old中的一些脏页刷新到磁盘，定时/当缓存池不足的时候执行。

根据繁忙情况，将flush链表中的页刷新到磁盘。

为了更好支持多线程，设计了多个缓存池实例。

为了支持运行时调整缓存池大小，不再一次性的申请一大片连续的内存空间，而是以chunk为单位申请。默认128m。

使用SHOW ENGINE INNODB STATUS查看缓存池状态。

事务

• 原子性(Atomicity)
• 隔离性(Isolation)
• 一致性(Consistency)
• 持久性(Durability)

数据库某些操作的原子性和隔离性都是保证一致性的一种手段，在操作执行完成后保持符合所有既定的约束则是一种结果。

使用SAVEPOINT保存点，方便回滚到特定的地方。

redo日志

因为innodb是以页为单位来管理存储空间，在持久化时也是以页为单位刷新到磁盘。 但是刷新一个完整的页比较浪费，随机io刷新比较慢。为了解决这个保证事务的持久性，设计了redo日志。因为redo日志仅仅记录的改动的内容，占用的空间小，顺序存储，顺序io效率高。

有很多种不同类型的redo日志，大部分的有这样的格式

执行一条语句可能涉及修改多个页，所有会产生多个redo日志。将日志进行分组，以组的形式操作日志，保证日志的原子性。

分组的标记是在组最后插入一个特殊的redo日志。

事务，语句和日志的关系

日志的写入过程

把mtr生成的日志都放到一个页里面(block)。同时也存在一个日志的缓存池redo log buffer。

在mtr运行时生成的日志，先放到一个临时的地方，执行完之后，再一起复制到log buffer中。

日志刷盘时机

• 缓存池空间不足时
• 事务提交时候候
• 后台线程自动刷新
• 正常关闭服务器时候。
• 等等

日志文件可能有多个，一个一个写，写到最后一个再从头开始。

文件头2048个字节是管理数据，后面的存储缓存池中的block镜像。

每一组由mtr生成的redo日志都有一个唯一的LSN值与其对应，LSN值越小，说明redo日志产生的越早。

1redo日志只是为了系统崩溃后恢复脏页用的，当脏页已经刷新到磁盘，这些日志也就不需要了，也就是可以被覆盖了。

使用checkpoint记录脏页刷新到的位置。

undo日志

undo日志是为了保证事务的原子性。为回滚设计。

在事务中，只有第一次对表进行增删改操作才会给这个事务分配一个事务 id.

记录的行格式，有trx_id，roll_pointer两个隐藏列。

在增删改之前要先记录undo日志。

插入的日志

对应的日志类型是TRX_UNDO_INSERT_REC，主要记录表个主键信息。

roll_pointer的含义

简单说就是指向undo日志的指针。

删除对应的日志

删除一条记录分为两步：

1. 将记录头信息中的delete_mask置为1，这个阶段是delete mark
2. 当事务提交后，由专门的线程将这个记录从正常的链表中移除，加入到垃圾链表中。这个阶段是purge。
   这么做主要是为了事务的mvcc。

对应的日志类型TRX_UNDO_DEL_MARK_REC。

在进行delete mark之前，先把这个记录的当前的trx_id和roll_pointer记录到日志中，这样形成了一个版本链，也是为mvcc服务。类似的情况可以是先插入一个，再删除这个，那回滚的时候就会用到这个版本链。

更新对应的日志

不更新主键的情况：
就地更新，也就是记录的各列的数据长度不变。
不能就地更新的，先删除旧记录，再插入新记录，这里的删除是直接移到垃圾链表中，而不是仅仅的标记，同时使用的同步剔除，而不是专门的线程。
使用的日志类型是TRX_UNDO_UPD_EXIST_REC；

更新主键的情况：
因为这时候主键变化了，在索引的中的位置也要改变。
先标记删除，这里仅仅的标记，是因为其他的事务也可能访问这个记录，如果直接移除到垃圾链表，别的事务就访问不到了，也是为了mvcc
然后插入一条数据。

记录一条TRX_UNDO_DEL_MARK_REC类型的日志

存储位置

日志页是存储在FIL_PAGE_UNDO_LOG页中，这些页也是像之前一样，组成双向链表。
在这种页的页头信息中记录的当前页存储的两大类日志的类型：
TRX_UNDO_INSERT:插入语句或者更新主键的时候产生
TRX_UNDO_UPDATE:删除语句或者更新普通记录产生

一个页面只能存储一种大类型的日志，不能混存。之所以分为两大类，也是为了mvcc，第一类在事务提交后可以直接删除，第二类还有用处。

两种类型的的日志的链表分别组成了两个双向链表，同时还有临时表和普通表的区别，也就是一个事务中，最多会产生四条链表。

不同的事务的链表是隔离的。也就是不同的事务过程中产生的日志需要写入不同的日志页面链表中。

每个undo页面链表都对应一个段，叫做Undo Log Segment，也就是链表中的页面都是从这个段中申请的。在链表的第一个页面中有Undo Log Segment Header，记录了对应段的信息。存储了当前页面链表处在什么状态

有活跃状态：一个活跃的事务正在往这个链表里面写日志；
被缓存状态：等待被其他事务重用
等等

重用undo页面

因为有些事务占用的日志页面很少，也为其分配了新链表比较浪费空间。
判断能否重用：
该链表中只包含一个页面；(页面很多，维护也是成本)
该页面使用的空间小于整个页面空间的3/4;

1insert undo链表的重用：因为这种链表在事务提交后可以删除，所有直接覆盖写页面
1update undo链表的重用：因为这种不能直接删除，所有在页面后面继续写，也就是一个页面包含多组的日志。

回滚段

为了管理这些undo链表，设计了回滚段的概念，这是一个段，但是就一个页面，这个页面中存储了undo链表的第一个页面的地址(undo slot)。

初始的undo slot的值的FIL_NULL。当要开始分配undo链表时候，先看这个槽是不是初始状态，如果是，就在这个槽中记录链表的第一个页面地址；如果不是，看下一个槽是不是。一共有1024个槽，也就是并发支持的事务有上限，会抛出异常。

当事务提交后，槽指向的页面符合重用条件，加入到缓存链表中，再有新事务分配槽时候，先去这个缓存链表中查找，找不到再去回滚段中的槽查找。

如果不能重用，对于指向的是insert undo链表，直接释放，初始化状态。update undo链表，初始化状态，将这些undo日志放到History链表中。

为了支持更多的事务并发，设计了多个回滚段。为了管理这些回滚段，在系统表空间中的第5号页面设计了128个包含8字节的格子，每一个格子对应一个回滚段。

事务隔离级别和MVCC(多版本并发控制)

因为事务并发执行的原因，为了最大可能的保持隔离性和性能，提出了mvcc。

脏写：

一个事务修改了另外一个未提交事务修改过的数据。这是一定要避免的。

脏读：
li一个事务读到另外一个未提交事务修改过的数据。

不可重复读：
一个事务只能读到另一个已经提交的事务修改过的数据，并且其他事务每次对这个数据进行一次修改并且提交后，该事务都能读取到最新值

幻读：
一个事务先根据某些条件查出一些数据，之后另一个书屋又向表中插入了符合这些条件的数据，原来的事务在此按照此条件查询时候，能把另一个事务插入的记录页读取出来

隔离级别

mysql在repeatable read的隔离级别下是可以禁止幻读的发生。

mvcc原理

前面说的版本链。每一条记录的头有trx_id事务 id 和roll_pointer回滚点，也是指向undo日志。同时在undo日志中，也又指向前一个undo日志的指针，这就形成了一个版本链。undo日志中页记录了事务 id。

####ReadView
对于READ UNCOMMITTED，每次读取最新的值就好了；对于SERIALIZABLE，使用加锁保证串行化。其他两个级别都要保证读取到已经提交的记录。也就是要判断版本链中哪个版本是对当前事务可见的。因此提出了ReadView的概念。一个ReadView包含下面四个重要内容：

1m_ids：在生成ReadView时，当前系统中活跃的读写事务的 id 列表
1min_trx_id：在生成ReadView时，当前活跃的读写事务 id的最小值，也是上面列表中的最小值
1max_trx_id：在生成ReadView时，系统应该分配给下一个事务的 id
1creator_trx_id:生成ReadView的事务 id。

当访问记录中的事务 id==当前的事务 id,说明是自己修改的，可以访问。

当访问版本的事务 id< 最小事务 id。说明访问的这个记录已经提交了，可以访问。

当访问的版本的事务 id>下一个事务 id。说明这个事务是在生成ReadView之后才开启的，不能访问。

如果访问的版本事务 id在 2，3之间，要判断事务 id在不在活跃的事务 id 列表中，如果在，不能访问。

如果当前版本的数据对当前事务不可见，就沿着版本链找，看能不能找到符合的版本。

1READ COMMITTED和REPEATABLE READ的不同在于生成ReadView的时机不同，前一个是每次读取事务前就生成一个，后一个是事务中第一次读取数据时生成一个，后面就不生成了。所以前一个能读取到相对较多的数据，后一个读取的数据就是生成ReadView时能读的，后面的就读不到了。前一个还有可能读到，因为它是不断生成的。类似快照。

锁

为了禁止脏写的情况，也就是并发写要排队，提出了锁的概念。锁在 MySQL 中是一个在内存中的结构。

当想对一条记录进行修改时候，如果没有对应的锁结构，生成一个。

如果一个有了，要阻塞等待锁释放。

实现mvcc一种是上面的版本链，还可以使用锁。

共享锁(s锁):
一个事务对一个记录加了 s 锁，另一个也可以加 s 锁。不能加 x 锁。

独占锁(x锁)：
一个事务对一个记录加了 x锁，其他事务不能加 s 锁也不能 x 锁。

SELECT ... LOCK IN SHARE MODE;s 锁读
SELECT ... FOR UPDATE;x锁 读

删除操作可以看成获取 x 锁的锁定读；
插入操作一般不加锁，提供隐私锁保护该记录在事务提交前被别的事务访问。
更新分三种：没修改主键且更新列的存储空间不变，就地更新，看成 x 锁的锁定读。
没修改主键但是更新列的存储空间变化了，要先删再插入，看成 x 锁的锁定读。

多粒度锁

表 s 锁：不能访问表 x锁和记录的 x 锁
表 x 锁：啥都不行。

当对表进行上锁时候，如何知道表中有没有被上行锁？因此设计了意向锁。

意向共享锁(IS)：当准备给一个记录上 s 锁，先对表上一个 IS 锁。
意向独占所(IX)：当准备给一个记录上 x 锁，先对表上一个 IX 锁。

MyISAM等其他引擎只支持表锁。

行级锁详情

1Record Locks：皮称 正经记录锁，分 s 和 x 锁。就是理解中的锁。
1Gap Locks：gap 锁，给当前记录前面加锁。仅仅是为了防止插入幻读记录提出的。
1Next-Key Locks:next-key 锁，给当前记录以及记录前面加锁。
插入的时候可以不显式的加锁。当插入一个记录后，马上有事务访问这个记录，会自动帮这个新插入的记录生成一个x 锁，然后在给自己生成一个锁，进行阻塞等待。

超全面MySQL语句加锁分析（上篇）
超全面MySQL语句加锁分析（中篇）
超全面MySQL语句加锁分析（下篇）