Mysql(独立表空间)数据的存储结构

在这之前你需要对索引的存储方式有一定的了解，这里我们只讲表空间的结构，不讲概念相关的东西。其次我们应该知道数据的存储结构的设计很大一部分原因是为了加速数据的查找和插入，也就是取数据和村数据。

1. 表空间结构

在图1和图2中，里面的extent是区的意思，我们知道Mysql是以页(一个页16KB)方式进行数据存储的，这里的区是页的集合，64去页组成一个区，一个区就是16KB*64=1MB大小。

知道了区之后，组就很好说了，256个区组成一个组(如图1)。另外需要提前说明的是图2中的extent0、extent256、extentn表示组开头的第一个区。

这里我们需要注意的重点是图2每个区右边箭头指向的方块，每个方块表示一个页。这里并没有将所有的页按照顺序画出来，只画出了我们关心的几个页类型。

首先是FSP_HDR，表空间中第一个组中的第一个区中的第一个页是FSP_HDR类型的页。在FSP_HDR页后面是IBUF_BITMAP类型的页(并没有画出来，因为我们不讲他)，紧跟其后的是一个INODE类型的页，到此我们就引出了我们关键的两个类型的页了，第一个区后面的61个页我们先不管。

然后是表空间中第一个组后面的其他组中每个组开头的第一个页是XDES类型的页。我们可以暂且将XDES与FSP_HDR看作是一个类型的页(他们都存储了XDES Entry，但是FSP_HDR存储了一些表空间相关的属性)，也就是说每个组的开头都有一个XDES类型的页。这样我们就可以很快定位到表空间中所有的XDES页了，只需要知道是哪个表空间，然后位移固定的长度，就可以找到所有的XDES页了，因为每个组的大小是固定的。

 _____________                ____________        _______________
|   extent 0  |              |            | ---> | FSP_HDR(16KB) |
|-------------|              |            |       ---------------
|     ...     |              |  extent 0  |       _______________
|-------------|              |            | ---> |  INODE(16KB)  |
|  extent 255 |              |            |       ---------------
|-------------|              |------------|       _______________
|  extent 256 |              |            | ---> |  XDES(16KB)   |
|-------------|              |            |       ---------------
|     ...     |              | extent 256 |
|-------------|              |            |
|  extent 511 |              |------------|       _______________
|     ...     |              | extent n   | ---> |  XDES(16KB)   |
 -------------                ------------        ---------------
     图1(组结构)                         图2(区)

2. XDES类型的页

XDES页的结果如下图所示，File Header和File Trailer是通用的页结构，重点是里面存的记录，存储的是一个一个的XDES Entry，一个XDES Entry对应一个区，每个组中有一个XDES页，而一个XDES Entry对应一个区。页中有256条记录，对应着组中的256个区。并且每个XDES页的位置是固定的，因为每个区的大小是固定的，所以我们可以快速定位到每个组的第一个区的开头位置，也就可以快速定位到XDES页了。

        _________________________________
       |           File Header           |
       |---------------------------------|  
       |                                 |
       |---------------------------------|
       |          XDES Entry 0           |
       |          XDES Entry 1           |
       |          XDES Entry 2           |
       |             ...                 |
       |          XDES Entry 255         |
       |---------------------------------|
       |          Emptry Space           |
       |---------------------------------|
       |          File Trailer           |
        ---------------------------------

2.1 XDES Entry的结构

这里先说段，为了减少随机IO，在进行数据存放时，Mysql希望将一类数据尽量存放在一起。我们的一条一条数据是以B+树的方式存储的，我没在进行数据查找的时候，如果是索引查找，那就会从索引的根节点开始向下找，B+数种的节点分为叶子结点和非叶子结点，如果是索引查找的话，我们是先从非叶子结点查找，然后找到对应的叶子结点，如果是全部扫描的话，我们就需要直接从叶子结点的第一个节点开始查找。所以为了较少随机IO，我们索引中页面链表(B+树中同一层的节点也就是页是通过链表的方式连接的)中相邻页的的物理位置尽量相连。段就可以实现将叶子结点和非叶子结点分开存储，因为段中存储的是一个或多个区，我们的一个索引或生成两个段进行存储，一个存所有叶子结点，另一个存所有非叶子节点。

  • Segment ID 表示对应的区所属的段的ID，只有该区已经分配给某个段，这个字段的值才有意义。因为还有隶属于表空间的区，他们不属于任何段。
  • List Node 用来与其他区建立连接，形成链表。
  • State 区的状态，
    • FREE 表示已经分配空间，但是为使用的区，
    • FREE_FRAG 有空闲空间的碎片区
    • FULL_FRAG 没有空闲空间的碎片区
    • FSEG 属于某个段的区
    • Page State Bitmap 一共128bit，没2位对应一个页，如果第一位是1，表示页空闲
        _________________________________
       |           Segment ID            |
       |---------------------------------|      _______________________
       |                                 |     | Prev Node Page Number |
       |                                 |      -----------------------
       |                                 |     |    Prev Node Offset   |
       |          List Node              |--->  -----------------------
       |                                 |     | Next Node Paage Number|
       |                                 |      -----------------------
       |                                 |     |    Next Node Offset   |
       |---------------------------------|      -----------------------
       |             State               |           List Node结构
       |---------------------------------|
       |       Page State Bitmap         |
        ---------------------------------
               XDES Entry结构

