MySQL InnoDB索引那点事儿( 二 ) _MySQL

未分配空间(Free Space)：指页面未使用的存储空间，随着页面不断使用，未分配空间将会越来越小。当新插入一条记录时，首先尝试从自由空间链表中获得合适的存储位置（空间足够），如果没有满足的，就会在未分配空间中申请。

Slot区：也称为Page Directory，页中某些记录的相对位置，用于提升查询效率。slot是一些页面有效记录的指针，每个slot占两个字节，存储了记录相对页面首地址的偏移。如果页面有n条有效记录，那么slot的数量就在n/8+2~n/4+2之间，它是记录页面有序和二分查找的关键。

页尾(Page Tailer)：页面最后部分，占8个字节，主要存储页面的校验信息。

上面提到，页头里包含了唯一id，页的左右兄弟页面指针，从而可以将页抽象为如下结构：

文章插图
【MySQL InnoDB索引那点事儿】
Page的头部保存了两个指针，分别指向前一个Page和后一个Page，根据这两个指针我们很容易想象出Page链接起来就是一个双向链表的结构。
InnoDB的行数据和索引的存储都位于User Records，存在4种不同的Record，它们分别是：

主键索引树非叶节点
主键索引树叶子节点
辅助键索引树非叶节点
辅助键索引树叶子节点

这4种节点的Record格式有一些差异，但是它们都存储着Next指针指向下一个Record 。User Record在Page内以单链表的形式存在，最初数据是按照插入的先后顺序排列的，但是随着新数据的插入和旧数据的删除，数据物理顺序会变得混乱，但他们依然保持着逻辑上的先后顺序。

文章插图

将该结构扩展到多个页就有如下形式：

文章插图

根据最大最小虚记录将多个页内记录的顺序连接起来。
2.3 页内查询前面提到User Records中的记录是以单链表的形式存在，这样在插入一条记录时，只要修改前后两条记录的指针就行，这样就可以避免记录的移动同时保证了有序性。但是，带来的问题是，链表是无法在对数时间内使用二分查找，这样的设计会导致查询效率低下。为了高效地在一个页中查找指定的一条记录，InnoDB使用Page Directory提供了解决方案。
InnoDB会将一个页中的所有记录划分成若干个组，每组4-8个记录。将每个组最后一个记录相对于第一个记录的地址偏移量（可以定位到真实数据记录）提取出来存放在页中一个叫做Page Directory的数组中，数组中的元素就是这些地址偏移量，也称为槽(slot) 。

文章插图

所以在一个页中根据主键查找记录是很快的，步骤为：

二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
通过next_record属性遍历单链表找到记录

对于插入操作，首先通过查询的方式确定插入的位置，在自由空间链表或未分配空间中获得空间并写记录内容，slot所指向的链高度加1，同时维护好原链表的关系。
插入记录后，如果Slot支链高度超过8，那么就将该支链拆分为两个子链，同时多申请一个slot（平移此slot及其后面的空间）。
3. 索引结构MySql提供了两种索引存储方式，一种叫做聚簇索引，一种叫做非聚簇索引。
3.1. 聚簇索引行数据和主键B+树存储在一起，辅助键B+树只存储辅助键和主键，主键和非主键B+树几乎是两种类型的树。InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上。
考虑如下的数据：

文章插图

其中Id作为主索引，Name作为辅助索引，则聚集索引的结构如下：

文章插图

当通过主键索引查找数据时，会连带返回对应的记录。当通过辅助键查找数据时，根据索引找到叶子节点中的主键值，根据主键值再到聚簇索引中得到完整的一行记录，该行为也即我们常说的回表。需要说明一点的是，对于联合主键，当存在辅助索引时，辅助索引也会保留联合主键的多个字段，从而影响到索引文件的大小。
下面以开头的B+树为例，再结合Page结构，展示其内部组织方式（只展示其中一部分）：