InnoDB 记录存储结构

mysql——innodb（学习笔记）
这是一条记录以Cpmpact形式保存时候的存储结构。

变长字段长度列表：类似varchar，会存储在这里面，并以倒叙的顺序。
NULL值列表：某些列存储的是null值，则这个列表会存储
记录头信息：

heap_no：表示在页中的位置，从0开始，但是普通记录的heap_no 2开始，其中 0是最小记录，1是最大记录。
record_type：
2表示最小记录，就是heap_no 是0的，同时数据表示的是infimum。
3表示最大记录，就是heap_no是1的，同时数据表示的是supremum。
next_record：这个指向的就是向下一条记录，以链式的方式存储。

记录头信息：

行溢出

因为一页的大小被限制到16KB（16384字节），但是一个字段的长度不能超过65535字节。所以这里会产生一个行溢出的问题，所以里面处理的方式，在不同格式下会有些差异。大体上就是将超出的部分放在别的页里面。原本的列里面保存的是别的页上面的地址。

InnoDB 数据页结构

mysql——innodb（学习笔记）
此处Infimum和supremum和记录头信息中的heap_no =0，1 有所关系。
heap_no = 0 ，则这条记录是独立的一条，并不存储任何的数据，仅仅是标记着 Infimum，
supremum同样是这样的结构。

新记录的插入，会从空闲空间分配空间出去。

页目录

一页中数据可能有很多条，如果没有其他的措施，对数据进行查询的话，只有根据记录上的记录头信息里面的next_record信息查询下一条。这样个时间复杂度可能需要o(N)，但是对庞大数据库来说这种设计肯定是太繁重了。
所以采用空间换时间的方式。

显示对多条数据进行分组
每个分组中的最后一条记录的地址会保存在Page Directory中。

这中设计的目的可以使用二分法，进行查询时间复杂度是o(logN)
mysql——innodb（学习笔记）
现在就是图中的n_owned的意义，用于记录的分组，并用于分组。

Page Header

表示页里的一些状态信息，占固定的56个字节。
mysql——innodb（学习笔记）
每页会以双向链表的方式链接。

File Header

表示文件头，占固定的38字节。

MySQL 的索引

mysql——innodb（学习笔记）

一页的数据量是16KB，但是一张表中不仅仅只有一页的数据。所以会有上面这个每页之间以双向链表的形式。
对一页中对数据，可以根据Page Directory来二分查询。

但是跨页查找数据的话，就需要额外的空间来换取时间的高效。所以会对每页建立目录项。
他的key 就是该页最小的主键值
对应的值就是每页的页码。
mysql——innodb（学习笔记）
目录项存储的跟普通的记录没有区别，叶子节点他们底层的数据保存的是真实的数据，但是目录项保存的是对应的页码，但是目录项的页同样有Page Directory 可以通过二分法快速查找。

这就是innoDB里面的B+树存储结构。