本文分享InnoDB如何規(guī)劃表空間，如何存儲表空間元信息以及用戶數(shù)據(jù)。

思考一個(gè)問題，如果給你一個(gè)文件，讓你存儲MySql的數(shù)據(jù)，你會怎么做？

下面是一種比較合理的思路。首先把文件劃分成大小相等的塊（InnoDB中的頁），每次取一塊使用。為了管理這些塊信息，我們也拿出一塊空間，存儲每一塊空間的位置，偏移量，以及已經(jīng)使用和剩余未使用的塊（InnoDB中的FSP HEADER PAGE
，文件管理頁）
然后根據(jù)不同的邏輯建立對應(yīng)的對象，如索引對象，回滾信息對象（InnoDB中的段），這些對象從上面分好的塊中申請空間使用，并管理屬于自己的塊，當(dāng)然，這些對象信息也需要拿出一塊空間存儲起來（InnoDB中的INODE PAGE）。
這就是InnoDB中段和頁的概念

下面來明確幾個(gè)核心概念

• 表空間
  InnoDB將所有數(shù)據(jù)（包括表數(shù)據(jù)，索引，回滾信息，插入緩沖索引頁，系統(tǒng)事務(wù)信息，二次寫緩沖）邏輯地放在一個(gè)空間中，稱為共享表空間。
  默認(rèn)表空間的存儲文件為data目錄下的ibdata1，初始化為10M。

• 段
  一個(gè)索引（InnoDB都是B+索引）由兩個(gè)段管理，葉子節(jié)點(diǎn)段（leaf segment）和非葉子節(jié)點(diǎn)段（non leaf segment）
  回滾數(shù)據(jù)也是通過段管理。

• 區(qū)
  InnoDB申請空間的最小單位，由連續(xù)頁組成的空間，大小為1MB，保持不變。
  InnoDB一次從磁盤中申請4~5個(gè)區(qū)。

• 頁
  InnoDB訪問的最小單位，默認(rèn)16KB。一個(gè)區(qū)中一共有64個(gè)連續(xù)的頁。
  緩沖池是以頁為管理單位，每次讀取或刷新一頁數(shù)據(jù)。
  參數(shù): innodb_page_size，可以將頁大小設(shè)置為4K，8K.

InnoDB將表空間按Page切分，這些Page主要分為兩類：存儲表空間元信息的管理頁（如FIL_PAGE_TYPE_FSP_HDR）和存儲表空間用戶數(shù)據(jù)的索引頁（如FIL_PAGE_INDEX，F(xiàn)IL_PAGE_INODE）。

FIL Header

所有頁都有兩個(gè)統(tǒng)一的結(jié)構(gòu)，F(xiàn)IL Header，占據(jù)頁面的前38個(gè)字節(jié)，F(xiàn)IL Trailer，占據(jù)頁面末尾8字節(jié)。

FIL Header結(jié)構(gòu)如下

InnoDB中每一個(gè)表空間都會有一個(gè)唯一的space id，共享表空間的space id就是0。
每個(gè)頁都有一個(gè)32位序號page no，稱為偏移量，即離表空間初始位置的偏移量。因?yàn)槊總€(gè)頁大小為16kb，所以第0個(gè)頁的偏移量為0，第一個(gè)頁的偏移量為16384，以此類推。
通過space id和page no，InnoDB可以定位任何一個(gè)頁。

FIL_PAGE_TYPE標(biāo)志頁的類型，InnoDB常用頁類型如下
FIL_PAGE_TYPE_ALLOCATED：該頁為最新分配
FIL_PAGE_IBUF_BITMAP：Insert Buffer位圖頁
FIL_PAGE_TYPE_SYS：系統(tǒng)頁
FIL_PAGE_TYPE_TRX_SYS：事務(wù)系統(tǒng)數(shù)據(jù)頁
FIL_PAGE_TYPE_FSP_HDR：FSP HEADER PAGE頁
FIL_PAGE_TYPE_XDES：擴(kuò)展描述頁
FIL_PAGE_IBUF_FREE_LIST：Insert Buffer空閑列表頁
FIL_PAGE_UNDO_LOG：Undo Log頁
FIL_PAGE_INDEX：B+樹葉子節(jié)點(diǎn)頁
FIL_PAGE_INODE：B+樹索引節(jié)點(diǎn)頁
FIL_PAGE_TYPE_BLOB：BLOB頁

