①. 页的概述、大小

• ①. 数据库的存储结构：页

1. 索引结构给我们提供了高效的索引方式,不过索引信息以及数据记录都是保存在文件上的,确切来说是存储在页结构中。另一方面,索引是在存储引擎中实现的,MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同的存储引擎中存放的格式一般是不同的,甚至有的存储引擎Memory都不用磁盘来存储数据
2. 由于InnoDB是MySQL的默认存储引擎,所以本章节讲解InnoDB存储引擎的数据存储结构

• ②. 磁盘与内存交互的基本单位:页

1. InnoDB将数据划分为若干个页,InnoDB中页的默认大小为16KB
2. 以页作为磁盘和内存之间交互的基本单位,也就是一次最少从磁盘中读取16KB的内容到内存中,一次最少把16KB的内容刷新到磁盘中
3. 在数据库中,不论读一行,还是读多行,都是将这些行所在的页进行加载。也就是说数据库管理存储空间的基本单位是页,数据库I/O操作的最小单位也是页。一个页中可以存储多个行记录
   注意:记录是按照行来储存的,但是数据库的读取并不以行为单位,否则一次读取(也就是一次I/O操作),只能处理一行数据,效率会非常的低

• ③. 页结构概述

1. 页a、页b、页c,这些页可以不在物理结构上相连,只要通过双向链表相关联即可
2. 每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表,每个数据页都会为存储在它里边的记录生成一个页目录
3. 在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽
   

• ④. 页的大小
  不同数据库管理系统的页大小不同,MySQL的InnoDB存储引擎中,默认的页大小是16KB
  SQL Server中页的大小为8kb,而在Oracle中我们用术语"块"来代表页,Oracke支持的块大小为2kb、4kb、8kb、16kb、32kb、64kb

mysql> show variables like '%innodb_page_size%';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+

• ⑤. 页的上层结构,在数据库中还存在着区、段、和表空间的概念

1. 区(Extent)是比页大一级的存储结构,在InnoDB存储引擎中,一个区会分配64个连续的页。因为InnoDB中的页大小默认是16KB,所以一个区的大小是64 * 16KB = 1MB
2. 段(Segment)由一个或多个区组成,区在文件系统是一个连续分配的空间(在InnoDB中是连续的64个页),不过在段中不要求区与区之间是相邻的。段是数据库中分配单位,不同类型数据库对象以不同的段形式存在。当我们创建数据表、索引的时候,就会响应创建对应的段,比如创建一张表时会创建一个表段,创建一个索引时会创建一个索引段
3. 表空间(Tablespace)是一个逻辑容器,表空间储存的对象是段,在一个表空间中可以有一个或多个段,但是一个段只能属于一个表空间。数据库由一个或多个表空间组成,表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等
   

②. 页的内部结构

• ①. 页按照类型划分,常见的有数据页(保存B+树节点)、系统页、Undo页和事务数据页等。数据页是我们最常使用的页,页结构示意图如下:
  
• ②. 数据页16KB大小的存储空间被划分为七个部分,分别是文件头、页头、最大最小记录、用户记录、空闲空间、页目录和文件尾,如下图所示

③. 第一部分 - 文件头

• ①. File Header:描述各种页的通用信息。比如页的编号、其上一页、下一页是谁等、大小为38字节

• ②. File Header文件头部具体构成
  

• ③. FIL_PAGE_OFFSET:每一个页都有一个单独的页号,就跟你的身份证号码一样,InnoDB通过页号可以唯一定位一个页

• ④. FIL_PAGE_TYPE:代表当前页的类型
  

• ⑤. FIL_PAGE_PREV和FIL_PAGE_NEXT
  InnoDB都是以页为单位存放数据的,如果数据分散到多个不连续的页中存储的话需要把这些页关联起来,FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了,保证这些页之间不需要是物理上的连续,而是逻辑上的连续
  

• ⑥. FIL_PAGE_SPACE_OR_CHKSUM:代表当前页面的校验和checksum

1. 文件头部和文件尾部都有属性：FIL_PAGE_SPACE_OR_CHKSUM
2. 什么是校验和？对于一个很长的字节串来说,我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串,这个比较短的值就称为校验和
3. 在比较两个很长的字节串之前,先比较这两个长字节串的校验和,如果校验和都不一样,则两个长字节串肯定是不同的,所以省去了直接比较两个比较长的字节串的时间损耗

• ⑦. 校验和的作用

1. InnoDB存储引擎以页为单位把数据加载到内存中处理,如果该页中的数据在内存中被修改了,那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候断电了,造成了该页传输的不完整
2. 为了检测一个页是否完整也就是在同步的时候有没有发生只同步一半的尴尬情况,这时可以通过文件尾的校验和checksum值与文件头的校验和做比对,如果两个值不相等则证明页的传输有问题,需要重新进行传输,否则认为页的传输已经完成

• ⑧. 校验和举例子

1. 每当一个页面在内存中修改了,在同步之前就要把它的校验和算出来,因为File Header在页面的前边,所以校验和会被首先同步到磁盘,当完全写完时,校验和也会被写到页的尾部,如果完全同步成功,则页的首部和尾部的校验和应该是一致的
2. 如果写了一半儿断电了,那么在File Header中的校验和就代表着已经修改过的页,而在File Trailer中的校验和代表着原先的页,二者不同则意味着同步中间出了错。这里,校验方式就是采用 Hash 算法进行校验

