數(shù)據(jù)頁

我們都知道平時(shí)執(zhí)行crud的時(shí)候，都會(huì)從磁盤上加載數(shù)據(jù)頁到Buffer Pool的緩存頁里去，更新緩存頁后，由異步線程刷回磁盤的數(shù)據(jù)頁。

所以MySQL進(jìn)行數(shù)據(jù)操作的最小單位是數(shù)據(jù)頁，接下來就分析分析，數(shù)據(jù)頁到底長什么樣。

每個(gè)數(shù)據(jù)頁默認(rèn)16kb的大小，數(shù)據(jù)頁由多個(gè)部分組成，如下圖所示：

當(dāng)然這么多概念，阿星只會(huì)挑重點(diǎn)，循循漸進(jìn)的講，所以大家莫慌。

空閑空間

其實(shí)數(shù)據(jù)頁還未寫入數(shù)據(jù)時(shí)，是沒有數(shù)據(jù)行的，只有空閑空間，一旦寫入，空閑空間會(huì)減少一些，直到空閑空間耗盡，具體過程如下圖：

數(shù)據(jù)頁滿了，自然需要開辟新的數(shù)據(jù)頁出來存儲(chǔ)數(shù)據(jù)。

但是隨著數(shù)據(jù)頁多起來，它們?cè)趺粗郎弦豁撆c下一頁在那呢?

雙向鏈表

其實(shí)在數(shù)據(jù)頁文件頭中存放了特別多的信息，如當(dāng)前頁號(hào)、頁類型、所屬表空間、上一頁號(hào)、下一頁號(hào)等等。

所以數(shù)據(jù)頁是通過上下頁號(hào)，組成雙向鏈表，如下圖所示：

數(shù)據(jù)頁內(nèi)部會(huì)存儲(chǔ)一行一行的數(shù)據(jù)，每一行數(shù)據(jù)都會(huì)按照主鍵大小進(jìn)行排序存儲(chǔ)，同時(shí)每一行數(shù)據(jù)都有指針指向下一行數(shù)據(jù)，組成單向鏈表。

但是這個(gè)結(jié)構(gòu)并不高效，假設(shè)根據(jù)主鍵ID查詢數(shù)據(jù)，只能進(jìn)入數(shù)據(jù)頁，挨個(gè)挨個(gè)的對(duì)單向鏈表遍歷查詢。

所以要再加點(diǎn)料，把二分查找利用起來(不知道二分查找是什么，建議百度，這是最基礎(chǔ)算法)

數(shù)據(jù)頁目錄

這個(gè)料就是數(shù)據(jù)頁目錄部分，數(shù)據(jù)頁目錄存儲(chǔ)的內(nèi)容就是主鍵ID和行位置。

這樣就可以通過數(shù)據(jù)頁目錄走二分查找，快速定位到數(shù)據(jù)頁內(nèi)的數(shù)據(jù)行。

如果只有一個(gè)數(shù)據(jù)頁，倒沒啥問題，哪有成千上萬個(gè)數(shù)據(jù)頁呢，還是得一個(gè)一個(gè)進(jìn)數(shù)據(jù)頁，搜索數(shù)據(jù)頁目錄。

有沒有覺得，這似乎是在做全表掃描?

沒錯(cuò)，在沒有索引的情況下，數(shù)據(jù)庫就是這樣執(zhí)行的。

索引

如果沒有索引，查詢速度可以說是慢到驚人，一般是不能讓查詢走全表掃描的。

因此數(shù)據(jù)庫中的查詢，必須要運(yùn)用索引來加速。

頁分裂

在說索引之前，先說個(gè)前置知識(shí)，索引的核心基礎(chǔ)要求后一個(gè)數(shù)據(jù)頁的主鍵值都大于前面一個(gè)數(shù)據(jù)頁的主鍵值，如果你的主鍵是自增的，可以保證這一點(diǎn)。

但有時(shí)候主鍵并不是自增長的，可能會(huì)出現(xiàn)后一個(gè)數(shù)據(jù)頁的主鍵值小于前一個(gè)數(shù)據(jù)頁的主鍵值。

為了保證索引的核心基礎(chǔ)，有個(gè)交換行數(shù)據(jù)的過程，這個(gè)過程叫頁分裂。

過程如下

• 數(shù)據(jù)頁0的id=6行數(shù)據(jù)挪到數(shù)據(jù)頁1
• 數(shù)據(jù)頁1的頁目錄更新
• 數(shù)據(jù)頁1的id=3行數(shù)據(jù)挪到數(shù)據(jù)頁0
• 數(shù)據(jù)頁0的頁目錄更新

主鍵目錄

好了，現(xiàn)在我們以主鍵為例，創(chuàng)建一個(gè)主鍵索引，這個(gè)主鍵索引就是主鍵目錄，它會(huì)維護(hù)所有數(shù)據(jù)頁的最小主鍵值與對(duì)應(yīng)的頁號(hào)。

有了主鍵目錄的加持，那找數(shù)據(jù)就非常快了，過程如下

• 二分查找主鍵目錄，找到對(duì)應(yīng)的數(shù)據(jù)頁
• 進(jìn)入數(shù)據(jù)頁，二分查找數(shù)據(jù)頁目錄，找到對(duì)應(yīng)的行數(shù)據(jù)

可是又來一個(gè)新問題，表里的數(shù)據(jù)可能有幾百萬，幾千萬，甚至幾億條數(shù)據(jù)，會(huì)有大量的數(shù)據(jù)頁，意味著主鍵目錄要存儲(chǔ)大量的數(shù)據(jù)頁號(hào)和最小主鍵值。

可能主鍵目錄存儲(chǔ)不下，就算能存儲(chǔ)，海量的數(shù)據(jù)僅僅靠二分查找也很吃力。

所以InnoDB實(shí)際上是把主鍵目錄數(shù)據(jù)存儲(chǔ)在多個(gè)數(shù)據(jù)頁中，我們把這個(gè)數(shù)據(jù)頁稱為索引頁

索引頁

索引頁，顧名思義，就是存儲(chǔ)索引信息的數(shù)據(jù)頁，在數(shù)據(jù)頁的文件頭部，有頁類型來進(jìn)行區(qū)分。

索引頁會(huì)存儲(chǔ)兩類內(nèi)容，一類是最小主鍵值與索引頁號(hào)，另一類是最小主鍵值與數(shù)據(jù)頁號(hào)。

把大量的索引信息分散在多個(gè)索引頁中，再將多個(gè)索引頁組建成B+樹結(jié)構(gòu)，方便二分查找，結(jié)構(gòu)如下圖：

一直說InnoDB的索引是用B+樹來組成的，其實(shí)就是這個(gè)意思，當(dāng)然真實(shí)的B+樹不長這樣，這樣畫還是為了幫助大家理解。

現(xiàn)在整個(gè)搜索過程就十分簡單了

• 根據(jù)主鍵id二分查找索引頁
• 找到對(duì)應(yīng)索引頁，再二分查找數(shù)據(jù)頁
• 進(jìn)入數(shù)據(jù)頁，二分查找數(shù)據(jù)頁目錄，找到對(duì)應(yīng)的行數(shù)據(jù)

寫到這里就結(jié)束了，通過數(shù)據(jù)頁到最后的索引，體會(huì)這個(gè)優(yōu)化的過程，才是本文的重點(diǎn)，由于篇幅有限，索引的內(nèi)容后面會(huì)單獨(dú)講解。