InnoDB的表空間

表空間可以看做是InnoDB存儲引擎邏輯結構的最高層，所有的數據都是存放在表空間中。

1. Extent

對于16KB的頁來說，連續的64個頁就是一個區，也就是說一個區默認占用1MB空間大小。

每256個區被劃分成一組,第一組的前3個頁面是固定的（FSP_HDR，IBUF_BITMAP，INODE），每組的前兩個頁面是固定的（XDES，IBUF_BITMAP）

1.1 為什么需要引入區的概念？

因為B+樹的每一層的節點，都是用一個雙向鏈表連起來的，如果以頁作為存儲單位的話，在B+樹上相鄰的兩個節點，可能在磁盤上相隔非常遠，就會造成磁盤的隨機I/O，因此我們應該使得相鄰位置的節點，物理位置也盡量相連，形成順序I/O。

所以，所以才引入了區（extent）的概念，一個區就是在物理位置上連續的64個頁。在表中數據量大的時候，為某個索引分配空間的時候就不再按照頁為單位分配了，而是按照區為單位分配。

1.2 區的分類

FREE 空閑的區
FREE_FRAG 有剩余空間的碎片區
FULL_FRAG 沒有剩余空間的碎片區
FSEG 附屬于某個段的區
注意：處于FREE、FREE_FRAG以及FULL_FRAG這三種狀態的區都是獨立的，算是直屬于表空間；而處于FSEG狀態的區是附屬于某個段的。

1.3 XDES Entry

每一個區都對應著一個XDES Entry結構.XDES Entry的組成如下圖

Segment ID（8字節）
該區所屬的段的ID
List Node（12字節）
將XDES Entry連成一個鏈表，存儲的是指向上一個XDES和下一個XDES的指針
State（4字節）
前面說到的幾種區的分類，FREE、FREE_FRAG、FULL_FRAG和FSEG
Page State Bitmap（16字節）
這個部分共占用16個字節，也就是128個比特位。我們說一個區默認有64個頁，這128個比特位被劃分為64個部分，每個部分2個比特位，對應區中的一個頁。這兩個比特位的第一個位表示對應的頁是否是空閑的，第二個比特位還沒有用。

1.3.1 XDES Entry鏈表

當向某個段中插入數據時

在剛開始向表中插入數據的時候，段是從某個碎片區以單個頁面為單位來分配存儲空間的。
因此，查找FREE_FRAG 有剩余空間的碎片區，申請一些零散的頁面將數據插入，直到為FULL_FRAG。否則找FREE空閑的區，插入數據。而為了查找特定狀態的區：

把狀態為FREE的區對應的XDES Entry結構通過List Node來連接成一個鏈表，這個鏈表我們就稱之為FREE鏈表。
把狀態為FREE_FRAG的區對應的XDES Entry結構通過List Node來連接成一個鏈表，這個鏈表我們就稱之為FREE_FRAG鏈表。
把狀態為FULL_FRAG的區對應的XDES Entry結構通過List Node來連接成一個鏈表，這個鏈表我們就稱之為FULL_FRAG鏈表。

當某個段已經占用了32個碎片區頁面之后，就會以完整的區為單位來分配存儲空間

因為一個段中可以有好多個區，有的區是完全空閑的，有的區還有一些頁面可以用，有的區已經沒有空閑頁面可以用了，為了找出段中特定狀態的區：

FREE鏈表：同一個段中，所有頁面都是空閑的區對應的XDES Entry結構會被加入到這個鏈表。注意和直屬于表空間的FREE鏈表區別開了，此處的FREE鏈表是附屬于某個段的。
NOT_FULL鏈表：同一個段中，仍有空閑空間的區對應的XDES Entry結構會被加入到這個鏈表。
FULL鏈表：同一個段中，已經沒有空閑空間的區對應的XDES Entry結構會被加入到這個鏈表。

1.3.2 鏈表基節點

上面說到的6種鏈表，都對應著一個LIst Base Node，因此只要記錄下鏈表基節點，就可以搜索整個鏈表

List Length表明該鏈表一共有多少節點，
First Node Page Number和First Node Offset表明該鏈表的頭節點在表空間中的位置。
Last Node Page Number和Last Node Offset表明該鏈表的尾節點在表空間中的位置。

2.segment

段由若干個零散的頁面以及一些完整的區組成。

2.1 為什么需要引入段的概念？

在進行范圍查詢的時候，其實我們是對B+樹的葉子節點進行掃描，如果將B+樹的葉子節點和非葉子節點都放在一個地方的話，就會影響范圍查詢的速度。

因此，InnoDB將葉子節點的區的集合分為一個段，非葉子區的集合同樣也分為一個段。也就是說一個索引會生成2個段，一個葉子節點段，一個非葉子節點段。

