InnoDB数据结构
1 数据库的存储结构：页
索引信息和数据记录都是保存在文件上的，确切来说是保存在页结构中；另一方面，索引是在存储引擎上实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同的存储引擎的存放格式是不同的，比如Memory甚至不使用磁盘进行存储数据。
磁盘和内存的基本交换单位：页
页之间可以不在物理上相连，只需要通过双向链表的方式向连接。而页中的数据会按照主键的大小从小到大排序成一个单链表，并且每个数据页会为存储在它之中的记录生成一个页目录，以方便在通过主键查找的时候直接通过二分法找到对应的槽，然后遍历该槽对应分组中的记录即可。
以页作为磁盘和内存交互的基本单位，意思是：
一次最少将16kb的记录从磁盘加载到内存，或者从内存刷回磁盘
不论是读一行还是读多行，都是将这些行对应的页进行加载
总结来说：页是数据库管理存储空间的基本单位，也是数据库IO操作的基本单位
页的大小
不同的DBMS的页大小是不同的，在mysql中通过系统变量innodb_page_size可以查看默认页大小：
mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)
页的上层结构
在数据库中，页的上层结构还包括着区、段、表空间的概念，它们的关系如下：
区：在InnDB中，一个区会分配64个连续的页，大小则为64 * 16 kb = 1024 KB = 1 MB
段：段由一个区或多个区组成，在段中不要求区和区之间是相连的，段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。当我们创建索引、表的时候，就会创建相应的索引段和表段
即段是面向数据库对象，如索引、表的分配单位
表空间：是一个逻辑容器，表空间的存储对象是段，一个表空间可以有一个或者多个段，但是一个段只能属于一个表空间。数据库由一个或者多个表空间组成，表空间可以分为：系统表空间、用户表空间、撤销表空间和临时表空间等
系统表空间即数据目录下的ibdata1文件
2 页的内部结构
页结构的示意图如下所示：
这七个部分的作用分别如下：
| 名称 | 占用大小（字节 B） | 说明 |
|---|---|---|
| File Header | 38 | 文件头部，描述页的信息 |
| Page Header | 56 | 页头部，页的状态信息 |
| Infimum + Supremum | 26 | 最大和最小记录，两个虚拟的行记录 |
| User Records | - | 用户记录，存储行记录内容 |
| Free Space | - | 空闲记录，页中还没有被使用的内容 |
| Page Directory | - | 根据用户记录生成的页目录，存储用户记录的相对位置 |
| File Trailer | 8 | 文件尾部，检验页是否完整 |
1 File Header & File Trailer
首先是文件通用部分，也就是文件头和文件尾
①文件头部，描述页的信息，比如页的编号、它的上一个和下一个页是谁，所有的数据页会组成一个双向链表：
FILE_PAGE_OFFSET：每一个页的单独页号，InnoDB可以通过页号唯一定位一个页
FILE_PAGE_TYPE：当前页的页类型
FILE_PAGE_PREV FILE_PAGE_NEXT：上一页和下一页的页号，如此便通过这样的双向链表将多个页连接起来了
FILE_PAGE_SPACE_OR_CHECKSUM：文件校验和，用于和文件尾部的校验和搭配使用检测页的完整性
校验和：类似于哈希，指利用某种算法来对一个字节串生成一个比较短的值，利用这个值来比较两个字节串是否相同。
比如刷盘的过程中，数据页同步磁盘的时候突然宕机了，导致文件头部进行了更新而文件尾部没有，这时候就可以通过检查头部和尾部的校验和来判断页的完整性
FILE_PAGE_LSN：页面最后修改时对应的日志序列
②文件尾部
前四个字节记录和File_Header对应的文件校验和
后四个字节记录最后修改时对应的日志序列(LSN)
如果首部和尾部的LSN值校验不成功的话，也说明同步过程中出现了问题
2 记录部分
Free Space空闲空间
每当插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一块记录大小的空间划分到User Records部分，当Free Space部分全部被User Records替换完了，如果还有新的记录插入的话，就需要去申请新的页了。
User Records
User Records中的记录，按照指定的行格式形成单链表存储在User Records中。
而用户记录的数据是如何记录的，就需要讲一下行格式记录头信息，这里以Compat行格式为例：
delete mask：记录是否被删除，0表示没有1表示已经删除，占用一个二进制位
为什么被删除的记录还要存储在页中呢？
后续添加的记录可以直接在已删除记录形成的垃圾链表中进行覆盖，这样能够减少删除带来的性能消耗。
至于删除带来的消耗，感觉这里视频
移除会导致重新排列是不对的，因为记录之间是通过单链表连接，也不是很明白记录之间紧密连接是什么意思，弹幕说的会导致B+树的调整也不是主要的吧（小于一定值会导致页的合并）的，正确的应该是： 数据页根据记录生成的页目录由于是连续存储，所以当记录删除的时候，如果删除页目录项会导致重新排列，认为我想得不对的话，欢迎在评论区指正
min_rec_mask：B+树每层非叶子节点的最小记录都会添加该标记为1，如下图的四条记录都为0，表示都不是B+树的非叶子节点的最小记录
record_type：0：普通记录，1：B+树非叶子节点记录，2：最小记录，3：最大记录
heap_no：记录在本页中的位置，如下图中的位置分别为2 3 4 5
为什么没有1和2呢，这是因为1和2记录的是虚拟行（不存储真实数据），是这个表中的最小和最大记录，这部分不是用户定义的，因此不属于User Records
n_owened：最后一组记录中的头信息中会存储该组总共多少条记录
next_recodr：记录下一组记录的偏移量
假设现在插入四条数据，则User Records部分的情况如下：
INSERT INTO page_demo VALUES (1, 100, 'song'),
(2, 200, 'tong'),
(3, 300, 'zhan'),
(4, 400, 'lisi');
Infimum + Supremum
上面简单介绍行格式的heap_no的时候介绍过了，这里补充一下实际添加过程中就是在最小和最大记录之间添加节点的过程，增删的过程：
设置delete_mask为0或1
修改前后指针
修改最后一个记录的n_owned
3 页目录与页头
在页中，记录之间是以单链表的方式进行存储的，优点是插入、删除比较方便，缺点是检索效率不高，因此专门设置一个页目录，通过二分查找的方法来提高检索效率。
但是如果把所有的记录的索引列都放入页目录中的话，存储消耗实在太大，因此使用数据结构中的分组查找的方式：
首先将所有的记录分组，这些记录包括最小和最大记录，但是不包含已经删除的记录
第一组只包含最小记录，最后一组是最大记录所在的分组，包含1-8条记录
其余组的记录数在4-8条之间
在每个组的最后一条记录的头部信息都会存储该组总共有多少条记录，作为n_owned字段
页目录用来存储最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储下来，每组的地址偏移量又被称作为槽(slot)，即每个槽都相当于指针指向了不同分组的最后一条记录
这么做的目的是除了最小记录，其他的组尽量评分其他所有记录
为什么上面最小记录的n_owned为1，而最大记录为5？
n_owned记录的是页目录槽内记录的个数，在分组的时候最小记录自成一组，分组的过程如下：
初始情况下，一个数据页中只有最小和最大记录两个虚拟页，它们属于两个分组
之后插入每一条数据，都会从页目录中查找比该条记录的主键值大而且差值最小的槽，然后插入槽内并将槽内最后一条记录头信息中的n_owned+1，直到为8
当超过8个的时候会分为两个组，一个为4，另一个为5条记录，这时候页目录也会生成一个新的槽来记录这个新的分组中最大的那条记录的偏移量
页目录结构下如何在数据页中快速查找记录
首先通过二分法从页目录中查找比该条记录的主键值大而且差值最小的槽
然后由于槽实际是指向记录分组中的最大分组的指针，而且记录之间是通过单链表的方法链接的，所以要利用上一个槽的指针到这个槽指针之间利用记录的next_record属性来进行顺序查找
页面头部
PAGE_N_DIR_SLOTS：分组、槽的数量（方便进行二分查找）
PAGE_FREE：前面所说的垃圾链表
PAGE_DIRECTION：记录记录插入的方向，递增的方向是右，递减是左
PAGE_N_DIRECTION：记录连续插入同一个方向记录的数量
