1.2 InnoDB页结构

我们已经知道，<font><font color="#4669ea">记录</font><font><font color="#000000">在</font><font><font color="#4669ea">⻚</font><font><font color="#000000">中是按照</font><font><font color="#4669ea">主键值</font><font><font color="#4669ea">由小到大</font><font><font color="#000000">顺序串联成一个单链表放在</font><font color="#4669ea"> </font><font><font color="#4669ea">UserRecords</font><font color="#000000"> 部分</font><font color="#000000">的。<br><br><font>如果我们想根据主键值查找⻚中的某条记录该咋办?</font><br><font>最笨的办法: 从 Infimum记录(最小记录)开始，沿着链表一直往后找，总有一天会找到(或者找不到)。</font><br><font>在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了。</font><br><br><font>这个方法在⻚中存储的记录数量比较少时也没啥问题，但如果一个⻚中存储了非常多的记录，</font><font><b>遍历操作对性能来说还是有损耗的</b>，所以说遍历查找这是一个笨办法。</font><font color="#e74f4c">(时间复杂度很显然是 `O(n)`)<br></font></font></font></font></font></font></font></font></font></font>

<font color="#000000">设计InnoDB的大叔们自然不会用上面那种笨办法，他们从现实中的</font><b>书籍目录</b><font color="#000000">中找到了灵感。他们为页中的记录也制作了一个类似的目录。制作过程如下：</font><br><ul><li><font color="#000000">将所有正常的记录(包括页内的最大和最小记录，不包括标记为已删除的记录) 划分为几个</font><font color="#4669ea"><b>组</b> ；</font></li><li><font><font color="#4669ea">每个组的最后一条记录(也就是组内最大的那条记录)相当于“带头大哥”，组内其余的记录相当于“小弟”。</font><font><font color="#000000">“带头大哥”的记录头信息中的 </font><font><b><font color="#e855a4">n_owned</font><font color="#000000">&nbsp;</font></b><span style="font-size:inherit;"><font color="#000000">属性表示该组内共有几条记录；</font></span></font></font></font></li><li><font><font><font><font><font><font color="#000000">将每个组内</font><font><font color="#000000">最后一条记录(也就是 “带头大哥”)在页面中的地址偏移量(就是该条记录与页面中第0个字节之间的距离)单独提取出来并且还<font>按主键顺序存储到靠近⻚尾的地方，这个地方就是所谓的</font></font><font> <font><font color="#e855a4">Page Directory，也就是`</font><font color="#4669ea"><b>⻚目录</b>`</font><font><font color="#000000">。</font><font><font color="#000000">⻚目录<span style="font-size:inherit;">中的这些</span></font><font><font color="#000000">地址偏移量<span style="font-size:inherit;">被称为&nbsp;</span></font><b><font color="#4669ea">槽</font></b><font><font><span style="color:rgb(232, 85, 164); font-size:inherit;">(英文名:</span><b><font color="#4669ea">Slot</font></b><font><font><span style="font-size:inherit;"><font color="#e855a4">)</font><font color="#000000">，所以说，</font></span><b><font color="#000000">⻚目录其实就是由</font><font color="#4669ea">页内</font><font color="#000000">多个组中的</font><font color="#4669ea">带头大哥</font><font color="#000000">组成的</font></b><font><font><span style="font-size:inherit;">。</span></font></font></font></font></font></font></font></font></font></font></font></font></font></font></font></font></font></li></ul>

比方说现在的demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个<b>最小记录</b>，第二组中是<b>剩余的5条记录</b>，2个组就对应着两个槽，<font color="#4669ea">每个槽中存放着每个组中最大的那条记录在页面中的地址偏移量</font>:<br>

接着，我们一口气又往表中添加了12条记录，现在⻚里边就一共有18条记录了(包括最小和最大记录)，这些记录被分成了5个组: (图中只保留了用户记录头信息中的n_owned和next_record属性，也省略了各个记录之间的箭头!)<br>