本文為摘錄文章，如有錯(cuò)誤，請(qǐng)指正。文章是以MySQL5.7版本進(jìn)行說(shuō)明，和現(xiàn)有版本可能會(huì)有一定差距，但是數(shù)據(jù)頁(yè)的設(shè)計(jì)基本沒(méi)有發(fā)生過(guò)變化，因此，可以作為學(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庫(kù)（schema）和wmills表，在文件目錄（/var/lib/mysql）有如下內(nèi)容：

data/
  windmills/
      wmills.ibd
      wmills.frm

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

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

圖片

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

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

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

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

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

圖片

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

圖片

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

圖片

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

4 頁(yè)合并（page merging）

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

圖片

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

圖片

圖片

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

5 頁(yè)分裂（Page Splits)

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

圖片

圖片

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

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

圖片

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

圖片

此時(shí)的頁(yè)與頁(yè)之間的關(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ù)順序插入新增的頁(yè)）；

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

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

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

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

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

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

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

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