Mysql InnoDB引擎原理

一、InnoDB是什么？

Mysql从5.5开始就将InnoDb做为默认的存储引擎，它也是目前使用最多的一款存储引擎，其次就是MyiSam引擎。

二、InnoDB的体系结构

InnoDB体系结构

InnoDB主要分为内存数据结构、磁盘数据结构。
在内存中，主要是Buffer pool缓存和Log Buffer缓存，而在磁盘中，则是各种表空间进行分割数据，每一个表空间存放的数据和作用都是不同的。磁盘中主要的文件有双写缓存文件、undo log、redo log。

三、InnoDB的存储结构

Mysql的数据文件都是存放在磁盘中，每次查询数据都要从磁盘读取到内存中，但是从磁盘读取文件的速度比内存读取慢了几个数量级，因此为了提升读取速度，Mysql每次都是按页进行读取数据，每页的大小为16KB，对修改过的数据回写磁盘也是按页回写。

行格式

对于每一页数据而言，还可以细分为行，也就是一页有多行数据存放。

行格式
一行主要有三部分组成：额外信息、隐藏列、真实数据。
其中额外信息主要是InnoDB用于管理数据行、对数据行进行状态标识使用；
隐藏列：
DB_ROW_ID:标识一条记录的唯一ID
DB_TRX_ID:表示事务的ID
DB_ROLL_PTR:回滚指针
真实数据：就是用户的业务数据。

索引页

索引页就是上面提到的Mysql为了加快从磁盘读取速度，按页读取的单位。

页的数据格式

Infimum + Supremum：最小记录和最大记录
User Records:用户记录，就是存储数据行
Free Space：空闲空间，当前页面尚未使用的空间

刚生成页的时候，其实并没有User Records这个部分，只有当数据插入进来，才会从Free Space申请一个记录行的空间，然后划分给User Records，当Free Space使用完后，就会重新生成一个页，用于存放后面的记录。

每个数据页存放行的格式

当一页数据不为空时，里面的数据行会按照主键id的大小进行排序，然后形成一个单向链表，Infimum指向的是最小的一个数据行，而Supremum则是最大的一个数据行。如果数据被删除，就会从链表中移除。

Page Directory

Page Directory主要是解决链表查询的问题，如果按照现有的存储格式进行查找某条数据，那就必然要遍历整个链表，遍历链表还有可能找不到目标数据，这样时间复杂度相对较高，Mysql因此做了相关优化。
InnoDB的做法是为每个页再单独制作一个目录：

Page Directory示意图
1.将页中所有正常的数据行分为几个组
2.将每个组的最后一条数据，也就是最大的那条数据，单独提取出来存放在页尾Page Directory中
3.每组数据条数有如下规定：最小记录所在的组只能有一条数据，最大的记录所在组的数据在1_{8条，其他组的数据条数在4}8之间。
查找数据时，通过主键进行二分查找，然后定位对应的组，再遍历该组的数据。

四、InnoDB中的表空间

表空间可以看做是一个大池子，里面存放着很多的数据页，是用来管理和存放数据页的。
在InnoDB中，划分了两种表空间：独立表空间、系统表空间。
File-Per-Table Tablespaces（独立表空间）：就是以表名.ibd的文件，实际上就是我们建立的数据表。
系统表空间：一般叫ibdata1，对应着一个或多个文件。
区（extent）:一个表空间可以存放2的32次方个页，对于管理这么多个页而言，是相对困难的，为了更好地管理这些数据页，InnoDB引入了区这个概念，连续的64个页就是一个区。当数据量较大时，为数据分配空间就是按照区来进行分配，这样可以消除很多随机I/O，提升效率。

段（segment）：在进行范围查询时，其实就是对叶子节点进行顺序扫描，如果不区分非叶子节点和叶子节点，那么将这些页都进行范围扫描，执行的效率将大大折扣，因此引入了段这个概念，一个索引会分为两个段，分别是叶子节点段和非叶子节点段。段是逻辑上的概念，而非物理上的连续空间。

双写缓冲机制（double write buffer）

doublewrite buffer是属于系统表空间的一部分，占用128个页，也就是两个区。因为Mysql的页大小是16KB，而操作系统每次只能写4KB的数据，在某些极端情况下，可能导致部分页写入的情况。
为了解决这个问题，Mysql引入doublewrite buffer机制，在将脏页数据写入磁盘前，先将数据写到doublewrite buffer中，然后立刻写到磁盘中，这个过程是顺序写，性能损耗并不大，在doubulewrite写完后，才会将数据写入其它文件中。
当Mysql发现有部分页写入的情况，就会使用doublewrite的数据进行相应的数据页恢复。

五、InnoDB的Buffer pool

Buffer pool是为了提升Mysql读取数据的速度，在系统启动时，就向操作系统申请了一块连续的内存空间，用于存放从磁盘读取的数据。

Buffer pool的内部组成

Buffer pool是由控制块和缓存页组成的。
每一个控制块都对应一个缓存页，控制块主要存放该页的表空间编号、在Buffer pool中的地址、链表节点信息等。
详情如下图：

buffer pool数据结构

free链表

free链表主要就是记录buffer pool中有哪些缓存页是空闲的，然后将这些空闲页对应的控制块构建成一个链表，当有数据要存放到buffer pool中时，就从free链表中移除一块，表示该缓存块已经被使用了。

flush链表

flush链表主要就是记录哪些页面的数据有改动，需要写回到磁盘中。其构造的结构和free链表类似，都是将对应页的控制块信息构建成一个链表，然后再某个时间点再去刷盘。

LRU链表

当buffer pool的内存容量不足时，要将不常用的数据页进行清除，最好的实现方式就是LRU链表。但是淘汰那些数据页，淘汰多少数据页这个没有办法控制，因此Mysql中又对LRU链表做了热数据和冷数据区分，也叫young区域和old区域。
因为局部性原理，LRU会将最近访问的数据页移动到头结点，但是频繁的移动数据页也会导致性能降低，因此Mysql对LRU又做了进一步的优化，热数据区的后1/4数据页访问才会移动到头结点，old区域和young区域的前3/4都不会移动到头结点。

buffer pool中刷新脏页到磁盘

1.从LRU链表的冷数据区域刷新一部分页面到磁盘
2.从flush链表中刷新一部分页面到磁盘
以上两种刷盘都是后台有线程在执行，因此不会影响用户的操作。