本文為摘錄文章，如有錯(cuò)誤，請指正。文章是以MySQL5.7版本進(jìn)行說明，和現(xiàn)有版本可能會有一定差距，但是數(shù)據(jù)頁的設(shè)計(jì)基本沒有發(fā)生過變化，因此，可以作為學(xué)習(xí)參考。原文為2017年發(fā)表的一篇文章：《InnoDB Page Merging and Page Splitting - Percona Database Performance Blog》。

1 文件表（File-Table）結(jié)構(gòu)

在MySQL5.7創(chuàng)建windmills庫（schema）和wmills表，在文件目錄（/var/lib/mysql）有如下內(nèi)容：

data/
  windmills/
      wmills.ibd
      wmills.frm

原因是從MySQL5.6開始innodb_file_per_table參數(shù)默認(rèn)設(shè)置為1，即：每個(gè)表都會單獨(dú)作為一個(gè)文件存儲（如果有分區(qū)，可能有多個(gè)文件）。如果配置為0，則所有的表都是寫入公共表空間。

• vmills.ibd文件由多個(gè)段（segments）組成，每個(gè)段和一個(gè)索引有關(guān)；
• 段由多個(gè)區(qū)構(gòu)成，區(qū)僅存于段內(nèi)，每個(gè)區(qū)的默認(rèn)固定大小為1MB（頁體積默認(rèn)情況下）；
• 區(qū)是由很多數(shù)據(jù)頁構(gòu)成，默認(rèn)大小為16KB，即一個(gè)分區(qū)最多由64個(gè)數(shù)據(jù)頁構(gòu)成。
• 數(shù)據(jù)頁可以容納2-N行數(shù)據(jù)行，行的數(shù)量取決于數(shù)據(jù)行的大?。籌nnoDB要求頁至少要有兩行，因此行的大小最多為8000bytes。
• 文件的結(jié)構(gòu)不會隨著數(shù)據(jù)行的刪除而變化，但是段會跟著區(qū)的變化而變化；

圖片

2 根、分支和葉子(Roots,Branches and Leaves)

每個(gè)頁（邏輯上指的是主鍵索引的葉子節(jié)點(diǎn)）包含2-N行數(shù)據(jù)行，根據(jù)主鍵排列，樹有著特殊的頁區(qū)管理不同的分支，即內(nèi)部節(jié)點(diǎ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")

表結(jié)構(gòu)為：

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+樹的根節(jié)點(diǎn)就是查詢的根節(jié)點(diǎn)，如圖的#3就是根節(jié)點(diǎn)。根節(jié)點(diǎn)（頁）包含了索引ID、INodes數(shù)量等信息。INodes頁包含了關(guān)于頁本身的信息、值的范圍等。最后還有葉子節(jié)點(diǎn)，存儲著具體的數(shù)據(jù)行的全部數(shù)據(jù)。在示例中，葉子節(jié)點(diǎn)#5有57行記錄，共7524bytes。這行信息是具體的記錄，可以看到數(shù)據(jù)行內(nèi)容。

因此， 使用InnoDB管理表和行，InnoDB會將數(shù)據(jù)以分支、頁和記錄形式進(jìn)行組織。InnoDB可操的最小粒度是頁，頁加載進(jìn)內(nèi)存后才會通過掃描頁獲取行數(shù)據(jù)（即示例中的record）。

3 頁的內(nèi)部原理(page internals)

數(shù)據(jù)頁的數(shù)據(jù)會按照主鍵的順序來排序，這也是我們在設(shè)計(jì)表主鍵時(shí)設(shè)置為AUTO_INCREMENT的原因，這樣在頻繁插入時(shí)，寫入的數(shù)據(jù)盡可能的寫入相同的頁，寫滿后刷盤也可以是順序?qū)憽?/p>

圖片

但是如果頁的數(shù)據(jù)比較小，就會導(dǎo)致磁盤和內(nèi)存空間的浪費(fèi)，因此，如果 頁的數(shù)據(jù)大小/頁大小 小于一定比例，就會做頁合并，這個(gè)值我們稱之為MERGE_THRESHOLD，默認(rèn)值為50%。

圖片

當(dāng)本頁數(shù)據(jù)寫滿后，就會從內(nèi)存中申請新頁（next）進(jìn)行寫入。

圖片

每個(gè)葉子節(jié)點(diǎn)都有著一個(gè)指向包含下一條（順序）記錄的頁的指針，這也是InnoDB可以實(shí)現(xiàn)自頂向下的遍歷和葉子節(jié)點(diǎn)順序范圍掃描的能力基礎(chǔ)。

