MySQL：InnoDB的頁合并與頁分裂到底是什么
本文為摘錄文章，如有錯誤，請指正。文章是以MySQL5.7版本進行說明，和現有版本可能會有一定差距，但是數據頁的設計基本沒有發生過變化，因此，可以作為學習參考。原文為2017年發表的一篇文章：《InnoDB Page Merging and Page Splitting - Percona Database Performance Blog》。
1 文件表（File-Table）結構
在MySQL5.7創建windmills庫（schema）和wmills表，在文件目錄（/var/lib/mysql）有如下內容：
data/
windmills/
wmills.ibd
wmills.frm原因是從MySQL5.6開始innodb_file_per_table參數默認設置為1，即：每個表都會單獨作為一個文件存儲（如果有分區，可能有多個文件）。如果配置為0，則所有的表都是寫入公共表空間。
- vmills.ibd文件由多個段（segments）組成，每個段和一個索引有關；
- 段由多個區構成，區僅存于段內，每個區的默認固定大小為1MB（頁體積默認情況下）；
- 區是由很多數據頁構成，默認大小為16KB，即一個分區最多由64個數據頁構成。
- 數據頁可以容納2-N行數據行，行的數量取決于數據行的大小；InnoDB要求頁至少要有兩行，因此行的大小最多為8000bytes。
- 文件的結構不會隨著數據行的刪除而變化，但是段會跟著區的變化而變化；
圖片
2 根、分支和葉子(Roots,Branches and Leaves)
每個頁（邏輯上指的是主鍵索引的葉子節點）包含2-N行數據行，根據主鍵排列，樹有著特殊的頁區管理不同的分支，即內部節點（INodes）。示例如下：
圖片
ROOT NODE #3: 4 records, 68 bytes
NODE POINTER RECORD ≥ (id=2) → #197
INTERNAL NODE #197: 464 records, 7888 bytes
NODE POINTER RECORD ≥ (id=2) → #5
LEAF NODE #5: 57 records, 7524 bytes
RECORD: (id=2) → (uuid="884e471c-0e82-11e7-8bf6-08002734ed50", millid=139, kwatts_s=1956, date="2017-05-01", locatinotallow="For beauty's pattern to succeeding men.Yet do thy", active=1, time="2017-03-21 22:05:45", strrecordtype="Wit")表結構為：
CREATE TABLE `wmills` (
`id` bigint(11) NOT NULL AUTO_INCREMENT,
`uuid` char(36) COLLATE utf8_bin NOT NULL,
`millid` smallint(6) NOT NULL,
`kwatts_s` int(11) NOT NULL,
`date` date NOT NULL,
`location` varchar(50) COLLATE utf8_bin DEFAULT NULL,
`active` tinyint(2) NOT NULL DEFAULT '1',
`time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
`strrecordtype` char(3) COLLATE utf8_bin NOT NULL,
PRIMARY KEY (`id`),
KEY `IDX_millid` (`millid`)
) ENGINE=InnoDB;B+樹的根節點就是查詢的根節點，如圖的#3就是根節點。根節點（頁）包含了索引ID、INodes數量等信息。INodes頁包含了關于頁本身的信息、值的范圍等。最后還有葉子節點，存儲著具體的數據行的全部數據。在示例中，葉子節點#5有57行記錄，共7524bytes。這行信息是具體的記錄，可以看到數據行內容。
因此， 使用InnoDB管理表和行，InnoDB會將數據以分支、頁和記錄形式進行組織。InnoDB可操的最小粒度是頁，頁加載進內存后才會通過掃描頁獲取行數據（即示例中的record）。
3 頁的內部原理(page internals)
數據頁的數據會按照主鍵的順序來排序，這也是我們在設計表主鍵時設置為AUTO_INCREMENT的原因，這樣在頻繁插入時，寫入的數據盡可能的寫入相同的頁，寫滿后刷盤也可以是順序寫。
圖片
但是如果頁的數據比較小，就會導致磁盤和內存空間的浪費，因此，如果 頁的數據大小/頁大小 小于一定比例，就會做頁合并，這個值我們稱之為MERGE_THRESHOLD，默認值為50%。
圖片
當本頁數據寫滿后，就會從內存中申請新頁（next）進行寫入。
圖片
每個葉子節點都有著一個指向包含下一條（順序）記錄的頁的指針，這也是InnoDB可以實現自頂向下的遍歷和葉子節點順序范圍掃描的能力基礎。
4 頁合并（page merging）
當執行數據行刪除時，并沒有物理刪除，而是將改行數據標記（flaged）為刪除，允許被其他記錄聲明使用。
圖片
當頁中刪除的記錄達到MERGE_THRESHOLD（默認頁體積的50%），InnoDB確認最靠近的前后頁是否頁達到MERGE_THRESHOLD，如果也已經在限定值之下， 可以將兩個頁進行合并優化空間使用。如上圖，當page#5數據小于50%時，由于page#6數據量也是小于50%，因此會進行頁合并，合并后，page#6就會變為空頁，可以接納新數據。
圖片
圖片
在delete/update語句操作中都可能會誘發頁合并的發生，關聯到當前頁的相鄰頁。如果頁合并成功，在INFOMATION_SCHEMA.INNODB_METRICS中的index_page_merge_successful將會增加。
5 頁分裂（Page Splits)
假設有如下場景，page#10已經被填滿時，繼續插入數據，#10沒有足夠空間去容納新的記錄，根據“下一頁”邏輯，記錄應該由page#11負責，但是頁#11也已經滿了。
圖片
圖片
這時候的簡化邏輯為：
- 創建新頁#12；
- 判斷當前頁（page#10）可以從哪里進行分裂（記錄行里面）；
- 移動記錄行；
- 重新定義頁與頁之間的關系；
圖片
新的頁#12被創建。
圖片
此時的頁與頁之間的關系為：
- Page #10 will have Prev=9 and Next=12
- Page #12 Prev=10 and Next=11
- Page #11 Prev=12 and Next=13（page#13是后續順序插入新增的頁）；
這樣，B+樹水平方向的邏輯一致性仍然滿足，但是在物理存儲上頁可能是亂序的，大概率會落到不同的區。
不太清楚這里是否會有疑問，page#10和page#11雖然都已經寫滿，但是可能已經存在page#12，并且還有大量剩余空間，為什么不做數據遷移呢？這樣不就可以不插入新頁而導致大量的空間浪費了嗎？
雖然從理論上是可行的，但是在實操中，這時候InnoDB就需要先遍歷確認next page是否有空余位置，甚至是繼續遍歷直至找到有空余位置的頁，然后進行數據遷移，這個操作可能帶來大量遍歷的時間復雜度以及數據復制的IO操作，因此，方案不可行。
因此，我們可以總結：頁分裂可能發生在執行插入或者更新時，但是可能也會造成頁的錯位（dislocation），即落入不同的區。
InnoDB用INFORMATION_SCHEMA.INNODB_METRICS表來跟蹤頁的分裂數。可以查看其中的index_page_splits和index_page_reorg_attempts/successful統計。
當page#12和page#10的數據都低于MERGE_THRESHOLD時，這時候可以通過頁合并將數據合并回來。
另一種方式是使用OPTIMIZE重新整理表，可以將大量分布在不同區的頁理順，因此，也是一個很重量級和耗時的過程。
同時，不管是頁分裂還是頁合并，InnoDB都會在索引樹上加寫鎖（x-latch）。在操作頻繁的系統中這會是在隱患，可能會導致索引的鎖競爭（index latch contention）。如果表中沒有合并和分裂操作（也就是寫操作），稱之為“樂觀（optimistic）”更新，只需要使用讀鎖（S）。帶有合并或者分裂的操作稱之為“悲觀（pessimistic）”更新，使用寫鎖（X）。
