本文分享InnoDB如何規(guī)劃表空間讥巡，如何存儲(chǔ)表空間元信息以及用戶數(shù)據(jù)。
思考一個(gè)問(wèn)題趴樱，如果給你一個(gè)文件馒闷，讓你存儲(chǔ)MySql的數(shù)據(jù)，你會(huì)怎么做叁征？
下面是一種比較合理的思路纳账。首先把文件劃分成大小相等的塊（InnoDB中的頁(yè)），每次取一塊使用捺疼。為了管理這些塊信息疏虫，我們也拿出一塊空間，存儲(chǔ)每一塊空間的位置啤呼，偏移量卧秘，以及已經(jīng)使用和剩余未使用的塊（InnoDB中的FSP HEADER PAGE
，文件管理頁(yè)）
然后根據(jù)不同的邏輯建立對(duì)應(yīng)的對(duì)象官扣，如索引對(duì)象翅敌，回滾信息對(duì)象（InnoDB中的段），這些對(duì)象從上面分好的塊中申請(qǐng)空間使用惕蹄，并管理屬于自己的塊蚯涮，當(dāng)然，這些對(duì)象信息也需要拿出一塊空間存儲(chǔ)起來(lái)（InnoDB中的INODE PAGE）卖陵。
這就是InnoDB中段和頁(yè)的概念
下面來(lái)明確幾個(gè)核心概念
表空間
InnoDB將所有數(shù)據(jù)（包括表數(shù)據(jù)遭顶，索引，回滾信息泪蔫，插入緩沖索引頁(yè)棒旗，系統(tǒng)事務(wù)信息，二次寫緩沖）邏輯地放在一個(gè)空間中撩荣，稱為共享表空間铣揉。
默認(rèn)表空間的存儲(chǔ)文件為data目錄下的ibdata1饶深，初始化為10M。段
一個(gè)索引（InnoDB都是B+索引）由兩個(gè)段管理逛拱，葉子節(jié)點(diǎn)段（leaf segment）和非葉子節(jié)點(diǎn)段（non leaf segment）
回滾數(shù)據(jù)也是通過(guò)段管理粥喜。
- 區(qū)
InnoDB申請(qǐng)空間的最小單位，由連續(xù)頁(yè)組成的空間橘券，大小為1MB，保持不變卿吐。
InnoDB一次從磁盤中申請(qǐng)4~5個(gè)區(qū)旁舰。
- 頁(yè)
InnoDB訪問(wèn)的最小單位，默認(rèn)16KB嗡官。一個(gè)區(qū)中一共有64個(gè)連續(xù)的頁(yè)箭窜。
緩沖池是以頁(yè)為管理單位，每次讀取或刷新一頁(yè)數(shù)據(jù)衍腥。
參數(shù): innodb_page_size磺樱，可以將頁(yè)大小設(shè)置為4K，8K.
InnoDB將表空間按Page切分婆咸，這些Page主要分為兩類：存儲(chǔ)表空間元信息的管理頁(yè)（如FIL_PAGE_TYPE_FSP_HDR）和存儲(chǔ)表空間用戶數(shù)據(jù)的索引頁(yè)（如FIL_PAGE_INDEX竹捉，F(xiàn)IL_PAGE_INODE）。
FIL Header
所有頁(yè)都有兩個(gè)統(tǒng)一的結(jié)構(gòu)尚骄，F(xiàn)IL Header块差，占據(jù)頁(yè)面的前38個(gè)字節(jié)，F(xiàn)IL Trailer倔丈，占據(jù)頁(yè)面末尾8字節(jié)憨闰。
FIL Header結(jié)構(gòu)如下
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| FIL_PAGE_SPACE | 4 | 所在表空間ID(space id) |
| FIL_PAGE_OFFSET | 4 | 該頁(yè)在表空間的偏移量（page no） |
| FIL_PAGE_PREV | 4 | 前驅(qū)節(jié)點(diǎn)的偏移量(僅對(duì)索引頁(yè)有效) |
| FIL_PAGE_NEXT | 4 | 后繼節(jié)點(diǎn)的偏移量（僅對(duì)索引頁(yè)有效） |
| FIL_PAGE_LSN | 8 | 頁(yè)最后刷新到磁盤的LSN |
| FIL_PAGE_TYPE | 2 | 頁(yè)的類型 |
| FIL_PAGE_FILE_FLUSH_LSN | 8 | 僅在第一個(gè)Page（FSP HEADER PAGE）使用，用來(lái)判斷數(shù)據(jù)庫(kù)是否正常關(guān)閉 |
| FIL_PAGE_SPACE_ID | 8 | 僅在第一個(gè)Page使用需五，保存數(shù)據(jù)庫(kù)關(guān)閉時(shí)歸檔重做日志的編號(hào) |
InnoDB中每一個(gè)表空間都會(huì)有一個(gè)唯一的space id鹉动，共享表空間的space id就是0。
每個(gè)頁(yè)都有一個(gè)32位序號(hào)page no宏邮，稱為偏移量泽示，即離表空間初始位置的偏移量。因?yàn)槊總€(gè)頁(yè)大小為16kb蜀铲，所以第0個(gè)頁(yè)的偏移量為0边琉，第一個(gè)頁(yè)的偏移量為16384，以此類推记劝。
通過(guò)space id和page no变姨，InnoDB可以定位任何一個(gè)頁(yè)。
FIL_PAGE_TYPE標(biāo)志頁(yè)的類型厌丑，InnoDB常用頁(yè)類型如下
FIL_PAGE_TYPE_ALLOCATED：該頁(yè)為最新分配
FIL_PAGE_IBUF_BITMAP：Insert Buffer位圖頁(yè)
FIL_PAGE_TYPE_SYS：系統(tǒng)頁(yè)
FIL_PAGE_TYPE_TRX_SYS：事務(wù)系統(tǒng)數(shù)據(jù)頁(yè)
FIL_PAGE_TYPE_FSP_HDR：FSP HEADER PAGE頁(yè)
FIL_PAGE_TYPE_XDES：擴(kuò)展描述頁(yè)
FIL_PAGE_IBUF_FREE_LIST：Insert Buffer空閑列表頁(yè)
FIL_PAGE_UNDO_LOG：Undo Log頁(yè)
FIL_PAGE_INDEX：B+樹葉子節(jié)點(diǎn)頁(yè)
FIL_PAGE_INODE：B+樹索引節(jié)點(diǎn)頁(yè)
FIL_PAGE_TYPE_BLOB：BLOB頁(yè)
FIL Trailer
FIL Trailer是在文件末尾的最后8個(gè)字節(jié)定欧， 低位4個(gè)字節(jié)是用來(lái)表示Page頁(yè)中數(shù)據(jù)的checksum渔呵，最后4字節(jié)和FIL Header中的FIL_PAGE_LSN相同
下面說(shuō)到的頁(yè)都有FIL Header，F(xiàn)IL Trailer砍鸠，不再重復(fù)說(shuō)明扩氢。
現(xiàn)在看一下關(guān)鍵的關(guān)鍵的管理頁(yè)。
FSP HEADER PAGE
表空間第1頁(yè)就是文件管理頁(yè)FSP HEADER PAGE爷辱，存儲(chǔ)表空間關(guān)鍵元數(shù)據(jù)信息录豺。由FSP HEADER、XDES ENTRIES構(gòu)成饭弓。
FSP HEADER
FSP HEADER主要存儲(chǔ)表空間元信息双饥，維護(hù)關(guān)鍵結(jié)構(gòu)分配信息，主要變量如下：
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| FSP_SIZE | 4 | 表空間大小弟断，以Page數(shù)量計(jì)算 |
| FSP_FREE_LIMIT | 4 | 當(dāng)前已經(jīng)使用的位置 |
| FSP_FREE | 16 | 空閑區(qū)鏈表 |
| FSP_FREE_FRAG | 16 | 部分可以用碎片區(qū)鏈表 |
| FSP_FULL_FRAG | 16 | 已經(jīng)完全使用的碎片區(qū)鏈表 |
| FSP_SEG_INODES_FULL | 16 | 已經(jīng)完全使用的INODE PAGE鏈表 |
| FSP_SEG_INODES_FREE | 16 | 部分可用的INODE PAGE鏈表 |
區(qū)具體可以分為區(qū)(extent)和碎片區(qū)(frag extent)
碎片區(qū)是比較特殊的區(qū)咏花，用于分配碎片頁(yè)。
XDES ENTRIES
接下來(lái)是區(qū)描述符XDES ENTRIES阀趴，每個(gè)區(qū)描述符需占用40個(gè)字節(jié)昏翰，用于追蹤64個(gè)頁(yè)的使用狀態(tài)。
每個(gè)FSP HEADER PAGE只能管理256個(gè)區(qū)的信息（也就是16384個(gè)頁(yè)）刘急，因此每隔16384個(gè)頁(yè)棚菊，會(huì)有一個(gè)類似FSP HEADER PAGE的Page來(lái)描述隨后的區(qū)信息
XDES ENTRIES主要變量如下
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| XDES_FLST_NODE | 12 | 維護(hù)鏈表前后節(jié)點(diǎn)信息 |
| XDES_STATE | 4 | 標(biāo)識(shí)該區(qū)是屬于FSP_FREE，F(xiàn)SP_FRAG_FREE或FSP_FRAG_FREE_FULL或XDES_SEG（某個(gè)段） |
| XDES_BITMAP | 16 | 標(biāo)識(shí)區(qū)中64個(gè)頁(yè)的使用狀態(tài) |
XDES_BITMAP使用位圖方式保存排霉，每個(gè)頁(yè)的使用狀態(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é)，對(duì)應(yīng)一個(gè)段苟耻。
SEGMENT INODE結(jié)構(gòu)主要變量如下：
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| FSEG_FREE | 16 | 未使用的extend鏈表 |
| FSEG_FULL | 16 | 已完全使用的extend鏈表 |
| FSEG_NOT_FULL | 16 | 部分可用的extend鏈表 |
| FSEG_FRAG_ARR[0] | 4 | 碎片頁(yè)數(shù)組首頁(yè)地址 |
| ... | ||
| FSEG_FRAG_ARR[31] | 4 | 碎片頁(yè)數(shù)組尾頁(yè)地址 |
為節(jié)省空間篇恒，每個(gè)segment都先從FSP HEADER的FSP_FREE_FRAG中分配32個(gè)碎片頁(yè)（FSEG_FRAG_ARR），當(dāng)這些32個(gè)頁(yè)面不夠使用時(shí)凶杖，再申請(qǐng)區(qū)胁艰。
每個(gè)INODE PAGE默認(rèn)可存儲(chǔ)85個(gè)SEGMENT INODE。每個(gè)索引使用2個(gè)segment，分別用于管理葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)腾么。
所以一個(gè)INODE PAGE最多可以保存42個(gè)索引信息(一個(gè)索引使用兩個(gè)段)奈梳。如果表空間有超過(guò)42個(gè)索引,則必須再分配一個(gè)INODE PAGE。INODE PAGE的分配是從碎片區(qū)中申請(qǐng)解虱，但它的位置不是固定的攘须。為了找到索引的INODE ENTRY，InnoDB定義了SEGMENT HEADER殴泰，結(jié)構(gòu)如下
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| FSEG_HDR_SPACE | 4 | INODE PAGE所在表空間ID |
| FSEG_HDR_PAGE_NO | 4 | INODE PAGE所在表空間的偏移量 |
| FSEG_HDR_OFFSET | 2 | INODE ENTRY在頁(yè)的偏移量 |
對(duì)于用戶表于宙，其索引的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é) | 描述 |
|---|---|---|
| FLST_LEN | 4 | 鏈表長(zhǎng)度 |
| FLST_FIRST | 6 | 鏈表首節(jié)點(diǎn)地址 |
| FLST_LAST | 6 | 鏈表尾節(jié)點(diǎn)地址 |
它們指向的節(jié)點(diǎn)為XDES ENTRIES的XDES_FLST_NODE瓶蚂，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體稱為FLST_NODE
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| FLST_PREV | 6 | 鏈表前驅(qū)節(jié)點(diǎn)地址 |
| FLST_NEXT | 6 | 鏈表后繼節(jié)點(diǎn)地址 |
下面是一個(gè)表空間的示意圖糖埋，請(qǐng)理解該圖
第2個(gè)Page是FIL_PAGE_IBUF_BITMAP，主要用于跟蹤隨后的每個(gè)PAGE的change buffer信息窃这，使用4個(gè)bit來(lái)描述每個(gè)page的change buffer信息瞳别。
由于FIL_PAGE_IBUF_BITMAP的空間有限，同樣每隔256個(gè)Extent Page之后杭攻，也會(huì)在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埠巨，存儲(chǔ)了SYS_TABLES，SYS_TABLE_IDS现拒，SYS_COLUMNS辣垒，SYS_INDEXES和SYS_FIELDS等數(shù)據(jù)詞典表的Root Page（b+樹Root節(jié)點(diǎn)所在Page）。
有興趣的同學(xué)可以自行了解
索引組織表
上面說(shuō)了InnoDB通過(guò)索引頁(yè)來(lái)存放行記錄印蔬，那么這些行記錄是怎么組織的呢
（這里說(shuō)的索引頁(yè)勋桶，包括了B+樹葉子節(jié)點(diǎn)頁(yè)FIL_PAGE_INDEX和B+樹索引節(jié)點(diǎn)頁(yè)FIL_PAGE_INODE）
聚集索引
InnoDB中，表都是根據(jù)聚集索引順序組織存放的，這種存儲(chǔ)方式的表稱為索引組織表哥遮。
而InnoDB中主鍵索引使用的是B+索引（通過(guò)B+樹組織的索引）
當(dāng)我們需要打開一張表時(shí)岂丘，需要從表空間的數(shù)據(jù)詞典表中加載元數(shù)據(jù)信息，其中SYS_INDEXES系統(tǒng)表中記錄了用戶表中所有索引Root Page對(duì)應(yīng)的page no眠饮，進(jìn)而找到B+樹Root Page奥帘，就可以對(duì)整個(gè)用戶數(shù)據(jù)B+樹進(jìn)行操作。
B+是為磁盤和其他直接存取輔助設(shè)備設(shè)計(jì)的一種多路平衡查找樹仪召。
看一個(gè)例子
B+樹有以下特點(diǎn)
1寨蹋、B+樹不僅是多叉樹，而且每個(gè)非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值扔茅，不存儲(chǔ)數(shù)據(jù)已旧，這樣每個(gè)非葉子節(jié)點(diǎn)所能保存的鍵值大大增加，可以降低B+的樹深度召娜。
該特性應(yīng)用到索引上运褪，可以使每次加載的節(jié)點(diǎn)包括更多的索引數(shù)據(jù)，也可以減少IO操作（每次讀取樹的下一層都需要一次IO）玖瘸。
所以B+索引具有高扇出性秸讹，在數(shù)據(jù)庫(kù)中，B+樹的高度一般都在2~4層雅倒，查找某一個(gè)鍵值的行記錄最多只需要2到4次IO璃诀。
B+樹中，所有數(shù)據(jù)按鍵值的大小順序存放在同一層的葉子節(jié)點(diǎn)上蔑匣，由各葉子節(jié)點(diǎn)指針進(jìn)行連接劣欢。
每次查找數(shù)據(jù)都需要查找到葉子節(jié)點(diǎn)，查找次數(shù)都相同裁良，所以查詢速度很穩(wěn)定凿将。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ù)庫(kù)做全表掃描。
注意：B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表华匾，這個(gè)是邏輯上的有序映琳，而非物理存儲(chǔ)是順序（維護(hù)成本過(guò)高）机隙。
InnoDB中，Page的FIL Header維護(hù)了上下Page的偏移量萨西，組成雙向鏈表有鹿，而Page中行記錄的記錄頭中維護(hù)了下一行記錄的位置，組成單向鏈表谎脯。
B+樹的查找
類似于二叉查找樹葱跋。起始于根節(jié)點(diǎn)，自頂向下遍歷樹源梭，根據(jù)目標(biāo)值與鍵值比較結(jié)果向下查找對(duì)應(yīng)子樹娱俺。
但B+的數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，所以就算某個(gè)非葉子節(jié)點(diǎn)的鍵值與所查的關(guān)鍵字相等時(shí)废麻，并不停止查找荠卷，而是繼續(xù)沿著這個(gè)節(jié)點(diǎn)左邊的指針向下，一直查到該關(guān)鍵字所在的葉子節(jié)點(diǎn)為止烛愧。
B+樹的平衡
對(duì)于插入和刪除操作油宜，B+通過(guò)分裂和合并節(jié)點(diǎn)維持平衡（類型紅黑樹的旋轉(zhuǎn)），
InnoDb中B+樹的鍵值和數(shù)據(jù)都存放在Page中怜姿，因此Page也需要合并和分裂验庙，有興趣的同學(xué)可以自行了解。
輔助索引
InnoDB中聚集索引和輔助索引都是B+索引社牲。但輔助索引葉子節(jié)點(diǎn)的數(shù)據(jù)不是存儲(chǔ)實(shí)際的數(shù)據(jù)，而是主鍵的值悴了。要想拿到實(shí)際的數(shù)據(jù)需要再通過(guò)主鍵索引找到對(duì)應(yīng)的行記錄然后才能拿到實(shí)際的數(shù)據(jù)搏恤，這個(gè)過(guò)程稱為回表。
如果查詢語(yǔ)句可以從輔助索引（包括聯(lián)合索引）中獲取到所有需要的列湃交，這時(shí)不需要再通過(guò)主鍵索引找到對(duì)應(yīng)的行記錄熟空，這種情況稱為覆蓋索引。
聯(lián)合索引
聯(lián)合索引也是B+索引搞莺。
聯(lián)合索引中列的順序很重要息罗。
InnoDB首先根據(jù)聯(lián)合索引中最左邊的、也就是第一列進(jìn)行排序才沧，在第一列排序的基礎(chǔ)上迈喉，再對(duì)聯(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通過(guò)group查詢后饱搏，再通過(guò)score查詢。
這個(gè)規(guī)則稱為最左前綴匹配原則置逻。
頁(yè)結(jié)構(gòu)
下面看一下InnoDB索引頁(yè)如何保持用戶數(shù)據(jù)推沸，索引頁(yè)由以下部分組成
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| Page Header | 56 | 頁(yè)頭，記錄頁(yè)的一些狀態(tài)信息 |
| Infimun/Supremum Records | 26 | 系統(tǒng)記錄 |
| User Records | 不確定 | 用戶記錄诽偷，即行記錄 |
| Free Space | 不確定 | 空閑空間 |
| Page Directory | 不確定 | 頁(yè)目錄 |
Page Header
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| PAGE_N_DIR_SLOTS | 2 | page directory中槽的數(shù)量 |
| PAGE_HEAP_TOP | 2 | 堆中空閑空間的偏移量 |
| PAGE_N_HEAP | 2 | 記錄數(shù)據(jù)數(shù)量坤学，包含用戶記錄，系統(tǒng)記錄以及標(biāo)記刪除的記錄 |
| PAGE_FREE | 2 | 刪除記錄的鏈表 |
| PAGE_GARBAGE | 2 | 已標(biāo)記刪除記錄數(shù)量 |
| PAGE_N_RECS | 2 | 用戶記錄數(shù)量报慕，不包含系統(tǒng)記錄以及標(biāo)記刪除的記錄 |
| PAGE_MAX_TRX_ID | 8 | 最近一次修改該P(yáng)age記錄的事務(wù)ID |
| PAGE_LEVEL | 2 | 當(dāng)前頁(yè)在索引樹的位置 |
| PAGE_INDEX_ID | 8 | 索引id深浮，表示當(dāng)前頁(yè)屬于那個(gè)索引 |
| PAGE_BTR_SEG_LEAF | 10 | B+樹葉子節(jié)點(diǎn)所在段的segment header，僅在B+樹的Root Page中定義 |
| PAGE_BTR_SEG_TOP | 10 | B+樹非葉子節(jié)點(diǎn)所在段的segment header眠冈，僅在B+樹的Root Page中定義 |
PAGE_LAST_INSERT飞苇，PAGE_DIRECTION，PAGE_N_DIRECTION等變量并未在表中列出蜗顽，他們用于進(jìn)行頁(yè)的分裂操作布卡。
當(dāng)記錄被刪除（不僅是將記錄的deleted_flag設(shè)置為1，而是徹底刪除）雇盖，會(huì)放到PAGE_FREE鏈表中（鏈表通過(guò)記錄頭信息next_record串聯(lián)）忿等，如果這個(gè)頁(yè)上有記錄要插入，會(huì)先檢查PAGE_FREE鏈表空間是否滿足崔挖，如果空間滿足贸街，直接從PAGE_FREE鏈表空間分配，如果空間不夠狸相，再?gòu)目臻e地址(PAGE_HEAP_TOP)分配薛匪。
注意：檢查PAGE_FREE鏈表空間時(shí)，僅檢查第一個(gè)節(jié)點(diǎn)的可用空間脓鹃，不會(huì)通過(guò)next_record進(jìn)行遍歷逸尖。
頁(yè)記錄是根據(jù)主鍵順序排序的，這個(gè)排序是邏輯上的瘸右，而非物理上的（開銷過(guò)大）娇跟。當(dāng)頁(yè)空間不足時(shí)，會(huì)調(diào)用函數(shù)btr_page_reorganize_low進(jìn)行頁(yè)的重新組織太颤，即根據(jù)頁(yè)中記錄主鍵的順序重新進(jìn)行整理逞频，這樣就能整理出碎片的空間。若還是空間不足栋齿，則進(jìn)行分裂操作苗胀。
Infimun和Supremum Records
系統(tǒng)虛擬的記錄襟诸，Infimun表示比任何主鍵值都小的值，Supremum表示比任何可能的值都大的值基协。
User Records
行記錄以鏈表的形式存放在 User Records 中歌亲，行記錄格式中的記錄頭中的 next_record 存放著下一條記錄的地址
Free Space
隨著記錄越來(lái)越多衷旅，F(xiàn)ree Space空間越來(lái)越小救恨，User Records空間越來(lái)越大。當(dāng)Free Space的全部空間都被分配完了猬腰，這個(gè)頁(yè)也就使用完了杂穷，需要申請(qǐng)新的頁(yè)悍缠。
Page Directory
B+索引本身不能定位具體的一條記錄，只能找到該記錄所在的頁(yè)耐量。
InnoDB將頁(yè)載入到內(nèi)存后飞蚓，可以遍歷頁(yè)所有的記錄找到目標(biāo)記錄，但這樣做太慢了廊蜒。
（Page的記錄非物理順序存儲(chǔ)趴拧，無(wú)法通過(guò)物理地址二分查詢）
InnoDB將頁(yè)中數(shù)據(jù)進(jìn)行分組，將每個(gè)組最后一條數(shù)據(jù)的偏移量按順序存儲(chǔ)起來(lái)山叮，組成目錄著榴。
每個(gè)偏移量也被稱為一個(gè)槽（Slot，兩個(gè)字節(jié)）屁倔。這些偏移量都會(huì)被存儲(chǔ)到靠近頁(yè)的尾部的地方脑又，被稱為Page Directory。
這樣InnoDB可以通過(guò)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è)記錄）
行格式
上面說(shuō)了InnoDB索引頁(yè)如何保存用戶數(shù)據(jù)俺亮，即表的行記錄驮捍，下面看看每一行的存儲(chǔ)格式
InnodB中行記錄存儲(chǔ)方法有Compress，Redundant脚曾，Compressed东且，Dynamic。
Redundant行格式是MySql5.0之前使用的本讥，現(xiàn)在基本不會(huì)再使用珊泳，這里就不介紹了鲁冯。
compact格式下，一行記錄依次為以下內(nèi)容：
變長(zhǎng)字段長(zhǎng)度列表色查，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ù)篇解析）
變長(zhǎng)字段長(zhǎng)度列表
若列的長(zhǎng)度小于255字節(jié)塘秦，用1字節(jié)表示
若列的長(zhǎng)度大于255字節(jié)，用2字節(jié)表示（varchar最大限制為65535）
NULL標(biāo)志位
占用字節(jié)為(可為NULL的列數(shù)量/8)向上取整,字節(jié)中哪一位為1动看，表示該行數(shù)據(jù)對(duì)應(yīng)列為NULL值
注意尊剔，變長(zhǎng)字段長(zhǎng)度列表和NULL標(biāo)志位都是是按列定義的倒敘保存的，他們都是可選的菱皆，如果表中沒有變長(zhǎng)字段和允許NULL值的字段须误，那么這兩個(gè)都是占用0字節(jié)長(zhǎng)度
char(N)中的N指定的是字符，UTF-8下CHAR(10)類型的列仇轻，最小可以存儲(chǔ)10字節(jié)的字符京痢，最大可以存儲(chǔ)30字節(jié)的字符。
所以對(duì)于多字節(jié)的字符篷店，char類型在InnoDB存儲(chǔ)引擎內(nèi)部被視為變長(zhǎng)字符類型祭椰。也意味著這些CHAR數(shù)據(jù)類型的長(zhǎng)度會(huì)記錄在變長(zhǎng)長(zhǎng)度列表中。
記錄頭信息
固定5字節(jié)疲陕，結(jié)構(gòu)如下
| 變量 | 字節(jié) | 描述 |
|---|---|---|
| () | 2 | 預(yù)留位 |
| deleted_flag | 1 | 該行是否已被刪除 |
| min_rec_flag | 1 | 如果該行記錄是預(yù)定義為最小的記錄方淤，為1 |
| n_owned | 4 | 該記錄所在Slot擁有的記錄數(shù) |
| heap_no | 13 | 索引堆中該條記錄的索引號(hào) |
| record_type | 3 | 記錄類型，000（普通）蹄殃，001（B+Tree節(jié)點(diǎn)指針）携茂，010（Infimum），011（Supremum） |
| next_record | 16 | 頁(yè)中下一條記錄的相對(duì)位置 |
看一例子
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è)頁(yè)钱慢，可以依照行的實(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 // 變長(zhǎng)字段長(zhǎng)度列表卿堂， 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自動(dòng)創(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'
行溢出
對(duì)于占用字節(jié)數(shù)非常大的列饿敲，在記錄的真實(shí)數(shù)據(jù)中只會(huì)存儲(chǔ)一小部分?jǐn)?shù)據(jù)（768個(gè)字節(jié)），剩余的數(shù)據(jù)分散在其他溢出頁(yè)中(BLOG類型的頁(yè))逛绵，記錄的真實(shí)數(shù)據(jù)中記錄這些頁(yè)的地址怀各，以便找到他們。
注意：行溢出與列定義的類型無(wú)關(guān)术浪。如果varchar過(guò)長(zhǎng)會(huì)發(fā)生行溢出瓢对，而text，blog不夠長(zhǎng)則不會(huì)發(fā)生行溢出胰苏。
InnoDB 1.0.x引入新的行格式硕蛹，以前支持的Compress 和Redundant稱為Antelope文件格式，新的文件格式為Barracuda文件格式硕并，有兩個(gè)行記錄格式：Compressed和Dynamic法焰。他們是Compact的變種形式。他們基本沒什么本質(zhì)上的區(qū)別倔毙，唯一的區(qū)別就是對(duì)于行溢出的處理不同埃仪。Compressed在數(shù)據(jù)頁(yè)只存儲(chǔ)一個(gè)指向溢出頁(yè)的地址，所有的實(shí)際數(shù)據(jù)都存放在溢出頁(yè)中陕赃。
而Compressed還可以是zlib算法對(duì)行數(shù)據(jù)進(jìn)行壓縮卵蛉，因此對(duì)于BLOB，TEXT凯正，VARCHAR這類大長(zhǎng)度類型的數(shù)據(jù)能夠非常有效的存儲(chǔ)毙玻。
參考文檔：
《MySQL技術(shù)內(nèi)幕InnoDB存儲(chǔ)引擎》
《MYSQL內(nèi)核：INNODB存儲(chǔ)引擎》
Innodb表空間
深度 | 解析InnoDB引擎
Chapter 22 InnoDB Storage ngine
InnoDB 文件系統(tǒng)之文件物理結(jié)構(gòu)
如果您覺得本文不錯(cuò)豌蟋，歡迎關(guān)注我的微信公眾號(hào)廊散，您的關(guān)注是我堅(jiān)持的動(dòng)力！