FIL Trailer

FIL Trailer是在文件末尾的最后8個(gè)字節(jié)， 低位4個(gè)字節(jié)是用來表示Page頁中數(shù)據(jù)的checksum，最后4字節(jié)和FIL Header中的FIL_PAGE_LSN相同
下面說到的頁都有FIL Header，F(xiàn)IL Trailer，不再重復(fù)說明。

現(xiàn)在看一下關(guān)鍵的關(guān)鍵的管理頁。

FSP HEADER PAGE

表空間第1頁就是文件管理頁FSP HEADER PAGE，存儲表空間關(guān)鍵元數(shù)據(jù)信息。由FSP HEADER、XDES ENTRIES構(gòu)成。

FSP HEADER

FSP HEADER主要存儲表空間元信息，維護(hù)關(guān)鍵結(jié)構(gòu)分配信息，主要變量如下：

區(qū)具體可以分為區(qū)(extent)和碎片區(qū)(frag extent)
碎片區(qū)是比較特殊的區(qū)，用于分配碎片頁。

XDES ENTRIES

接下來是區(qū)描述符XDES ENTRIES，每個(gè)區(qū)描述符需占用40個(gè)字節(jié)，用于追蹤64個(gè)頁的使用狀態(tài)。
每個(gè)FSP HEADER PAGE只能管理256個(gè)區(qū)的信息（也就是16384個(gè)頁），因此每隔16384個(gè)頁，會有一個(gè)類似FSP HEADER PAGE的Page來描述隨后的區(qū)信息

XDES ENTRIES主要變量如下

XDES_BITMAP使用位圖方式保存，每個(gè)頁的使用狀態(tài)占用2位（預(yù)留一位）。

一個(gè)區(qū)可以屬于FSP_FREE，F(xiàn)SP_FRAG_FREE或FSP_FRAG_FREE_FULL或者某一個(gè)段。區(qū)的分配實(shí)現(xiàn)了一套類似于借還的機(jī)制。段向表空間租借區(qū)，只有段退還該空間時(shí)，該區(qū)才能重新出現(xiàn)在FSP_FREE/FSP_FULL_FRAG/FSP_FULL中。

INODE PAGE

表空間文件的第3個(gè)page的類型為FIL_PAGE_INODE，管理表空間的段。

INODE PAGE由SEGMENT INODE組成，每個(gè)SEGMENT INODE為192字節(jié)，對應(yīng)一個(gè)段。

SEGMENT INODE結(jié)構(gòu)主要變量如下：

為節(jié)省空間，每個(gè)segment都先從FSP HEADER的FSP_FREE_FRAG中分配32個(gè)碎片頁（FSEG_FRAG_ARR），當(dāng)這些32個(gè)頁面不夠使用時(shí)，再申請區(qū)。

每個(gè)INODE PAGE默認(rèn)可存儲85個(gè)SEGMENT INODE。每個(gè)索引使用2個(gè)segment，分別用于管理葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)。
所以一個(gè)INODE PAGE最多可以保存42個(gè)索引信息(一個(gè)索引使用兩個(gè)段)。如果表空間有超過42個(gè)索引,則必須再分配一個(gè)INODE PAGE。INODE PAGE的分配是從碎片區(qū)中申請，但它的位置不是固定的。為了找到索引的INODE ENTRY，InnoDB定義了SEGMENT HEADER，結(jié)構(gòu)如下

對于用戶表，其索引的Root Page中保存了兩個(gè)SEGMENT HEADER，分別指向葉子節(jié)點(diǎn)的SEGMENT INODE和非葉子節(jié)點(diǎn)的SEGMENT INODE。

