透過前面的內容大家知道表格空間是一個抽象的概念，對系統表格空間來說，對應著檔案系統中一個或多個檔案;對獨立表格空間來說，對應著檔案系統中一個名為(表名.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--