2.3 第3部分：
Page Directory(页目录)
Page Directory(页目录)
对n_owned的解释
为什么需要页目录?
在页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。
需求:根据主键值查找页中的某条记录，如何实现快速查找呢?
SELECT * FROM page_demo WHERE c1 = 3;
方式1:顺序查找
从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到(（或者找不到)，在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增。
如果一个页中存储了非常多的记录，这么查找性能很差。
方式2:使用页目录，二分法查找
1.将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录。
2.第1组,也就是最小记录所在的分组只有1个记录;
最后一组，就是最大记录所在的分组，会有1-8条记录;
其余的组记录数量在4-8条之间。
这样做的好处是，除了第1组（最小记录所在组）以外，其余组的记录数会尽量平分。
3.在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_owned字段。
这就是删除操作5->4的原因
4.页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽(slot)，每个槽相当于指针指向了不同组的最后一个记录。
举例1：
举例2:
现在的page_demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录。如下图：
从这个图中我们需要注意这么几点:
现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是
112，代表最大记录的地址偏移量（就是从页面的O字节开始数，数112个字节);槽O中的值是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条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。
备注：
页目录结构下如何快速查找记录?
现在向page_demo表中添加更多的数据。如下:
INSERT INTO page_demo VALUES (5,500, 'zhou'), (6, 600, 'chen'), (7,700, 'deng'), (8,800, 'yang'), (9, 900, 'wang'), ( 10,1000, 'zhao'), (11,1100, 'qian'), (12,1200, 'feng'), (13,1300, 'tang'), (14,1400, 'ding'), (15,1500, 'jing'), (16,1600, 'quan');
添加了12条记录，现在页里一共有18条记录了（包括最小和最大记录），这些记录被分成了5个组，如图所示:
这里只保留了16条记录的记录头信息中的n_owned和next_record属性，省略了各个记录之间的箭头。
现在看怎么从这个页目录中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用二分法来进行快速查找。5个槽的编号分别是:0、1、2、3、4,所以初始情况下最低的槽就是low=0，最高的槽就是high=4。比方说我们想找主键值为6的记录，过程是这样的:
1.计算中间槽的位置:(O+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 >6，所以设置high=2，low保持不变。
2.重新计算中间槽的位置:(0+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条，所以遍历一个组中的记录的代价是很小的
小结:
在一个数据页中查找指定主键值的记录的过程分为两步:
1.通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
2.通过记录的next_record属性遍历该梏所在的组中的各个记录。
备注：
Page Header(页面头部)
为了能得到一个数据页中存储的记录的状态信息，比如本页中己经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫PageHeader的部分，这个部分占用固定的56个字节，专门存储各种状态信息。
备注
PAGE_DIRECTION
假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是PAGE_DIRECTION。
备注
PAGE_N_DIRECTION
假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一个方向插入记录的条数记下来，这个条数就用PAGE_N_DIRECTION这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。
备注
2.4 从数据页的角度看B+树
如何查询一棵B+树按照节点类型可以分成两部分:
- 叶子节点，B+树最底层的节点，节点的高度为0，存储行记录。
- 非叶子节点，节点的高度大于0，存储索引键和页面指针，并不存储行记录本身。
当我们从页结构来理解B+树的结构的时候，可以帮我们理解一些通过索引进行检索的原理:
1.B+树是如何进行记录检索的?
如果通过B+树的索引查询行记录，首先是从B+树的根开始，逐层检索，直到找到叶子节点，也就是找到对应的数据页为止，将数据页加载到内存中，页目录中的槽（slot)采用二分查找的方式先找到一个粗略的记录分组，然后再在分组中通过链表遍历的方式查找记录。
2.普通索引和唯一索引在查询效率上有什么不同?
我们创建索引的时候可以是普通索引，也可以是唯一索引，那么这两个索引在查询效率上有什么不同呢?
唯一索引就是在普通索引上增加了约束性，也就是关键字唯一，找到了关键字就停止检索。而普通索引，可能会存在用户记录中的关键字相同的情况，根据页结构的原理，当我们读取一条记录的时候，不是单独将这条记录从磁盘中读出去，而是将这个记录所在的页加载到内存中进行读取。InnoDB存储引擎的页大小为16KB，在一个页中可能存储着上千个记录，因此在普通索引的字段上进行查找也就是在内存中多几次“"判断下一条记录”的操作，对于CPU来说，这些操作所消耗的时间是可以忽略不计的。所以对一个索引字段进行检索，采用普通索引还是唯一索引在检索效率上基本上没有差别。
2022/8/1 22:15
3. InnoDB行格式（或记录格式）
我们平时的数据以行为单位来向表中插入数据，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB存储引擎设计了4种不同类型的行格式，分别是Compact、Redundant、Dynamic和Compressed行格式。
查看MySQL8的默认行格式:
mysql>SELECT @@innodb_default_row_format; +-----------------------------+ | @@innodb_default_row_format | +-----------------------------+ | dynamic | +-----------------------------+ 1 row in set (0.05 sec)
也可以使用如下语法查看具体表使用的行格式:
SHOW TABLE STATUS like '表名\G
备注
3.1 指定行格式的语法
在创建或修改表的语句中指定行格式:
CREATE TABLE表名(列的信息Row_FORMAT=行格式名称ALTER TABLE表名ROW_FORMAT=行格式名称
举例:
mysql> CREATE TABLE record_test _table ( col1 VARCHAR(8), col2 VARCHAR(8) NOT NULL, col3 CHAR(8), col4 VARCHAR(8) )CHARSET=ascii ROW_FORMAT=COMPACT; Query OK,0 rows affected (0.03 sec)
向表中插入两条记录: INSERT INTO record_test table(col1,col2,col3,col4) VALUES ('zhangsan', 'lis', 'wangwru' , 'songhk'), ('tong','chen', NULL, NULL);
备注
3.2 Conpact行格式
在MySQL 5.1版本中，默认设置为Compact行格式。一条完整的记录其实可以被分为记录的额外信息和记录的真实数据两大部分。
备注
① 变长字段长度列表
MySQL支持一些变长的数据类型，比如VARCHAR(M)、VARBINARY(M)、TEXT类型，BLOB类型，这些数据类型修饰列称为变长字段，变长字段中存储多少字节的数据不是固定的，所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。在Compact行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表。
注意:这里面存储的变长长度和字段顺序是反过来的。比如两个varchar字段在表结构的顺序是a(10)，b(15)。那么在变长字段长度列表中存储的长度顺序就是15，10，是反过来的。
以record_test_table表中的第一条记录举例:因为record_test_table表的col1、col2、col4列都是VARCHAR(8)类型的，所以这三个列的值的长度都需要保存在记录开头处，注意record_test_table表中的各个列都使用的是ascii字符集（每个字符只需要1个字节来进行编码）。
又因为这些长度值需要按照列的逆序存放，所以最后变长字段长度列表的字节串用十六进制表示的效果就是（各个字节之间实际上没有空格，用空格隔开只是方便理解）:
06 04 08
把这个字节串组成的变长字段长度列表填入上边的示意图中的效果就是:
备注
② NULL值列表
Compact行格式会把可以为NULL的列统一管理起来，存在一个标记为NULL值列表中。如果表中没有允许存储 NULL 的列，则 NULL值列表也不存在了。
为什么定义NULL值列表？
之所以要存储NULL是因为数据都是需要对齐的，如果没有标注出来NULL值的位置，就有可能在查询数据的时候出现混乱。如果使用一个特定的符号放到相应的数据位表示空置的话，虽然能达到效果，但是这样很浪费空间，所以直接就在行数据得头部开辟出一块空间专门用来记录该行数据哪些是非空数据，哪些是空数据，格式如下：
1.二进制位的值为1时，代表该列的值为NULL。
2.二进制位的值为0时，代表该列的值不为NULL。
例如：字段 a、b、c，其中a是主键，在某一行中存储的数依次是 a=1、b=null、c=2。那么Compact行格式中的NULL值列表中存储：01。第一个0表示c不为null，第二个1表示b是null。这里之所以没有a是因为数据库会自动跳过主键，因为主键肯定是非NULL且唯一的，在NULL值列表的数据中就会自动跳过主键。
record_test_table的两条记录的NULL值列表就如下：
第一条记录：
第二条记录：
备注
记录头信息在将页的内部结构，讲过了
跳转到记录的真实数据
③ 记录头信息（5字节）
记录头信息（5字节）
记录头信息（5字节)
mysql> CREATE TABLE page_demo( c1 INT, c2 INT, c3 VARCHAR(10000), RIMARY KEY (c1) )CHARSET=ascii ROW_FORMAT=Compact;Query oK, 0 rows affected (0.03 sec)
这个表中记录的行格式示意图:
这些记录头信息中各个属性如下：
简化后的行格式示意图：
插入数据;
INSERT INTO page_demo VALUES (1,100, 'song'), (2,200, 'tong'), (3,300,'tmi'), (4,400, 'lisi');
图示如下:
备注：
结合：
下面进行具体介绍以下几个掩码
delete_mask
delete_mask
删除掩码
这个属性标记着当前记录是否被册除,占用1个二进制位。
- 值为0:代表记录并没有被删除
- 值为1:代表记录被删除掉了
被删除的记录为什么还在页中存储呢?
你以为它删除了，可它还在真实的磁盘上。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后其他的记录在磁盘上需要重新排列，导致性能消耗。所以只是打一个删除标记而已，所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为可重用空间，之后如果有新记录插入到表中的话，可能把这些被刮除的记录占用的存储空间覆盖掉。
备注
min_rec_mask
min_rec_mask
B+树的每层非叶子节点中的最小记录都会添加该标记,min_rec_mask值为1。
我们自己插入的四条记录的min_rec_mask值都是0，意味着它们都不是B+树的非叶子节点中的最小记录。
目录项中的记录的最小，用来二分
只针对min_rec_mask掩码
备注
record_type
record_type
这个属性表示当前记录的类型，一共有4种类型的记录:
- o:表示普通记录
- 1:表示B+树非叶节点记录
- 2:表示最小记录
- 3:表示最大记录
从图中我们也可以看出来，我们自己插入的记录就是普通记录，它们的record_type值都是0，而最小记录和最大记录的record_type值分别为2和3。至于record_type为1的情况，我们在索引的数据结构章节讲过。
备注
heap_no
heap_no
这个属性表示当前记录在本页中的位置。
从图中可以看出来，我们插入的4条记录在本页中的位置分别是:2、3、4、5。
怎么不见heap_no值为0和1的记录呢?
MySQL会自动给每个页里加了两个记录，由于这两个记录并不是我们自己插入的，所以有时候也称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。最小记录和最大记录的heap_no值分别是0和1，也就是说它们的位置最靠前。
就像这样，只针对heap_no掩码
备注
现在，我们在回到lnfimum + Supremum(最小最大记录)
看完lnfimum + Supremum(最小最大记录)，我们继续讲记录头信息的剩余部分
n_owned
n_owned
页目录中每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_ownedl字段。
详情见page directory。
备注
next_record
next_record
记录头信息里该属性非常重要，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。
比如:第一条记录的next_record值为32，意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。
注意，下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。
而且规定Infimum记录（也就是最小记录）的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是
Supremum记录（也就是最大记录）。下图用箭头代替偏移量表示next_record。
备注
演示:删除操作删除操作：
从表中删除掉一条记录，这个链表也是会跟着变化:mysql> DELETE FROM page_demo WHERE c1 = 2;Query OK, 1 row affected (0.02 sec)
删掉第2条记录后的示意图就是:
