InnoDB的表格空间-Part1(区、段、区的分类、段的结构)

透过前面的内容大家知道表格空间是一个抽象的概念，对系统表格空间来说，对应着档案系统中一个或多个档案;对独立表格空间来说，对应着档案系统中一个名为(表名.ibd)的实际档案。大家可以把表格空间想成一个池子，里面有许多页面，当要为表插入一笔纪录时，就要从池子捞出一个对应页面把资料写进去。

区

由於表格空间内的页面太多，为了方便管理，Innodb工程师提出了区(extent)的概念，连续64个页就是一个区，一页通常为16kb，也就是说占用约1mb。
无论是系统表格空间还是独立表格空间，都可看成是由许多连续的区组成，每256个区(256mb)划分成一组。

第一组就是(extent0,extent1...extent255)
第二组就是(extent256,extent257...extent511)
第三组就是(extent512,extent513...extent767)
而第一个组最开始三页的类型是固定的，也就是说extent0的前三页如下(其余没有唷exten1-exten266)：

1. FSP_HDR：这页用来登记整个表格空间的一些整体属性及本组所有区的属性。值得注意的是整个表格空间只有一个FSP_HDR页。
2. IBUF_BITNAP：这用来储存关於Change Buffer的一些资料(晚点会再说明)。
3. INODE：这用来储存许多称为INODE Entry的资料结构(晚点会再说明)。

其余各组最开始二页的类型是固定的，也就是说extent256及extent512的前两页如下：

1. XDES：全名是entent decriptor。用来登记本组256个区的属性。
2. IBUF_BITNAP：前面提到，不赘述。

之所以会提出区的概念还有一个原因，是因为如果双向串列中两页的物理位置不连续，对传统机械硬碟来说，需要重新定位磁头位置，也就是会产生随机I/O，这样会影响磁碟的性能，所以我们应尽量让双向串列中两页的物理位置也相邻，所以才引入了区的概念，一个区就是在物理位置上连续64个页(区里面的页号都是连续的)，当表中资料很大的时候，有时是直接按照区为单位进行分配，甚至一次性分配多个连续的区，虽然可能会造成一些空间浪费(资料不足以填满整个区)，但是就性能角度而言，可以消除很多随机I/O，还是较好的。

段

我们在使用B+树执行查询时只扫描叶子节点的纪录，所以Innodb的工程师对B+树的叶子节点(使用者纪录)和非叶子节点(目录项纪录)进行了区别对待，避免所有节点页面都放到区中，影响了效能。区别对待就是叶子节点有自己的区，非叶子节点也有自己的区，存放叶子节点的区的集合就算是一个段(segment)，存放非叶子节点的区的集合也算是一个段(segment)。也就是说一个索引会生成两个段：一个叶子节点段、一个非叶子节点段。

预设情况下，一个使用Innodb储存引擎的表只有一个聚簇索引，一个索引会生成两个段。而段是以区为单位申请储存空间的，一个区预设占用1MB储存空间。所以，预设情况下一个只存放了几笔纪录的小表也需要2MB的储存空间吗？以後每增加一个索引就要多申请2MB的储存空间吗？
这对储存纪录较少的表来说简直是天大的浪费...

症结点在於目前介绍的区都是非常纯粹的，一个区被整个分配到某一个段，或说区中的所有页面都是为了储存同一个段的资料而存在的，即使段的资料填不满区中所有的页面(剩下的页面也不能挪作他用)。

考量到这个情况(以完整的区为单位分配给某个段，对资料量较小的表来说太浪费了)
因此提出了碎片区(fragment)的概念，也就是在一个碎片区中，并不是所有的页要在同一段(可分属不同的段)。

碎片区直属於表格空间，并不属於任何一段。
所以为段分配储存空间的策略为，刚开始在表中插入资料时，段是先从某个碎片区以单一页面为单位来分配储存空间，当段已经占用了32个碎片区页面之後，才会以完整的区为单位来分配储存空间(原先占用的碎片区页面并不会复制到新申请的完整区中)。
所以段不能仅定义为某些区的集合，而是某些零碎页面及完整区的集合。

区的分类

我们知道表格空间是有许多个区组成的。分成以下4种类型

• 空闲的区(FREE)：顾名思义就是闲置的区。
• 有剩余空闲页面的碎片区(FREE_FRAG)：表示碎片区中还有可被分配的空闲页面。
• 没有空闲页面的碎片区(FULL_FRAG)：表示该碎片区中所有页面都已分配。
• 附属於某个段的区(FSEG)：Innodb另外定义一些特殊用途的段，由於这些段的资料很大，使用区作为基本分配单位。
  再次提醒：处於FREE、FREE_FRAG、FULL_FRAG这三种状态的区都是独立的，是直属於表格空间，而FSEG的区是属於某个段的。

为了方便管理这些区，设计Innodb的工程师设计了一个称为XDES Entry(Extent Descriptor Entry)的结构。每区对应一个XDES Entry结构，这个结构纪录了对应区的一些属性。
XDES Entry结构有40位元组，大致分为4个部分，各个部分的含义如下：

1. Segment ID(8位元组)：每一个段有一个唯一的编号，用ID表示。Segment ID栏位表示的就是该区所在的段，前提是该区已经分配给某个段，否则值没有任何意义。

2. List Node(12位元组)：这部分可将许多个XDES Entry结构串联成一个链结串列。包含了Pre Node Page Number和Pre Node Offset的组合(指向前一个XDES Entry的指标)以及Next Node Page Number和Next Node Offset的组合(指向後一个XDES Entry的指标)。

3. State(4位元组)：区的状态，共4种(FREE、FREE_FRAG、FULL_FRAG、FSEG)

4. Page State Bitmap(16位元组)：16位元组也就是128位元。一个区预设有64页，而这128个位元划分为64个部分，每部分有2位元，对应其中一页。比如Page State Bitmap的第1位元和第2位元对应着区中的第1页，Page State Bitmap的第3元和第4位元对应着区中的第2页...以此类推。这2个位元中的第1个位元表示对应的页是否为空闲的，第2位元还没有用到。

XDES Entry链结串列
到现在为止我们学习了许多概念 - 区、段、碎片区、附属於段的区、XDES Entry结构。
其实都是为了减少硬碟定位磁头产生的随机I/O，然後又不至於太浪费表的空间。
我们知道，在表中插入资料本质上就是在各个索引的叶子节点段、非叶子节点段插入资料。
我们也知道不同区有不同的状态。
现在再更清楚的来看看向某个段插入资料，申请新页面的过程。
当段中资料较少时，首先会查看表格空间中是否有状态为FREE_FRAG的区(也就是寻找还有空闲页面的区)，如果有，就从该区取一零散页把资料插进去，否则就到表格空间申请一个状态为FREE的区(空闲的区)，把该区的状态变更为FREE_FRAG，然後从该新申请的区取一零散页把资料插进去。
之後，在不同的段使用零散页时都从该区取，直到该区没有空闲页面，再把该区的状态变成FULL_FRAG。

现在的问题是我们怎麽知道表格空间中那些区的状态是FREE，那些区的状态是FREE_FRAG，那些区的状态是FULL_FRAG呢？
要知道表格空间是可以不断增大的，当增长到GB等级的时候，区的数量也就上千了，我们总不能每次都历遍全部的区吧...
这个时候就是XDES Entry中的List Node部分发挥奇效的时候了。
我们可以透过List Node指标做以下三件事

1. 把状态FREE的区对应的XDES Entry结构链结起来形成一个FREE链结串列
2. 把状态FREE_FRAG的区对应的XDES Entry结构链结起来形成一个FREE_FRAG链结串列
3. 把状态FULL_FRAG的区对应的XDES Entry结构链结起来形成一个FULL_FRAG链结串列

这样一来每当想找一个FREE_FRAG状态的区时，直接把FREE_FRAG链结串列的头点拿出来，从这节点对应的区中取一些零散页来插入资料。当这节点没有空闲页时，就修改它的state栏位为FULL_FRAG，并将其移至FULL_FRAG链结串列。同理，如果FREE_FRAG链结串列中一个节点都没有了，那就要跟FREE链结串列取一个节点移动到FREE_FRAG链结串列，并修改该节点的state栏位为FREE_FRAG，然後再从该节点对应的区取得零散页即可。
当段中的资料已占满32个零散页後，就直接申请完整的区来插入资料。

再来我们要怎麽快速知道那些区属於那些段呢？再历遍各个XDES Entry结构？这样实在是太慢了...
原先的想法是根据段号(SegmentID)来建立链结串列。有多少个段就建多少个链结串列？但这样有点问题
因为一个段可以有好多个区，有的区是完全空闲的，有的区是还有空闲页可以使用，有的区则是没有空闲页可以使用。
所以有必要继续细分，工程师为每个段中的区对应的XDES Entry结构建立了三种链结串列。

1. FREE链结串列。同一个段中，所有页面都是空闲页面的区对应的XDES Entry结构会被加入到这个链结串列(附属於某个段的链结串列)中。注意，这与直属於表格空间的FREE链结串列是不同的东西
2. NOT_FULL链结串列。同一个段中，仍有空闲页面的区对应的XDES Entry结构会被加入到这个链结串列
3. FULL链结串列。同一个段中，已经空闲页面的区对应的XDES Entry结构会被加入到这个链结串列

再强调一遍，每一个索引对应两个段，每个段都会维护上述3个链结串列。
举个例子

create table t (
    c1 int not null auto_increment,
    c2 varchar(100),
    c3 varchar(100),
    primary key (c1),
    key idx_c2 (c2)
)engine=InnoDB;

表t共有两个索引：一个聚簇索引和一个二级索引idx_c2。所以这个表共有4个段(1个索引2个段)，每段都会维护上述3个链结串列，总共是12个链结串列。再加上前文说过的直属於表格空间的3个链结串列，整个独立表格空间共需要维护15个链结串列

链结串列基节点
那我们到底要怎麽找到某个链结串列的头节点或尾节点在表格空间中的位置呢？
於是工程师设计了一个名叫List Base Node，这个结构包含了键结串列的头节点和尾节点的指标以及这个链结串列中包含了多少个节点的资讯。
前面介绍的每个链结串列都对应这麽一个List Base Node结构，如下：

• List Length 表明该链结串列中一共有多少个节点
• First Node Page Number和First Node Offset 表明该链结串列的头节点在表格空间中的位置
• Last Node Page Number和Last Node Offset 表明该链结串列的尾节点在表格空间中的位置

链结串列小结
综上述所说，表格空间是有许多个区组成的，每区对应一个XDES Entry结构。
直属於表格空间的区对应的XDES Entry结构可分成FREE链结串列、FREE_FRAG链结串列、FULL_FRAG三个链结串列。每个段可以有很多区，每的段中的区对应的XDES Entry结构可分成FREE链结串列、NOT_FULL链结串列、FULL三个链结串列。每个链结串列都对应一个List Base Node结构，这个结构包含了键结串列的头节点和尾节点的指标以及这个链结串列中包含了多少个节点的资讯。

段的结构

我们已经知道段其实不对应表格空间中某一连续物理区域，而是一个逻辑上的概念，由许多零散的页面及完整的区组成。
像每个区对应的XDES Entry结构来纪录区属性一样
每个段有对应的INODE Entry结构来纪录段属性
结构如下：

1. Segment ID：INODE Entry结构对应的段的编号，用ID表示。
2. NOT_FULL_N_USED：在NOT_FULL链结串列使用了多少页面。
3. 3个List Base Node：分别为段的FREE链结串列、NOT_FULL链结串列、FULL三个链结串列定义了List Base Node，这样当想寻找某个段的某个链结串列的头和尾节点时，可以直接利用这个部分。
4. Magic Number：标记INODE Entry是否已经初始化。如果这数字是97937874（没有特殊含义，纯粹人家规定）表示已经初始化，否则没有。
5. Fragment Array Entry：对应一个零散的页面，有4个位元组，表示零散页面的页号。

--take a break--