七、InnoDB数据存储结构
7.1、数据库的存储结构：页
索引结构提供了高效的索引方式，不过索引信息以及数据记录都保存在文件上的，确切说是存储在页结构中。另一方面，索引是在存储引擎中实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同存储引擎中存放的格式一般不同的，甚至有的存储引擎比如Memory都不用磁盘来存储数据。
InnoDB是MySQL的默认存储引擎。
7.1.1、磁盘与内存交互基本单位：页
InnoDB将数据划分为若干个页，InnoDB中页的大小默认为16KB。
以页作为磁盘和内存之间交互的基本单位，也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。也就是说， 在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。也就是说，数据库管理存储空间的基本单位是页（Page），数据库I/O操作的最小单位是页。 一个页中可以存储多个行记录。
记录是按照行来存储的，但是数据库的读取并不以行为单位，否则一次读取（也就是一次I/O操作）只能处理一行数据，效率会非常低。
7.1.2、页结构概述
页a、页b、页c…页n 这些页可以不在物理结构上相连，只要通过双向链表相关联即可。每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应的分组中的记录即可快速找到指定的记录。
7.1.3、页的大小
不同的数据库管理系统（DBMS）的页大小不同。比如在MySQL的InnoDB存储引擎中，默认页的大小是16KB
# 通过下面的命令来进行查看；
show variables like '%innodb_page_size%';
7.1.4、页的上层结构
区（Extent）是比页大一级的存储结构，在InnoDB存储引擎中，一个区会分配64个连续的页。因为InnoDB中的页大小默认是16KB，所以一个区的大小是64*16KB=1MB。
段（Segment）由一个或多个区组成，区在文件系统是一个连续分配的空间（在InnoDB中是连续的64个页），不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。当我们创建数据表、索引的时候，就会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引时会创建一个索引段。
表空间（Tablespace）是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。
7.2、页的内部结构
页如果按类型划分的话，常见的有 数据页（保存 B+ 树节点）、系统页、Undo 页 和事务数据页等。数据页是最常使用的页。
数据页的16KB大小的存储空间被划分为七个部分，分别是文件头（File Header）、页头（Page Header）、最大最小记录（Infimum+supermum）、用户记录（User Records）、空闲空间（Free Space）、页目录（Page Directory）和文件尾（File Tailer）。
这七部分的作用如下：
7.2.1、第1部分：文件头部和文件尾部
7.2.1.1、File Header(文件头)
文件头部信息
不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页，下一个页是谁等，所有的数据页会组成一个双链表。这个部分占用固定的38字节，是中下边这些内容组成的：
存放记录的数据页的类型其实是FIL_PAGE_INDEX， 也就是所谓的 索引页 。
数据页的链接实现
在文件头部内容中有两个属性：FIL_PAGE_PREV和FIL_PAGE_NEXT
InnoDB都是以页为单位存放数据的，如果数据分散到多个不连续的页中存储的话需要把这些页关联起来，FIL_PAGE_PREV和FIL_PAGE_NEXT 就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了，保证这些页之间 不需要是物理上的连续，而是逻辑上的连续。
检验页的完整性
# 什么是校验和?
- 就是对于一个很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和。
- 在比较两个很长的字节串之前，先比较这两个长字节串的校验和，如果校验和都不一样，则两个长字节串肯定是不同的，所以省去了直接比较两个比较长的字节串的时间损耗。
文件头部和文件尾部都有：FIL_PAGE_SPACE_OR_CHKSUM
InnoDB存储引擎以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候断电了，造成了该页传输的不完整。
为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况），这时可以通过文件尾的校验和（checksum 值）与文件头的校验和做比对，如果两个值不相等则证明页的传输有问题，需要重新进行传输，否则认为页的传输已经完成。
FIL_PAGE_LSN（8字节）：页面被最后修改时对应的日志序列位置（英文名是：Log Sequence Number）
7.2.1.2、File Trailer（文件尾部）
前4个字节代表页的校验和：这个部分是和File Header中的校验和相对应的。
后4个字节代表页面被最后修改时对应的日志序列位置（LSN）：这个部分也是为了校验页的完整性的，如果首部和尾部的LSN值校验不成功的话，就说明同步过程出现了问题。
7.2.2、第2部分：空闲空间、用户记录和最小最大记录
7.2.2.1、Free Space (空闲空间)
我们自己存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。
7.2.2.2、User Records (用户记录)
User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。
具体看7.3.2.3 记录头信息 章节。
7.2.2.3、Infimum + Supremum（最小最大记录）
记录可以比较大小吗 ？
是的，记录可以比大小，对于一条完整的记录来说，比较记录的大小就是比较主键的大小。比方说我们插入的4行记录的主键值分别是：1、2、3、4，这也就意味着这4条记录是从小到大依次递增。
InnoDB规定的最小记录与最大记录这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的。
7.2.3、第3部分：页目录和页面头部
7.2.3.1、Page Directory（页目录）
为什么需要页目录 ？
在页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。
# 方式1：顺序查找
- 从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到（或者找不到），在找的时候还能投机取巧，因为链表中各个记录的值是从小到大顺序排序的，所有当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增。
如果一个页中存储了非常多的记录，这么查找性能很差。
# 方式2；使用页目录，二分法查找
1. 将所有的记录`分成几个组`，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录。
2. 第 1 组，也就是最小记录所在的分组只有 1 个记录；
最后一组，就是最大记录所在的分组，会有 1-8 条记录；
其余的组记录数量在 4-8 条之间。
这样做的好处是，除了第 1 组（最小记录所在组）以外，其余组的记录数会`尽量平分`。
3. 在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段。
4. `页目录用来存储每组最后一条记录的地址偏移量`，这些地址偏移量会按照`先后顺序存储`起来，每组的地址偏移量也被称之为`槽（slot）`，每个槽相当于指针指向了不同组的最后一个记录。
举例：
现在的page_demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录。如下图：
从这个图中我们需要注意这么几点：
现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是112，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；槽0中的值是99，代表最小记录的地址偏移量。
注意最小和最大记录的头信息中的n_owned属性
最小记录的n_owned值为1，这就代表着以最小记录结尾的这个分组中只有1条记录，也就是最小记录本身。
最大记录的n_owned值为5，这就代表着以最大记录结尾的这个分组中只有5条记录，包括最大记录本身还有我们自己插入的4条记录。
用箭头指向的方式替代数字，这样更易于我们理解，修改后如下
页目录分组的个数如果确定？
为什么最小记录的n_owned值为1，而最大记录的n_owned值为5呢？
InnoDB规定：对于最小记录所在的分组只能有1条记录，最大记录所在的分组拥有的记录条数只能在1~8条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间。
分组是按照下边的步骤进行的：
初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个。
在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。
页目录结构下如何快速查找记录？
# 比方说我们想找主键值为6的记录，过程是这样的：
1. 计算中间槽的位置:(O+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 >6，所以设置high=2，low保持不变。
2. 重新计算中间槽的位置:(O+2)/2=1，所以查看槽1对应的主键值为4，又因为4<6，所以设置low=1，high保持不变。
3. 因为high - low的值为1，所以确定主键值为6的记录在槽2对应的组中。此刻我们需要找到槽2中主键值最小的那条记录，然后沿着单向链表遍历槽2中的记录。
但是我们前边又说过，每个槽对应的记录都是该组中主键值最大的记录，这里槽2对应的记录是主键值为8的记录，怎么定位一个组中最小的记录呢?别忘了各个槽都是挨着的，我们可以很轻易的拿到槽1对应的记录(主键值为4），该条记录的下一条记录就是槽2中主键值最小的记录，该记录的主键值为5。所以我们可以从这条主键值为5的记录出发，遍历槽2中的各条记录，直到找到主键值为6的那条记录即可。
由于一个组中包含的记录条数只能是1~8条，所以遍历一个组中的记录的代价是很小的。
小结：
在一个数据页中查找指定主键值的记录的过程分为两步：
通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
通过记录的next_record属性遍历该槽所在的组中的各个记录。
