第二篇：MySQL中InnoDB引擎的物理存储结构

1. 个人理解

看了很多MySQL的书籍和博客，感觉都是互相抄来抄去，把知识点的罗列，讲不清楚前因后果，让人看起来莫名其妙的。所以，我决定从MySQL的底层物理存储结构了解，掌握了InnoDB的物理存储结构，再理解索引，锁，事务，日志之类的上层优化就很容易了。

2. 知识来源

本文主要观点来自于阿里数据库内核月报
http://mysql.taobao.org/monthly/2016/02/01/
和一篇程序员宅基地
https://blog.csdn.net/jiang18238032891/article/details/108471750
本文主要梳理大致组织结构，不会深入每个细节，主要想让读者明白大致原理即可，因为InnoDB的组织过于复杂。如果文章存在错误，请多多包涵，望批评指正。

3. 基本知识

3.1、页PAGE

首先，InnoDB将物理磁盘划分为页page，每页的大小默认为16KB，页是最小的存储单位。因为上层应用的需要，比如索引、日志等，页有很多的格式。我们主要说数据页，也就是存储实际数据的页。
首先看，数据页的基本格式，如下图

3.1.1、File Header
描述数据页的外部信息，比如属于哪一个表空间、前后页的页号等。

名称	描述
check_sum	数据页的校验和
page_num	数据页的编号
space_id	数据页所属的表空间id
prev_page_num	上一个数据页的页号
next_page_num	下一个数据页的页号
lsn	最近刷新的日志编号

数据页在物理磁盘上是按照双向链表的方式来连接的

3.1.2、User Records
用户纪录，也就是数据库表中对应的数据，这里我们说常用的compact格式。

3.1.2.1、变长字段长度列表
InnoDB支持变成VARCHAR等数据格式，所以，在纪录的最前边纪录起占用的字节数，通过字节数来正确的读取数据

3.1.2.2、NULL值列表
通过NULL值列表用一个bit来标记为NULL的列，代替用NULL来标记真实数据，可以省空间

3.1.2.3、纪录头信息
用来描述纪录的一些信息
比如是否删除、下一条纪录的位置等信息

名称	描述
next_record	下一条纪录的位置信息
delete	是否被删除
type	0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录

3.1.2.4、列对应的真实数据
InnoDB除了我们插入的数据外，还有一些隐藏列，transaction_id（事务ID）、roll_pointer（回滚指针）是一定添加的。row_id则不一定，根据以下策略生成：
优先使用用户建表时指定的主键，若用户没有指定主键，则使用unique键。若unique键都没有，则系统自动生成row_id，为隐藏列。

3.1.3、Page Header
PAGE_HEADER用来描述数据页中的具体信息，比如存在多少条纪录，第一条纪录的位置等

名称	描述
rec_count	纪录的数量
free_top	freespace的最小地址
delete_addr	第一条被删除的纪录地址
delete_space	删除纪录的总空间
btree_level	当前页在B+树中的层级

3.1.4、infimum和supremum纪录
infimum和supremum是系统生成的纪录，分别为最小和最大纪录值，infimum的下一条是用户纪录中键值最小的纪录，supremum的上一条是用户纪录中键值最大的纪录，通过next_record字段来相连。

3.1.5、Free Space
页中目前空闲的存储，可以插入纪录

3.1.6、Page Dictionary
类似于字典的目录结构，根据主键大小，每隔4-8个纪录设置一个槽，用来纪录其位置，当根据主键查找数据时，首先一步到位找到数据所在的槽，然后在槽中线性搜素。这种方法比从前到后遍历页的链表的效率更快。

3.1.7、Page Tailer
File Header存储刷盘前内存的校验和，Page Tailer储存刷盘后的校验和。当刷盘的时候，出现异常，Page Tailer和File Header中的校验和不一致，则说明出现刷盘错误。

3.1.8、插入纪录过程
如果Free Space的空间足够的话，直接分配空间来添加纪录，并将插入前最后一条纪录的next_record指向当前插入的纪录，将当前插入纪录的next_record指向supremum纪录。
如果Free Space的空间不够的话，则首先将之前删除造成的碎片重新整理之后，按照上述步骤插入纪录。

如果当前页空间整理碎片之后仍然不足的话，则重新申请一个页，将页初始化之后，按照上述步骤插入纪录

3.2、区EXTENT

引入EXTENT的原因：
如果只有页这一层次的话，页的个数是非常多的，存储空间的分配和回收都会很麻烦，因为要维护这么多的页的状态是非常麻烦的。

所以，InnoDB又引入了区extent。一个区默认是64个连续的页组成的，也就是1MB。通过对EXTENT进行管理来进行存储空间的分配和回收就比较容易了。

3.3、段SEGMENT

为什么要引入段呢，这要从索引说起。我们都知道索引的目的是为了加快查找速度，是一种典型的用空间换时间的方法。

我们首先看没有索引的时候，数据是怎么查找的：
根据page的列表，从头到尾来遍历，速度极慢。可以看出没有索引的话，数据的查找效率极慢

那么索引是怎么来解决问题的呢

首先我们创建一个表

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)