4 頁合并（page merging）

當(dāng)執(zhí)行數(shù)據(jù)行刪除時(shí)，并沒有物理刪除，而是將改行數(shù)據(jù)標(biāo)記（flaged）為刪除，允許被其他記錄聲明使用。

圖片

當(dāng)頁中刪除的記錄達(dá)到MERGE_THRESHOLD（默認(rèn)頁體積的50%），InnoDB確認(rèn)最靠近的前后頁是否頁達(dá)到MERGE_THRESHOLD，如果也已經(jīng)在限定值之下， 可以將兩個(gè)頁進(jìn)行合并優(yōu)化空間使用。如上圖，當(dāng)page#5數(shù)據(jù)小于50%時(shí)，由于page#6數(shù)據(jù)量也是小于50%，因此會進(jìn)行頁合并，合并后，page#6就會變?yōu)榭枕?，可以接納新數(shù)據(jù)。

圖片

圖片

在delete/update語句操作中都可能會誘發(fā)頁合并的發(fā)生，關(guān)聯(lián)到當(dāng)前頁的相鄰頁。如果頁合并成功，在INFOMATION_SCHEMA.INNODB_METRICS中的index_page_merge_successful將會增加。

5 頁分裂（Page Splits)

假設(shè)有如下場景，page#10已經(jīng)被填滿時(shí)，繼續(xù)插入數(shù)據(jù)，#10沒有足夠空間去容納新的記錄，根據(jù)“下一頁”邏輯，記錄應(yīng)該由page#11負(fù)責(zé)，但是頁#11也已經(jīng)滿了。

圖片

圖片

這時(shí)候的簡化邏輯為：

1. 創(chuàng)建新頁#12；
2. 判斷當(dāng)前頁（page#10）可以從哪里進(jìn)行分裂（記錄行里面）；
3. 移動記錄行；
4. 重新定義頁與頁之間的關(guān)系；

圖片

新的頁#12被創(chuàng)建。

圖片

此時(shí)的頁與頁之間的關(guān)系為：

• 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是后續(xù)順序插入新增的頁）；

這樣，B+樹水平方向的邏輯一致性仍然滿足，但是在物理存儲上頁可能是亂序的，大概率會落到不同的區(qū)。

不太清楚這里是否會有疑問，page#10和page#11雖然都已經(jīng)寫滿，但是可能已經(jīng)存在page#12，并且還有大量剩余空間，為什么不做數(shù)據(jù)遷移呢？這樣不就可以不插入新頁而導(dǎo)致大量的空間浪費(fèi)了嗎？

雖然從理論上是可行的，但是在實(shí)操中，這時(shí)候InnoDB就需要先遍歷確認(rèn)next page是否有空余位置，甚至是繼續(xù)遍歷直至找到有空余位置的頁，然后進(jìn)行數(shù)據(jù)遷移，這個(gè)操作可能帶來大量遍歷的時(shí)間復(fù)雜度以及數(shù)據(jù)復(fù)制的IO操作，因此，方案不可行。

因此，我們可以總結(jié)：頁分裂可能發(fā)生在執(zhí)行插入或者更新時(shí)，但是可能也會造成頁的錯(cuò)位（dislocation），即落入不同的區(qū)。

InnoDB用INFORMATION_SCHEMA.INNODB_METRICS表來跟蹤頁的分裂數(shù)?？梢圆榭雌渲械膇ndex_page_splits和index_page_reorg_attempts/successful統(tǒng)計(jì)。

當(dāng)page#12和page#10的數(shù)據(jù)都低于MERGE_THRESHOLD時(shí)，這時(shí)候可以通過頁合并將數(shù)據(jù)合并回來。

另一種方式是使用OPTIMIZE重新整理表，可以將大量分布在不同區(qū)的頁理順，因此，也是一個(gè)很重量級和耗時(shí)的過程。

同時(shí)，不管是頁分裂還是頁合并，InnoDB都會在索引樹上加寫鎖（x-latch）。在操作頻繁的系統(tǒng)中這會是在隱患，可能會導(dǎo)致索引的鎖競爭（index latch contention）。如果表中沒有合并和分裂操作（也就是寫操作），稱之為“樂觀（optimistic）”更新，只需要使用讀鎖（S）。帶有合并或者分裂的操作稱之為“悲觀（pessimistic）”更新，使用寫鎖（X）。