• ⑨. FIL_PAGE_LSN:页面被最后修改时对应的日志序列位置英文名是：Log Sequence Number

④. 第一部分 - 文件尾

• ①. 大小8字节

1. 前4个字节代表页的校验和：这个部分是和File Header中的校验和相对应的
2. 后4个字节代表页面被最后修改时对应的日志序列位置LSN:这个部分也是为了校验页的完整性的,如果首部和尾部的LSN值校验不成功的话,就说明同步过程出现了问题

• ②. 文件头部和文件尾部都有属性:FIL_PAGE_SPACE_OR_CHKSUM

⑤. 第二部分 - 空闲、用户记录、最大最小

• ①. 页的主要作用是存储记录，所以 “最大和最小记录” 和 “用户记录” 部分占了页结构的主要空间
  
• ②. Free Space (空闲空间)
  我们自己存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了

• ③. User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表

• ④. Infimum + Supremum（最小最大记录）
  InnoDB规定的最小记录与最大记录这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的，如图所示
  
  

⑥. 第三部分 - 页目录

• ①. 为什么需要页目录？
  在页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率

• ②. 需求：根据主键值查找页中的某条记录，如何实现快速查找呢？

SELECT * FROM page_demo WHERE c1 = 3;

方式1：顺序查找
从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到（或者找不到），在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增(如果一个页中存储了非常多的记录，这么查找性能很差)
方式2：使用页目录，二分法查找

1. 将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录。
2. 第1组，也就是最小记录所在的分组只有1个记录；
   最后一组，就是最大记录所在的分组，会有1-8条记录；
   其余的组记录数量在4-8条之间
   这样做的好处是，除了第1组（最小记录所在组）以外，其余组的记录数会尽量平分
3. 在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_owned字段。
4. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录
   

• ③. 现在的page_demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录。如下图

1. 现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是112，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；槽0中的值是99，代表最小记录的地址偏移量
2. 注意最小和最大记录的头信息中的n_owned属性
   最小记录的n_owned值为1，这就代表着以最小记录结尾的这个分组中只有1条记录，也就是最小记录本身
   最大记录的n_owned值为5，这就代表着以最大记录结尾的这个分组中只有5条记录，包括最大记录本身还有我们自己插入的4条记录

• ④. 在一个数据页中查找指定主键值的记录的过程分为两步(非常重要)

1. 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录
2. 通过记录的next_record属性遍历该槽所在的组中的各个记录

⑦. 第三部分 - 页面头部

• ①. 为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫Page Header的部分，这个部分占用固定的56个字节，专门存储各种状态信息
  

• ②. PAGE_DIRECTION:假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就PAGE_DIRECTION

• ③. PAGE_N_DIRECTION:假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一个方向插入记录的条数记下来，这个条数就用PAGE_N_DIRECTION这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计

⑧. 从数据页角度看B+树

• ①. 一颗B+树按照节点类型可以分成两部分

1. 叶子节点,B+树最底层的节点,节点的高度为0,储存行记录
2. 非叶子节点,节点的高度大于0,储存索引键和页面指针,并不储存行记录本身
   

• ②. B+树是如何进行记录检索的呢？
  从B+树的跟几点开始,逐层检索,在哪个目录项里面,进行定位到具体的页,将数据页加载到内存中,页目录中的槽(slot)采用二分查找的方式找到一个粗略的记录分组,找到最小的那条记录,通过next_record遍历查找记录

• ③. 普通索引和唯一索引在查询效率上有什么不同？
  唯一索引就是在普通索引上增加了约束性,也就是关键字唯一,找到了关键字就停止检索。而普通索引,可能会存在用户记录中的关键字相同的情况,根据页结构的原理,当我们读取一条记录的时候,不是单独将这条记录从磁盘中读出去,而是将这个记录所在的页加载到内存中进行读取。InnoDB储存引擎的页大小为16KB,在一个页中可能存储着上千条记录,因此在普通索引的字段上进行查找页就是在内存中多几次"判断下一条记录"的操作,对于CPU来说,这些操作所消耗的时间是可以忽略不计的。所以对一个索引字段进行检索,采用普通索引还是唯一索引在检索效率上基本上没差别

⑨. 区、段和表、碎片区

• ①. 为什么要有区？

1. B+树的每一层中的页都会形成一个双向链表，如果是以页为单位来分配存储空间的话，双向链表相邻的两个页之间的物理位置可能离的非常远，如果需要范围查询的话只需要定位最左边和最右边的记录，沿着双向链表一直扫描即可，而如果两个页之间的物理位置隔得非常远，就是所谓的随机I/O，这是非常慢的，所以应该尽量让链表中相邻页的物理位置页相邻，这样进行范围查询时才可以使用所谓的顺序I/O
2. 这就引入了区的概念，一个区就是在物理位置上连续的64个页，因为InnoDB的页大小默认是16KB，所以一个区的大小是1MB。在表中数据量大的时候，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照区为单位分配，甚至在表中数据特别多的时候，可以一次性分配多个连续的区。虽然可能造成一点点空间的浪费，但是从性能角度看，可以消除很多随机I/O