MySQL数据库，详解索引原理(六)

⻚结构

mysql中页是innodb中存储数据的基本单位，也是mysql中管理数据的最⼩单位，和磁盘交互的时候都是以页来进⾏的，默认是16kb，mysql中采⽤b+树存储数据，页相当于b+树中的⼀个节点。

页的结构如下图：

每个Page都有通⽤的头和尾，但是中部的内容根据Page的类型不同⽽发⽣变化。Page的头部⾥有我们关⼼的⼀些数据，下图把Page的头部详细信息显⽰出来：

我们重点关注和数据组织结构相关的字段：Page的头部保存了两个指针，分别指向前⼀个Page和后⼀个Page，根据这两个指针我们很容易想象出Page链接起来就是⼀个双向链表的结构，如下图：

再看看Page的主体内容，我们主要关注⾏数据和索引的存储，他们都位于Page的User Records部分，User Records占据Page的⼤部分空间，User Records由⼀条⼀条的Record组成。在⼀个Page内部，单链表的头尾由固定内容的两条记录来表⽰，字符串形式的"In[imum"代表开头，"Supremum"代表结尾，这两个⽤来代表开头结尾的Record存储在System Records的，In[inum、Supremum和User Records组成了⼀个单向链表结构。最初数据是按照插⼊的先后顺序排列的，但是随着新数据的插⼊和旧数据的删除，数据物理顺序会变得混乱，但他们依然通过链表的⽅式保持着逻辑上的先后顺序，如下图：

把User Record的组织形式和若⼲Page组合起来，就看到了稍微完整的形式。innodb为了快速查找记录，在页中定义了⼀个称之为page directory的⽬录槽（slots）,每个槽位占⽤两个字节（⽤于保存指向记录的地址），page directory中的多个slot组成了⼀个有序数组（可⽤于⼆分法快速定位记录，向下看），⾏记录被Page Directory逻辑的分成了多个块，块与块之间是有序的，能够加速记录的查找，如下图：

看上图，每个⾏记录的都有⼀个nowned的区域（图中粉⾊区域），nowned标识所属的slot这个这个块有多少条数据，伪记录In[imum的nowned值总是1，记录Supremum的nowned的取值范围为[1,8]，其他⽤户记录nowned的取值范围[4,8]，并且只有每个块中最⼤的那条记录的nowned才会有值，其他的⽤户记录的n_owned为0。

数据检索过程

在page中查询数据的时候，先通过b+树中查询⽅法定位到数据所在的页，然后将页内整体加载到内存中，通过⼆分法在page directory中检索数据，缩⼩范围，⽐如需要检索7，通过⼆分法查找到7位于slot2和slot3所指向的记录中间，然后从slot3指向的记录5开始向后向后⼀个个找，可以找到记录7，如果⾥⾯没有7，⾛到slot2向的记录8结束。

n_owned范围控制在[4,8]内，能保证每个slot管辖的范围内数据量控制在[4,8]个，能够加速⽬标数据的查找，当有数据插⼊的时候，page directory为了控制每个slot对应块中记录的个数（[4,8]），此时page directory中会对slot的数量进⾏调整。

对page的结构总结⼀下

1. b+树中叶⼦页之间⽤双向链表连接的，能够实现范围查找

2. 页内部的记录之间是采⽤单向链表连接的，⽅便访问下⼀条记录3. 为了加快页内部记录的查询，对页内记录上加了个有序的稀疏索引，叫页⽬录

（page directory）整体上来说mysql中的索引⽤到了b+树，链表，⼆分法查找，做到了快速定位⽬标数据，快速范围查找。