鏈表結(jié)構(gòu)

InnoDB的鏈表都是雙向鏈表，如FSP HEADER中變量FSP_FREE，F(xiàn)SP_FREE_FRAG，F(xiàn)SP_FULL_FRAG，F(xiàn)SP_SEG_INODES_FULL，他們都是鏈表頭結(jié)構(gòu)FLST_BASE_NODE，維護(hù)了鏈表的頭指針和末尾指針，

它們指向的節(jié)點(diǎn)為XDES ENTRIES的XDES_FLST_NODE，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體稱為FLST_NODE

下面是一個(gè)表空間的示意圖，請理解該圖

第2個(gè)Page是FIL_PAGE_IBUF_BITMAP，主要用于跟蹤隨后的每個(gè)PAGE的change buffer信息，使用4個(gè)bit來描述每個(gè)page的change buffer信息。
由于FIL_PAGE_IBUF_BITMAP的空間有限，同樣每隔256個(gè)Extent Page之后，也會在XDES PAGE之后創(chuàng)建一個(gè)FIL_PAGE_IBUF_BITMAP。

其他的表空間元信息Page，如
FSP_TRX_SYS_PAGE_NO，共享表空間第6個(gè)Page，記錄了InnoDB重要的事務(wù)系統(tǒng)信息。
FSP_DICT_HDR_PAGE_NO，共享表空間第8個(gè)Page，存儲了SYS_TABLES，SYS_TABLE_IDS，SYS_COLUMNS，SYS_INDEXES和SYS_FIELDS等數(shù)據(jù)詞典表的Root Page（b+樹Root節(jié)點(diǎn)所在Page）。
有興趣的同學(xué)可以自行了解

索引組織表

上面說了InnoDB通過索引頁來存放行記錄，那么這些行記錄是怎么組織的呢
（這里說的索引頁，包括了B+樹葉子節(jié)點(diǎn)頁FIL_PAGE_INDEX和B+樹索引節(jié)點(diǎn)頁FIL_PAGE_INODE）

聚集索引

InnoDB中，表都是根據(jù)聚集索引順序組織存放的，這種存儲方式的表稱為索引組織表。
而InnoDB中主鍵索引使用的是B+索引（通過B+樹組織的索引）

當(dāng)我們需要打開一張表時(shí)，需要從表空間的數(shù)據(jù)詞典表中加載元數(shù)據(jù)信息，其中SYS_INDEXES系統(tǒng)表中記錄了用戶表中所有索引Root Page對應(yīng)的page no，進(jìn)而找到B+樹Root Page，就可以對整個(gè)用戶數(shù)據(jù)B+樹進(jìn)行操作。

B+是為磁盤和其他直接存取輔助設(shè)備設(shè)計(jì)的一種多路平衡查找樹。
看一個(gè)例子

B+樹有以下特點(diǎn)
1、B+樹不僅是多叉樹，而且每個(gè)非葉子節(jié)點(diǎn)只存儲鍵值，不存儲數(shù)據(jù)，這樣每個(gè)非葉子節(jié)點(diǎn)所能保存的鍵值大大增加，可以降低B+的樹深度。
該特性應(yīng)用到索引上，可以使每次加載的節(jié)點(diǎn)包括更多的索引數(shù)據(jù)，也可以減少IO操作（每次讀取樹的下一層都需要一次IO）。
所以B+索引具有高扇出性，在數(shù)據(jù)庫中，B+樹的高度一般都在2~4層，查找某一個(gè)鍵值的行記錄最多只需要2到4次IO。

2. B+樹中，所有數(shù)據(jù)按鍵值的大小順序存放在同一層的葉子節(jié)點(diǎn)上，由各葉子節(jié)點(diǎn)指針進(jìn)行連接。
   每次查找數(shù)據(jù)都需要查找到葉子節(jié)點(diǎn)，查找次數(shù)都相同，所以查詢速度很穩(wěn)定。

3. B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候非常方便。
   如上面例子中的B+樹，如果要查詢[22,89]范圍數(shù)據(jù)，再需要找到鍵值22，再遍歷到數(shù)據(jù)鍵值89就可以了。
   而遍歷所有數(shù)據(jù)，只需要遍歷所有的葉子節(jié)點(diǎn)即可，而不需要遍歷每一層數(shù)據(jù)，這有利于數(shù)據(jù)庫做全表掃描。

注意：B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，這個(gè)是邏輯上的有序，而非物理存儲是順序（維護(hù)成本過高）。
InnoDB中，Page的FIL Header維護(hù)了上下Page的偏移量，組成雙向鏈表，而Page中行記錄的記錄頭中維護(hù)了下一行記錄的位置，組成單向鏈表。

B+樹的查找
類似于二叉查找樹。起始于根節(jié)點(diǎn)，自頂向下遍歷樹，根據(jù)目標(biāo)值與鍵值比較結(jié)果向下查找對應(yīng)子樹。
但B+的數(shù)據(jù)都存儲在葉子節(jié)點(diǎn)，所以就算某個(gè)非葉子節(jié)點(diǎn)的鍵值與所查的關(guān)鍵字相等時(shí)，并不停止查找，而是繼續(xù)沿著這個(gè)節(jié)點(diǎn)左邊的指針向下，一直查到該關(guān)鍵字所在的葉子節(jié)點(diǎn)為止。

B+樹的平衡
對于插入和刪除操作，B+通過分裂和合并節(jié)點(diǎn)維持平衡（類型紅黑樹的旋轉(zhuǎn)），
InnoDb中B+樹的鍵值和數(shù)據(jù)都存放在Page中，因此Page也需要合并和分裂，有興趣的同學(xué)可以自行了解。

輔助索引

InnoDB中聚集索引和輔助索引都是B+索引。但輔助索引葉子節(jié)點(diǎn)的數(shù)據(jù)不是存儲實(shí)際的數(shù)據(jù)，而是主鍵的值。要想拿到實(shí)際的數(shù)據(jù)需要再通過主鍵索引找到對應(yīng)的行記錄然后才能拿到實(shí)際的數(shù)據(jù)，這個(gè)過程稱為回表。
如果查詢語句可以從輔助索引（包括聯(lián)合索引）中獲取到所有需要的列，這時(shí)不需要再通過主鍵索引找到對應(yīng)的行記錄，這種情況稱為覆蓋索引。

聯(lián)合索引

聯(lián)合索引也是B+索引。
聯(lián)合索引中列的順序很重要。
InnoDB首先根據(jù)聯(lián)合索引中最左邊的、也就是第一列進(jìn)行排序，在第一列排序的基礎(chǔ)上，再對聯(lián)合索引中后面的第二列進(jìn)行排序，依此類推。
所以如果想使用聯(lián)合索引的第n列，查詢條件中必須包括聯(lián)合索引前面的第1列到第n-1列的查詢信息。

如(group, score)，可能出現(xiàn)以下排序(1, 46), (1,58), (2,23), (2,96), (3,25), (3,67)。
如果要使用該索引的score，查詢條件中必須包含group，如where group = 2 and score = 96，InnoDB通過group查詢后，再通過score查詢。
這個(gè)規(guī)則稱為最左前綴匹配原則。

頁結(jié)構(gòu)

下面看一下InnoDB索引頁如何保持用戶數(shù)據(jù)，索引頁由以下部分組成

Page Header

PAGE_LAST_INSERT，PAGE_DIRECTION，PAGE_N_DIRECTION等變量并未在表中列出，他們用于進(jìn)行頁的分裂操作。