但是這也帶來了一個問題，就是無論如何一個索引都要至少要占用兩個區，就是2M的空間，即使數據量遠小于2M，就會造成浪費，因此引入了碎片區的概念。

2.3 碎片區

在一個碎片區中，并不是所有的頁都是為了存儲同一個段的數據而存在的，而是碎片區中的頁可以用于不同的目的，比如有些頁用于段A，有些頁用于段B，有些頁甚至哪個段都不屬于。碎片區直屬于表空間，并不屬于任何一個段。所以此后為某個段分配存儲空間的策略是這樣的：

在剛開始向表中插入數據的時候，段是從某個碎片區以單個頁面為單位來分配存儲空間的。
當某個段已經占用了32個碎片區頁面之后，就會以完整的區為單位來分配存儲空間。

2.4 INODE Entry

與區的XDES Entry類似，段也存在INODE Entry，組成如下

Segment ID

就是指這個INODE Entry結構對應的段的編號（ID）。

NOT_FULL_N_USED

這個字段指的是在NOT_FULL鏈表中已經使用了多少個頁面。

3個List Base Node

分別為段的FREE鏈表、NOT_FULL鏈表、FULL鏈表定義的List Base Node，這樣我們想查找某個段的某個鏈表的頭節點和尾節點的時候，就可以直接到這個部分找到對應鏈表的List Base Node。

Magic Number：

這個值是用來標記這個INODE Entry是否已經被初始化了（初始化的意思就是把各個字段的值都填進去了）。如果這個數字是值的97937874，表明該INODE Entry已經初始化，否則沒有被初始化。。

Fragment Array Entry

我們前邊強調過無數次段是一些零散頁面和一些完整的區的集合，每個Fragment Array Entry結構都對應著一個零散的頁面，這個結構一共4個字節，表示一個零散頁面的頁號

3.FSP_HDR（第一組前3個頁面之一）

這個頁面的類型是FSP_HDR，它存儲了表空間的一些整體屬性以及第一個組內256個區的對應的XDES Entry結構

由圖可得，這個頁面由五部分組成

3.1 File Header

記錄頁的一些通用信息

3.2 File Space Header

表空間的一些整體屬性信息

Space ID 4字節表空間的ID
Not Used 4字節這4個字節未被使用，可以忽略
Size 4字節當前表空間占有的頁面數
FREE Limit 4字節尚未被初始化的最小頁號，大于或等于這個頁號的區對應的XDES Entry結構都沒有被加入FREE鏈表
Space Flags 4字節表空間的一些占用存儲空間比較小的屬性
FRAG_N_USED 4字節 FREE_FRAG鏈表中已使用的頁面數量
List Base Node for FREE List 16字節 FREE鏈表的基節點
List Base Node for FREE_FRAG List 16字節 FREE_FRAG鏈表的基節點
List Base Node for FULL_FRAG List 16字節 FULL_FRAG鏈表的基節點
Next Unused Segment ID 8字節當前表空間中下一個未使用的 Segment ID
List Base Node for SEG_INODES_FULL List 16字節 SEG_INODES_FULL鏈表的基節點
List Base Node for SEG_INODES_FREE List 16字節 SEG_INODES_FREE鏈表的基節點

3.3 XDES Entry

在這部分保存的就是一整個組（256個區）的XDES Entry，

3.4 Empty Space

用于頁結構的填充，沒啥實際意義

3.5 File Trailer

校驗頁是否完整

4.INODE（第一組前3個頁面之一）

這個INODE類型的頁就是為了存儲INODE Entry結構而存在的

結構上與XDES大體相同，但是引入了List Node for INODE Page List

4.1 List Node for INODE Page List

每個INODE Entry結構占用192字節，一個頁面里可以存儲85個這樣的結構。但是一個表空間中可能存在超過85個段，所以可能一個INODE類型的頁面不足以存儲所有的段對應的INODE Entry結構，所以就需要額外的INODE類型的頁面來存儲這些結構。于是引入了List Node for INODE Page List：

SEG_INODES_FULL鏈表：該鏈表中的INODE類型的頁面中已經沒有空閑空間來存儲額外的INODE Entry結構了。
SEG_INODES_FREE鏈表：該鏈表中的INODE類型的頁面中還有空閑空間來存儲額外的INODE Entry結構了。

因此插入INODE Entry時

先看看SEG_INODES_FREE鏈表是否為空，如果不為空，直接從該鏈表中獲取一個節點，也就相當于獲取到一個仍有空閑空間的INODE類型的頁面，然后把該INODE Entry結構放到該頁面中。當該頁面中無剩余空間時，就把該頁放到SEG_INODES_FULL鏈表中。
如果SEG_INODES_FREE鏈表為空，則需要從表空間的FREE_FRAG鏈表中申請一個頁面，修改該頁面的類型為INODE，把該頁面放到SEG_INODES_FREE鏈表中，與此同時把該INODE Entry結構放入該頁面。