innodb在实现表空间（table space）基于文件IO之上构建的一层逻辑存储空间管理，table space采用逻辑分层的结构：space、segment inode、extent和page.在实现层的逻辑使用了磁盘链表这种结构来管理逻辑关系。我们先来介绍磁盘链表。 ## 1.磁盘链表 磁盘链表的实现fut0lst.*文件当中， innodb为了管理表空间和索引模块，定义了一个基于磁盘的链表，主要是用来保存磁盘数据结构之间的关系。这个链表不是基于内存指针的，而是基于page no和boffset来做位置绑定的。在innodb中定义了一个fil_addr_t的结构来做描述： ~~~ typedef struct fil_addr_struct { ulint page; /*page在space中的编号*/ ulint boffset; /*page中的字节偏移量，在内存中使用2字节表示*/ }fil_addr_t; ~~~ fil_addr_t可以通过fut_get_ptr函数来获得对应node的内存位置(flst_node_t) flst_node_t可以通过buf_ptr_get_fsp_addr来确定fil_addr_t。 flst_node_t中存有12个字节的内容，前6个字节（page:4 boffset:2）表示相对自己前一个node的fil_addr_t信息，后6个字节表示相对自己后1个node的fil_addr_t。除了flst_node_t以外，磁盘链表还有一个头信息flst_base_node_t，头信息是一个节点个数FLST_LEN（4字节） + FLST_FIRST (6字节)+ FLST_LAST（6字节）. ### 1.1磁盘链表的结构关系  ## 2.space结构分析 在innodb的表空间中，所有的数据都是以page为单位来存储的，在space(表空间)中有两种 page: FSP_HDR/XDES Page、fseg inodes Page。每个page是以默认16KB的大小存储的， innodb在分配page的时候总以一个extent为单位一次性分配64个page。 ### 2.1 FSP HDR/XDES Page ### 2.1.1XDES结构分析（extent） 这个类型的page主要存储两类信息，前面112个字节存储的是File Space header信息，后面剩余的空间存储多个extent描述信息（XDES ），具体存储结构图如下：  只有space的第一个page会保存FSP header,其他的页是用0填充的。 每个XDES Page最大包含256个XDES descritptors Entry，每个XDES descritptors Entry对应的是一个extent。XDES descritptors Entry的结构描述如下：  File Segment ID                 是当前extent所属segment的ID   XDES list                         是磁盘双向链表的一个节点，分别指向前一个XDES entry的page位置和后一个                                             XDES entry的page位置   state                                 extent的状态, XDES_FREE、XDES_FREE_FRAG、XDES_FULL_FRAG、                                             XDES_FSEG,在为XDES_FSEG的时候，表示这个extent已经隶属于一个                                             Segment,extent在创建的时候会指定成XDES_FSEG状态。一个extent在刚                                             分配时的状态XDES_FREE.  bitmap                              当前extent的所有page的状态索引，一个page占用2 bit,第一个bit表示是否被使用                                            状态，第二个位表示是否并 清空状态，清空状态暂时好像没有用 到，都是TRUE。 ### 2.1.2 FSP Header            space id                    当前表空间的ID           size                    当前space最大可容纳的page数,文件扩大时才会改变这个值           limit                   当前space已经分配初始化的page数,包括空闲的和已经使用的           flag                    未起作用           frage used         FSP_FREE_FRAG列表中已经被使用的page数           free list              space中可用的extent对象列表，extent里面没有一个page被使用           frag free list      有可用碎叶page的extent列表，exntent里面有部分page被使用           frag full list       没有有可用page的extent列表，exntent里面全部page被使用           segment id        下一个可利用的segment id           full inode list     space当前完全占满的segment inode页列表           free inode list     space当前完全占满的segment inode页列表 ### 2.2 Fseg inode Page 这个页类型是存储fseg inode用的页，每个inode 占用192个字节，一个page存储有85个inode对象,结构如下：  在FIL Header后面紧接了12个字节，这个12个字节其实就是full inode list或则free inode list中的列表所以，分别表示前后的fil_addr_t。每个inode信息占用192个字节，里面分别管理对应的extent和fragment page。inode 结构如下：    fseg id                                    segment ID           not full used                          FSEG_NOT_FULL列表中的page数           FSEG_FREE                         inode中空闲的extent列表           FSEG_NOT_FULL               extent有部分page被占用，有部分page空闲的extent列表           FSEG_FULL                          完全占满的extent的列表           FSEG_MAGIC_N                  校验魔法字           fragment array                       一个长度为32的零散page索引存储的数组，如果这个数据满了.主要的作用是                                                            节省空间，例如在表刚建立时，不会分配一个完整的extent给表用，只会分配                                                            6个PAGE页，这时候就需要用fragment array来管理。 ## 3.space结构图 ### 3.1space框架关系图  ### 3.2模块关系示意图  ## 4.space的inode、extent和page分配流程 innodb的space中，inode、extent和page之间的关系是环环相扣的，inode对应的是segment，extent对应的是区，page是页，也是表空间的最小分配单位。一个page在MySQL中默认是16KB大小，一个extent管理64个page,大小为1M，而inode可以管理很多extent加32个frag page（碎页）。frag page是为了节省空间而定义的。在了解了以上基本的概念后，我们开始分析inode的分配、extent的分配和page的分配过程。 ### 4.1 inode的分配流程 通过inode page的介绍我们可以知道，inode信息一定是存储在inode page中的，在分配inode的时候，一定是从inode page中获取空闲的inode。如果没有inode page可以使用，会先去在space的free list得到一个inode page（在函数fsp_alloc_seg_inode_page），然后再在这个inode page获得空闲的inode。在这个过程中会涉及到两个磁盘链表：FSP_SEG_INODES_FREE和FSP_SEG_INODES_FULL，这两个队列是管理inode page的，如果没有空闲inode的inode page是放在FSP_SEG_INODES_FULL中的，如果还有空闲inode的inode page是放在FSP_SEG_INODES_FREE中。一个inode页包含85个inode信息。以下是inode 分配示意图：    第1步：在FSP_SEG_INODES_FREE为空时，向space默认的头页中获取一个inode page，对应函数fsp_alloc_seg_inode_page   第2步：在申请inode时，如果FSP_SEG_INODES_FREE有可以的inode page,从inode page或的一个inode，对应函数fsp_alloc_seg_inode   第3步：如果在申请inode后，inode所处的inode page已经没有空闲的inode了，会将这个inode page放入FSP_SEG_INODE_FULL,并将其从FSP_SEG_INODES_FREE中删除。   第4步：如果inode管理的所有的页都是空闲，那么这个inode状态会被置为空闲状态，这个时候会将这个inode page从FSP_SEG_INODE_FULL移 到FSP_SEG_INODES_FREE中;这个过程只有在segment删除的时候才会调用。对应的函数fsp_free_seg_inode ### 4.2extent的分配流程 extent的分配方式有两种，一种是通过inode进行申请分配，一种是通过fragment碎片方式申请分配。inode分配方式是当inode中没有空闲可用的extent的时候，会向space free list中申请1个或者5个extent进行管理，如果当inode管理的extent数量小于40时，每次只会申请1个extent,如果超过这个大小，就会一次申请5个extent，这个过程会涉及到inode的FSEG_FREE、FSEG_NOT_FULL和FSEG_FULL三个磁盘链表。第二种申请方式是分配frag page时，是直接对extent进行申请，这其中会涉及到FSP_FREE_FRAG和FSP_FULL_FRAG这两个磁盘链表。以下是分配示意图：  上图中，1~7是属于inode申请分配流程， 8~12是属于frag page的申请extent方式   1: 当inode的free list为空，如果需要使用申请使用新的extent，innodb会从space free list获得空闲的extent加入到inode free list当中。   2: 当inode  free list中有extent,如果申请使用新的extent，只只需要从inode free list中拿取，并将extent移到inode not full当中。   3:只是通过inode方式申请页的一个操作，这个时候extent有足够多的空闲page.   4: 当extent中没有空闲的page时，会将这个extent从inode not full中转移到inode full当中。   5: 当一个page释放时，这个page所处的extent是一个完全占用的且被inode管理的extent,那么page释放后，就会将这个extent从inode full移到inode not full   6:当一个page释放时，这个page所处的extent有且只有这一个page被占用，那么page释放后,这个extent就会归还给inode list.并且会直接进行 7将extent归还给space free list. ** 8~12和以上步骤类似** ### 4.3page的分配流程 page的申请分配是基于inode 申请和extent申请的基础上，页的申请有外部通过inode方式申请，也有通过fragment page方式申请。fragment方式申请相对比较简单，就不在表述，源码中很清晰。inode方式分配是比较复杂的，其主要实现是在fseg_alloc_free_page_low和fseg_free_page_low这两个函数。在fseg_alloc_free_page_low函数中实现了7种情况获得inode中的page.   1. 指定的inode的hint位置的页是空闲状态，直接返回对应的page   2.descr是空闲状态，但segment inode中的空闲page数量 < 1/8,且碎片页被全部用完,为其分配一个extent,并获得hint对应的page   3.如果descr不是空闲状态，且segment inode中的空闲page数量 < 1/8,在inode当中获得一个空闲的extent，并且将这个extent descr对应的页返回。   4.descr是XDES_FSEG状态，且这个extent中还有空闲page,从其中获取一个page.   5.除了以上情况外，如果descr不是空闲的，但是inode还有其他的空闲extent,从其他的extent获得一个空闲。   6.如果其他的extent没有空闲页，但是fragment array还有空闲的碎片page，从空闲的碎片page中获得一个空闲页。   7.如果连碎页也没有，直接申请分配一个新的extent，并在其中获取一个空闲的page. ## 5.综述 table space的实现在fsp0fsp.*文件当中，也依赖于page0page.*  fil0fil.* 等文件。innodb在存储上，定义了最小的存储单位就是page，space在设计这些层关系，都是为了更为高效和合理的管理page。space可以和其他表存在同一个数据库文件中，也可以一张表一个文件存储。这取决于MySQL的配置。分析space的结构和工作原理有利于我们理解innodb的存储方式，其后面理解索引、锁和事务提供有力的基础。上面也说到最小的存储单位是page，我将在下一章节中单独来介绍数据page的存储方式和其工作原理。