當(dāng)記錄被刪除（不僅是將記錄的deleted_flag設(shè)置為1，而是徹底刪除），會放到PAGE_FREE鏈表中（鏈表通過記錄頭信息next_record串聯(lián)），如果這個(gè)頁上有記錄要插入，會先檢查PAGE_FREE鏈表空間是否滿足，如果空間滿足，直接從PAGE_FREE鏈表空間分配，如果空間不夠，再從空閑地址(PAGE_HEAP_TOP)分配。
注意：檢查PAGE_FREE鏈表空間時(shí)，僅檢查第一個(gè)節(jié)點(diǎn)的可用空間，不會通過next_record進(jìn)行遍歷。

頁記錄是根據(jù)主鍵順序排序的，這個(gè)排序是邏輯上的，而非物理上的（開銷過大）。當(dāng)頁空間不足時(shí)，會調(diào)用函數(shù)btr_page_reorganize_low進(jìn)行頁的重新組織，即根據(jù)頁中記錄主鍵的順序重新進(jìn)行整理，這樣就能整理出碎片的空間。若還是空間不足，則進(jìn)行分裂操作。

Infimun和Supremum Records
系統(tǒng)虛擬的記錄，Infimun表示比任何主鍵值都小的值，Supremum表示比任何可能的值都大的值。

User Records
行記錄以鏈表的形式存放在 User Records 中，行記錄格式中的記錄頭中的 next_record 存放著下一條記錄的地址

Free Space
隨著記錄越來越多，F(xiàn)ree Space空間越來越小，User Records空間越來越大。當(dāng)Free Space的全部空間都被分配完了，這個(gè)頁也就使用完了，需要申請新的頁。

Page Directory
B+索引本身不能定位具體的一條記錄，只能找到該記錄所在的頁。
InnoDB將頁載入到內(nèi)存后，可以遍歷頁所有的記錄找到目標(biāo)記錄，但這樣做太慢了。
（Page的記錄非物理順序存儲，無法通過物理地址二分查詢）

InnoDB將頁中數(shù)據(jù)進(jìn)行分組，將每個(gè)組最后一條數(shù)據(jù)的偏移量按順序存儲起來，組成目錄。
每個(gè)偏移量也被稱為一個(gè)槽（Slot，兩個(gè)字節(jié)）。這些偏移量都會被存儲到靠近頁的尾部的地方，被稱為Page Directory。
這樣InnoDB可以通過Page Directory進(jìn)行二叉查找定位目標(biāo)所在分組，再遍歷該組數(shù)據(jù)就可以。

每個(gè)槽可以包括4~8條記錄，每個(gè)記錄的記錄頭中n_owned變量，維護(hù)該記錄所在槽的記錄數(shù)量。
（例外，第1個(gè)槽僅包含一個(gè)1記錄，即Infimun，最后一個(gè)槽可包含1~8個(gè)記錄）

行格式

上面說了InnoDB索引頁如何保存用戶數(shù)據(jù)，即表的行記錄，下面看看每一行的存儲格式

InnodB中行記錄存儲方法有Compress，Redundant，Compressed，Dynamic。
Redundant行格式是MySql5.0之前使用的，現(xiàn)在基本不會再使用，這里就不介紹了。

compact格式下，一行記錄依次為以下內(nèi)容：
變長字段長度列表，NULL標(biāo)志位，記錄頭信息，rowID，TransactionID，RollPointer，列1數(shù)據(jù)，列2數(shù)據(jù)，...
其中rowID，TransactionID，RollPointer由InnoDB生成，
注意，如果表中已經(jīng)指定主鍵，則不生成rowID。
（TransactionID，RollPointer用于實(shí)現(xiàn)MVCC功能，將在事務(wù)篇解析）

變長字段長度列表
若列的長度小于255字節(jié)，用1字節(jié)表示
若列的長度大于255字節(jié)，用2字節(jié)表示（varchar最大限制為65535）

NULL標(biāo)志位
占用字節(jié)為(可為NULL的列數(shù)量/8)向上取整,字節(jié)中哪一位為1，表示該行數(shù)據(jù)對應(yīng)列為NULL值

注意，變長字段長度列表和NULL標(biāo)志位都是是按列定義的倒敘保存的，他們都是可選的，如果表中沒有變長字段和允許NULL值的字段，那么這兩個(gè)都是占用0字節(jié)長度