3. FSP_HDR类型页

前面我们说了可以将FSP_HDR看作是XDES，因为他们都存储了XDES Entry，但是相比于XDES，前者存储了一些表空间的相关属性。多了一个File Space Header，由于FSP_HDR在只存在于表空间中第一个组的第一区中的第一个页中，所以一个表空间只有一个File Space Header。

  • Space ID 表空间ID
  • Size 当前表空间拥有的页面数量
  • FREE Limit 尚未被初始化的最小页号
  • Space Flags 表空间中一些占用存储空间比较小的属性
  • FRAG_N_USED FREE_FRAG链表中已经使用的页面数量
  • List Base Node for FREE List FREE链表的基节点
  • List Base Node for FREE_FRAG list FREE_FRAG链表的基节点
  • List Base Node for FULL_FRAG list FULL_FRAG链表的基节点
  • Next Unused Segment ID 当前表空间中下一个未使用的Segment ID
  • List Base Node for SEG_INODES_FULL SEG_INODES_FULL链表的基节点
  • List Base Node for SEG_INODES_FREE SEG_INODES_FREE链表的基节点

重点是5个基节点

        _________________________________          ___________________________________
       |           File Header           |        |             Space ID              |
       |---------------------------------|        |-----------------------------------|
       |        File Space Header        | -----> |             Not Used              |
       |---------------------------------|        |-----------------------------------|
       |          XDES Entry 0           |        |               Size                |
       |          XDES Entry 1           |        |-----------------------------------|
       |          XDES Entry 2           |        |            FREE Limit             |
       |             ...                 |        |-----------------------------------|
       |          XDES Entry 255         |        |            Space Flags            |
       |---------------------------------|        |-----------------------------------|
       |          Emptry Space           |        |           FRAG_N_USED             |
       |---------------------------------|        |-----------------------------------|
       |          File Trailer           |        |    List Base Node for FREE List   |
        ---------------------------------         |-----------------------------------|
                                                  | List Base Node for FREE_FRAG list |
                                                  |-----------------------------------|
                                                  | List Base Node for FULL_FRAG list | 
                                                  |-----------------------------------|
                                                  |      Next Unused Segment ID       |
                                                  |-----------------------------------|
                                                  |List Base Node for SEG_INODES_FULL |
                                                  |-----------------------------------|
                                                  |List Base Node for SEG_INODES_FREE |
                                                   -----------------------------------

4. INODE类型页

INODE类型的页中存储的是记录是INODE Entry，一个INODE Entry对应一个段。我们还是按照惯例看看他的结构，可以看出来，他和我们前面说的XDES页的结构很像。右边的List Node结构也是用来形成链表的。

        _________________________________
       |          File Header            |
       |---------------------------------|      _______________________
       | List Node for INODE Page List   | --->| Prev Node Page Number |
       |---------------------------------|      -----------------------
       |          INODE Entry 0          |     |    Prev Node Offset   |
       |---------------------------------|      -----------------------
       |              ...                |     | Next Node Paage Number|
       |---------------------------------|      -----------------------
       |          INODE Entry 84         |     |    Next Node Offset   |
       |---------------------------------|      -----------------------
       |           Empty Space           |           List Node结构
       |---------------------------------|
       |          File Trailer           |
        ---------------------------------
                   INODE结构

4.1 INODE Entry结构

  • Segment ID 记录的是段ID
  • NOT_FULL_N_USED NOT_FULL List中已经使用了多少个页面
  • List Base Node for FREE List FREE链表的基节点
  • List Base Node for NOT_FULL List NOT_FULL链表的基节点
  • List Base Node for FULL List FULL链表的基节点
  • Magic Number 标记该INODE Entry是否已经初始化
  • Fragment Array Entry 对应着碎片区中一个一个零散页

重点是这个链表，链表中的节点是段中的一个一个区，通过区的存储空间占用情况，将区分为了三类，方便进行数据的存储，也提高了效率。比如你要存储非叶子结点页，就只需要找到NOT_FULL链表的基节点，然后存储到对应的区就行。避免遍历不必要的FREE和FULL链。

        _________________________________
       |          Segment ID             |
       |---------------------------------|
       |        NOT_FULL_N_USED          |
       |---------------------------------|
       |  List Base Node for FREE List   |
       |---------------------------------|
       | List Base Node for NOT_FULL List|
       |---------------------------------|
       |  List Base Node for FULL list   |
       |---------------------------------|
       |           Magic Number          |
       |---------------------------------|
       |    Fragment Array Entry 0       |
       |---------------------------------|
       |             ...                 |
       |---------------------------------|
       |    Fragment Array Entry 31      |
        ---------------------------------
                INODE Entry结构