下图为其纪录对应的格式。
record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、1表示索引纪录（下文中会提到）、2表示最小记录、3表示最大记录

放入页中的示意图如下

然后我们向表中插入数据

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

按照主键大小排列成单链表存储在页中（物理位置不一定是挨个排列的），效果图如下

此时我们再插入一条纪录

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

我们假设每个页中最多只能存在3条记录，所以需要申请一个新的页来存储，示意图如下：

为了显示效果，我们多插入几条纪录

这是我们可以每隔若干个页来抽取一个页来建立上层目录，类似于跳表的数据结构

目录项中只包含被抽中页中的最小的键值和其对应的页号。

那么目录项怎么存储呢？有没有发现跟数据页中的纪录很像？
所以，引入了索引页，其中的纪录的record_type为1.

然后我们迭代抽取页来建立上层索引，直至到一层只有一个页为止

上图的结构就是B+树。

当有了索引之后，我们如何查找数据呢？

跟二叉搜索树的查找过程极为相似，但是B+树有多个子节点，我们根据PageDictionary来快速查找目的的子节点，然后不断细化到叶子结点即可。
这种查找方式的效率比单链表的从头到尾遍历要高效很多倍

B+树的叶子节点存放的是我们的具体数据，非叶子结点是索引页。
所以B+树将数据分为了两部分，叶子节点部分和非叶子节点部分，也就我们要介绍的段Segment，创建两个Segment来存放对应的两部分数据。

Segment是一种逻辑上的组织，其层次结构从上到下一次为Segment、Extent、Page。

4、InnoDB物理存储架构

上图为InnoDB的系统架构图。

每个表对应着一个文件，将文件划分为若干个页。
其中有三个比较特殊的页：
1、Page0:page0为文件的第一个页，类型为FIL_PAGE_TYPE_FSP_HDR， 主要用于维护文件中的空间分配和释放
2、IBUF BITMAP PAGE：与本文关系不大，忽略
3、inodePage：内含多个inode_entry来描述B+树占用的Page和Extent情况。

4.1、Page0

page0分为两部分
1、文件管理信息
主要维护了5个链表，头节点和尾节点
free：还未被使用过的extent，指向当前还空闲的extent的entry
frag：被使用但是还未使用完的extent，指向有碎片的extent的entry
full：完全被使用完的extent，指向被填满的extent的entry
inode_free：可用的inode页
inode_full:被完全使用的inode页

**当所有的free链表上的extent都用完后，会申请新的extent，并将其信息注册到对应的extent page 中的extent entry，并将其extent entry加到free链表中。

**如果inode_free中inode page也用完后，也会申请新的inode page 将其加入到inode _free链表上

2、256个extent entry
一个extent entry用来描述一个extent的信息，一个extent是由连续的64个page组成，一个extent的大小为1M。
也就是说每隔256MB（不一定连续）就需要一个extent page来描述对应的256个extent的状态。

extent page 和page0的格式大概一致，只不过少了文件管理信息，只有用256个extent entry。

extent page存在于第一个extent的第一个page，那么这个extent在被使用的时候会被加入到frag中，而不是free中。

名称	描述
id	如果当前extent被完全分配给某个segment的话，填入其SegmentID
prev	上一个extent的地址
next	下一个extent的地址
bitmap	用一个bit来表示其所管理的64个page是否被使用

4.2、Inode Page

Inode Page用来管理文件中的segment，默认可以存85个inode_entry，一个entry对应一个segment。

名称	描述
prev	上一个inodepage的地址
next	下一个inodepage的地址
inode_entry1	第一个InodeEntry
…	…
inode_entry85	第85个inodeentry

InodeEntry的结构如下

名称	描述
segmentId	对应的segment的id
free	分配给该segment却还未使用的extent链表
frag	分配给该segment已经使用过的extent链表
full	分配给该segment并完全使用过的extent链表
num	frag链表中被使用的page的个数
page0	第1个独立的page
page1	第2个独立的page
…	…
page31	第32个独立的page

4.3、表创建过程

1、首先创建表的时候，InnoDB默认会创建一个B+树。
主键的生成策略：
优先使用用户建表时指定的主键，若用户没有指定主键，则使用unique键。若unique键都没有，则系统自动生成row_id，为隐藏列。

B+树根据主键大小来进行排序

如上文所说，B+树分为leaf_segment和non_leaf_segment。两者的生成方式大致一样，以non_left_segment为例，

1、首先利用Page0中的inode_free链表来获取一个inode page，并得到其中的一个InodeEntry，将其segmentid填入，并将其中的page0作为rootpage，初始化完成。

2、分配新page，按照以下策略获取：
a、尽量使用32个独立的page
b、尽量使用与当前页面物理位置接近的页面
c、尽量使用frag链表中的页面

3、回收page
a、若page所在的extent为full，则将其变为frag，并挂到full链表的末尾，如果extent变为了free，则挂到free链表的末尾
b、改变extent_entry中的bitmap的标志位

5、结束

大概先写这么多吧，第一次写博客，有点前言不搭后语，望多多包涵。如果有这方面不错的的技术文章或者书籍，希望朋友们留言评论。