char(N)中的N指定的是字符，UTF-8下CHAR(10)類型的列，最小可以存儲10字節(jié)的字符，最大可以存儲30字節(jié)的字符。
所以對于多字節(jié)的字符，char類型在InnoDB存儲引擎內(nèi)部被視為變長字符類型。也意味著這些CHAR數(shù)據(jù)類型的長度會記錄在變長長度列表中。

記錄頭信息
固定5字節(jié)，結(jié)構(gòu)如下

看一例子

create table mytest (
    t1 varchar(10),
    t2 varchar(10),
    t3 char(10),
    t4 varchar(10)
) engine=INNODB charset=LATIN1 ROW_format=compact;
insert into mytest3 values('d','11',NULL,'fff');

使用vim打開ibd文件，在“命令”模式中輸入“:%!xxd”命令，將文本轉(zhuǎn)換為16進(jìn)制，找到supremum字符串，后面的就是列數(shù)據(jù)了。
（ibd中可能有多個(gè)頁，可以依照行的實(shí)際數(shù)據(jù)判斷哪個(gè)是自己要找的數(shù)據(jù)。）

00010070: 7375 7072 656d 756d 0302 0104 0000 10ff  supremum........
00010080: ef00 0000 0002 0100 0000 0010 2281 0000  ............"...
00010090: 010a 0110 6431 3166 6666 0000 0000 0000  ....d11fff......

解析如下

03 02 01   // 變長字段長度列表， d列-03，c列-null,不記錄  b列-02  a列-01
04  // null標(biāo)準(zhǔn)位, 二進(jìn)制-00000100，逆序，d,c-null,b,a
00 00 10 ff ef  // Record Header，固定5字節(jié) 
00 0000 0002 01  // RowID ，InnoDB自動創(chuàng)建，6字節(jié) 
00 0000 0010 22  // TransactionID
81 0000 010a 0110  // Roll Pointer
64  // 列1數(shù)據(jù)  'a'
31 31  // 列2數(shù)據(jù) '11'
66 6666  // 列4數(shù)據(jù)  'fff'

行溢出
對于占用字節(jié)數(shù)非常大的列，在記錄的真實(shí)數(shù)據(jù)中只會存儲一小部分?jǐn)?shù)據(jù)（768個(gè)字節(jié)），剩余的數(shù)據(jù)分散在其他溢出頁中(BLOG類型的頁)，記錄的真實(shí)數(shù)據(jù)中記錄這些頁的地址，以便找到他們。
注意：行溢出與列定義的類型無關(guān)。如果varchar過長會發(fā)生行溢出，而text，blog不夠長則不會發(fā)生行溢出。

InnoDB 1.0.x引入新的行格式，以前支持的Compress 和Redundant稱為Antelope文件格式，新的文件格式為Barracuda文件格式，有兩個(gè)行記錄格式：Compressed和Dynamic。他們是Compact的變種形式。他們基本沒什么本質(zhì)上的區(qū)別，唯一的區(qū)別就是對于行溢出的處理不同。Compressed在數(shù)據(jù)頁只存儲一個(gè)指向溢出頁的地址，所有的實(shí)際數(shù)據(jù)都存放在溢出頁中。
而Compressed還可以是zlib算法對行數(shù)據(jù)進(jìn)行壓縮，因此對于BLOB，TEXT，VARCHAR這類大長度類型的數(shù)據(jù)能夠非常有效的存儲。

參考文檔：
《MySQL技術(shù)內(nèi)幕InnoDB存儲引擎》
《MYSQL內(nèi)核：INNODB存儲引擎》
Innodb表空間
深度 | 解析InnoDB引擎
Chapter 22 InnoDB Storage ngine
InnoDB 文件系統(tǒng)之文件物理結(jié)構(gòu)

如果您覺得本文不錯，歡迎關(guān)注我的微信公眾號，您的關(guān)注是我堅(jiān)持的動力！