到此我们已经把三个重要的页类型的基本结构都已经介绍了，我们可以看出来，所有的数据依旧是以页为最小单位进行存储的，只不过不同的页分担着不同的责任(记录着不同的内容)，这里重复最多的是XDES类型的页，这里FSP_HDR在一个表空间中只会有一个。然后就是对数据进行分类了，这里使用的是链表，通过链表的方式将将同类型(这里的类型其实说的是区或段的状态，看一下上面5个链表的名称你应该可以初步看出一些区别来)的数据连接在一起，然后在FSP_HDR中记录链表的基节点。

5. 碎片区

当我们向表空间中插入一条数据时(假设只有主键，没有其他索引)，按照上面我们说的，此时就会生成两个段(一个段存放非叶子结点，另一个段存叶子节点)，一个段里面要有一个区，所以一条数据会占2MB，显然，这样很浪费内存。所以为了解决这个问题，Mysql提出了碎片区，碎片区直属于表空间，当刚开始向表中插入数据时，段时从某个碎片区中以单个页为单位分配存储空间，当某个段占用了碎片区中32个页面后，就会以完整的区为单位分配存储空间(并不会将原来存在碎片区中的复制到新申请的完整的区中)。所以段是一些完整的区和一些碎片区中的页面组成的。

5.1 区的分类

区分为四类

  1. FREE 空闲的区，只分配了存储空间，但是没使用
  2. FREE_FRAG 有剩余空闲页面的碎片区
  3. FULL_FRAG 没有剩余空闲页面的碎片区
  4. FSEG 附属于某个段的区

5.1.1 FREE、FREE_FRAG、FULL_FRAG

表空间中有多个空闲区，我们知道区对应的结构是XDES Entry，为了区分不同类型的区，使用了链表将同类型的区连接起来，FREE类型的区对应的链表就是上面我们说的FREE List，他对应的基节点在FSP_HDR中的List Base Node for FREE List，也就是说，如果我们的段或者碎片区需要空闲区了，就会从FREE List去取，先从FSP_HDR页中找到List Base Node for FREE List基节点，然后取一个节点(区)，将他的状态从FREE改为FREE_FRAG(以碎片区为例)后放到FREE_FRAG List链表上去，然后分配页空间，写数据，等到碎片区满了之后，将该碎片区的State从FREE_FRAG改为FULL_FRAG后放到FULL_FRAG List链表上去。

6. SEG_INODES_FULL List 和 SEG_INODES_FREE List

其实与上面的3个链表很相似，先说一下这两个链表存的什么：

  1. SEG_INODES_FULL List 中存放的是没有空闲空间的INODE页面，也就是不能存储更多的INODE Entry了
  2. SEG_INODES_FREE List 中存放的是有空闲空间的INODE页面

当SEG_INODES_FREE链表不为空时，存储一个INODE Entry只需要从链表中获取一个有空闲空间的INODE页面，然后存进入(如果满了，就将当前节点放到SEG_INODES_FULL链表中)。如果SEG_INODES_FREE链表为空，就要从表空间下的FREE_FRAG链表中申请一个页面，并将该页面的类型修改为INODE，把该页面放到SEG_INODES_FREE链表中。

7. 表空间中查找数据

以使用主键索引查找数据为例，为了进行数据查找，我们需要先找到该索引的非叶子结点，然后找到叶子节点，就可以找到对应的数据了。所以在前面的过程中，我们首先需要知道的是该主键索引在哪个表空间，接下来我们需要找到对应的段，但是我们是不能直接找到段的，我们需要先找到管理段的INODE页面(也就是叶号)，然后找到对应INODE Entry，也就是我们的段。所以我们查找对应的数据，至少需要知道表空间ID、INODE页号、INODE Entry的偏移位置。

8. 总结

到这里为止，表空间为了进行数据管理，引入了区、组、段这些概念，使用XDES管理区(一个XDES页对应一个组)；使用INOD管理段，然后为了提高空间利用率和效率，引入了碎片区，使用存储空间的空闲状态将同类数据再次进行区分。1)将(隶属于表空间和隶属于段的)区分为了3种状态，2)将INODE页分为了两种状态(有空闲空间和没有空闲空间)。其实整体看来并不复杂，依旧是使用最基本的页进行数据存储，对不同的概念使用不同的页，再次基础上，增加了链表，目的是为了讲数据进一步分类，方便进行数据查找。

// TODO 有问题， 前面说的是当某个段占用了32个碎片区页面，也就是说放碎片区页中存的是数据页(级别小于段)，当时后面却说存INODE Entry时，INODE空间不够时，回去表空间下的FREE_FRAG中区申请一个页面作为INODE使用一个INODE存放的是多个段呀()

GitHub：https://github.com/godfunc
博客园：http://www.cnblogs.com/godfunc
Copyright ©2019 Godfunc
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Godfunc/p/15218704.html