MySQL中InnoDB页结构和索引的存储

局部性原理：OS虽然IO操作只读取一部分数据，但是OS每次IO操作取值都是以页为单位，一页=4kb。

1.InnoDB数据页结构

页是InnoDB管理存储空间的基本单位：1页=16kb = 16384

查看数据库页的大小SQL：

show global status like ‘Innodb_page_size’;

一个InnoDB数据页的存储结构：

名称	占用空间大小	简单描述
文件头部	38	页的一些通用信息(Page指针，双向链表)
页面头部	56	数据页专有的一些信息
最大、最小记录	26	两个虚拟的行记录（select用）
用户记录(data)	不确定	实际存储的行记录内容(单链表)
空闲空间	不确定	页中尚未使用的空间
页面目录	不确定	页中的某些记录的相对位置（主键位置）
文件尾部	8	校验页是否完整

索引相关页面目录功能：数据库会根据主键ID进行排序分组(单链表遍历查询的优化)（B+树(所有data都在叶子节点上)，非叶子节点存储的就是主键+指针(页号)¹），在页目录中进行存储分组后的主键ID（一个ID范围）。如图所示：一个颜色代表一个组，查询ID=6，则判断6>5找到page为200的页(这个页存放的都是叶子节点)，然后再遍历单链表。

注意:由于刚刚是通过主键ID的索引是可以直接定位到该ID所在的page，如果没有走索引，则要通过中序遍历找到B+树的第一个叶子节点的页然后根据页中data数据形成的单链表挨个遍历比较。

**最大、最小记录和用户记录才是真正的行记录（数据）。**新建的页的时候，是没有用户记录，当有数据插入进来的时候，会在空闲空间中划分一部分空间，然后也就是有了用户记录。当所有的空闲空间使用完后，再有新的数据插入进来，就需要新建一个页了。

新建一页的过程：保证第一页的地址不改变，树的根节点不变

1. 先将第一页copy
2. 再创建第二页
3. 将原第一页改成目录页

2.行格式

建表会默认使用Dynamic行格式

1.Compact行格式

记录的额外信息：服务器为了描述这条记录而不得不额外添加的一些信息。

1. 变长字段长度列表：temp、e列中如果存的是 e和f，那么变长字段长度列表中存的是e,f该值占用的字节数（存储位置相反）。—>2字节

2. NULL值列表（记录对应的字段是不是为null）：如果这个字段为null 则存为1，不为null 则存为0。—>1字节

3. 记录头信息：固定5字节组成。

4. 记录的真实数据：除了自己定义的列数据外，还有是三个隐藏的列

   列名	是否必须	占用空间	描述
   db_row_id	否	6字节	行id，唯一标识一条记录
   db_trx_id	是	6字节	事务id
   db_roll_ptr	是	7字节	回滚指针

   一个表没有手动定义主键，则会选取一个Unique键作为主键，如果连Unique键都没有定义的话，则会默认添加一个db_row_id的隐藏列作为主键。所以db_row_id在没有定义主键和Unique键情况下才会存在。

   必须含有主键的原因：

   为了方便使用B+树建立聚簇索引，递增添加，可以防止，添加大的id后，再添加小的id，使得原先排序好的页面发生大面积修改。由此，不要使用特别长的字符串作为主键（eg：UUID）占用行数据大小还生成的UUID序列不一定是有序的

   添加行号sql：

   SELECT (@rownumber :=@rownumber + 1) as '行号',a,b,c,e from (SELECT * from t1) c,(SELECT @rownumber := 0) r;
   

   SELECT @rownumber := 0 声明了一个叫rownumber的变量并赋值为0 。再将 c,r两表关联即可。

如果表中没有变长字段，则变长字段长度列表不存在，且都定义为不能为空，则NULL值列表 也不存在。这样不经节省空间，还有利于sql查询时候，提升行计算位置。

2.行溢出数据

每行数据除去blobs类型的，最大长度为：65535**(ASCII编码时：当没有定义为不为null和varchar时，最多为65532；utf8(utf8mb4才是java中的0~4字节)为：21845，1个字符占 3个字节)**。由于1页存储为16kb(16384)，一页存不下，故会发生行溢出。

当行格式为Compact时在真实数据处存储一部分真实数据，并且记录下一页的存储地址。会采用压缩算法对页面进行压缩。

在Dynamic中，不会记录一部分真实数据，而是把所有的数据都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。

3.索引

1.聚簇索引（主键），特点：

1. 按主键值的大小进行记录和页的排序：

   • 数据页（叶子节点）里的记录是按照主键值从小到大排序的一个单向链表
   • 数据页（叶子节点）之间也是是按照主键值从小到大排序的一个双向链表
   • B+树种同一层的页目录也是按照主键值从小到大排序的一个双向链表

2. B+树的叶子节点存储的是完整的data，就是指这个记录中存储了所有列的值（包含隐藏列）

2.二级索引（复制索引）

聚簇索引只能在搜索条件是主键值才能发挥作用，因为B+树都是按照主键进行排序的。

二级索引与聚簇索引不同：

1. 按指定的索引列的值来进行排序
2. 叶子节点存储的不是完整的data，而是索引列+主键
3. 目录项纪录中不是主键+页号，而是索引列+页号
4. 在对二级索引进行查找数据时，需要根据主键值去聚簇索引中查找到主键ID，再在主键索引树种查找到对应的完整的data（回表）。

**覆盖索引：**也是二级索引

select  列1  from table where 列1 = '';

主要是select查询的列和where的查询条件所用到的列都是建立了索引，这样就不需要回表操作了。

3.联合索引

多个列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引

4.目录项纪录的唯一性

B+树的同一层的节点的目录项纪录除页号这个字段以外是唯一的，所以目录项纪录的内容为：

• 索引列的值
• 主键值
• 页号

5.B+树索引总结

1. 每个索引对应一棵B+树，data都存储在B+树的叶子节点，所有目录都存储在非叶子节点

2. InnoDB会主动为主键建立聚簇索引，聚簇索引的叶子节点包含完整的data（只能有一个聚簇索引）

3. 可以建多个二级索引(249)个，二级索引的叶子节点包含索引列()+主键

4. B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是data还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引，页面和记录先按照联合索引最左边的列排序，如果该列值相同，再按照联合索引后面的列排序。

5. 通过索引查找记录是从B+树的根节点开始，一层层向下搜索。由于每个页面都是按照索引列的值建立了页目录，所以在这些页面中的查找非常快。

6.索引总结

每个表只能有一个聚簇索引，因为一个表中的记录只能以一种物理顺序存放。但是，一个表可以有不止一个非聚簇索引。每个表最多可以建立249个非聚簇索引。非聚簇索引需要大量的硬盘空间和内存。虽然非聚簇索引可以提高从表中取数据的速度，但是它也会降低向表中插入和更新数据的速度。当改变了一个建立了非聚簇索引的表中的数据时，必须同时更新索引，这是一个很复杂的过程。

4.Page和索引结构的存储图

1. page和page之间是双向链表进行连接排序；

2. page中的数据data是单向链表进行连接排序；

3. 跨page（叶子节点）的遍历查询，通过page的next指针找到下一页，从该页的第一个data开始遍历；

4. 非叶子节点的page中存储的都是子节点中最小的ID和对应的页号

注意： Page和B+树节点之间并不是一一对应的关系 ，Page只是一个存储容器，符合OS中的IO操作进行数据管理。在逻辑上分开的B+树结构中的节点在MySQL中并不一定同时都存储在一个Page中。

---