InnoDB如何存儲數(shù)據(jù)

MySQL支持多種存儲結(jié)構(gòu)，我們常用的就是InnoDB，前面我們在 前面的 " MySQL 的 NULL 值是怎么存放的 " 一文中已經(jīng)知道記錄是按照行來存儲的，數(shù)據(jù)讀取并不是以行為單位進行讀取的，因為這樣效率非常低，InnoDB 是以數(shù)據(jù)頁為單位進行讀取的。

也就是說，當(dāng)用戶只需要讀取一條記錄的時候，并不是將這個記錄從磁盤中讀出，而是以頁為單位，將記錄所在的頁整體讀入內(nèi)存。

InnoDB 數(shù)據(jù)頁默認(rèn)大小是16KB。

數(shù)據(jù)頁結(jié)構(gòu)分為7個部分，如下圖：

數(shù)據(jù)頁7個部分作用說明

File header

在 File Header 中有兩個指針，分別指向上一個數(shù)據(jù)頁和下一個數(shù)據(jù)頁，連接起來的頁相當(dāng)于一個雙向的鏈表，如下圖所示：

采用鏈表的結(jié)構(gòu)是讓數(shù)據(jù)頁之間不需要是物理上的連續(xù)的，而是邏輯上的連續(xù)。

記錄在頁中的存儲

數(shù)據(jù)頁的主要作用是存儲記錄，也就是數(shù)據(jù)庫的數(shù)據(jù)，所以重點說一下數(shù)據(jù)頁中的 User Records 是怎么組織數(shù)據(jù)的。

用戶插入數(shù)據(jù)的時候，記錄會按照行格式存儲到 User records 部分，在一開始的時候，沒有這一部分，每當(dāng)插入一條記錄的時候，都會從Free space 部分劃分到 User records 。

當(dāng) Free space 這部分的空間完全 被 User records這部分替換之后，也就代表著這個數(shù)據(jù)頁用完了。

過程如下：

數(shù)據(jù)頁中的記錄按照 主鍵 順序組成單向鏈表，單向鏈表的特點就是插入、刪除非常方便，但是檢索效率不高，最差的情況下需要遍歷鏈表上的所有節(jié)點才能完成檢索。InnoDB是這樣的嗎？ 答案：肯定不是啊！

page Directory(頁目錄)

我們平時在查找一本書中的某個內(nèi)容的時候，會怎么做呢？一般會先去看目錄，找到對應(yīng)的頁碼，然后就可以去對應(yīng)的頁碼頁看內(nèi)容了。InnoDB也實現(xiàn)了類似這樣一個目錄。

目錄創(chuàng)建過程如下

1. 將所有正常的記錄(包括 Infimum Supremum 記錄，但不包括已經(jīng)移除到垃圾鏈表的記錄)劃分為幾個組.

2. 每個組的最后一條記錄(也就是組內(nèi)最大的那條記錄)相當(dāng)于"帶頭大哥"組內(nèi)其余的記錄相當(dāng)于"小弟。帶頭大哥"記錄的頭信息中的 owned 屬性表示該組內(nèi)共有幾條記錄

3. 將每個組中最后一條記錄在頁面中的地址偏移量(就是該記錄的真實數(shù)據(jù)與頁面中個字節(jié)之間的距離〉單獨提取出來，按順序存儲到靠近頁尾部的地方，這個地方就是 Page Directory 。頁目錄中的這些地址偏移量稱為槽 (Slot) ，每個槽占用 2 個字節(jié)，頁目錄就是由多個槽組成的。

舉個例子

如下圖5 個槽的編號分別為 0，1，2，3，4，我想查找主鍵為 11 的用戶記錄：

• 先二分得出槽中間位是 (0+4)/2=2 ，2號槽里最大的記錄為 8。因為 11 > 8，所以需要從 2 號槽后繼續(xù)搜索記錄；
• 再使用二分搜索出 2 號和 4 槽的中間位是 (2+4)/2= 3，3 號槽里最大的記錄為 12。因為 11 < 12，所以主鍵為 11 的記錄在 3 號槽里；
• 這里有個問題，「槽對應(yīng)的值都是這個組的主鍵最大的記錄，如何找到組里最小的記錄」？比如槽 3 對應(yīng)最大主鍵是 12 的記錄，那如何找到最小記錄 9。解決辦法是：通過槽 3 找到 槽 2 對應(yīng)的記錄，也就是主鍵為 8 的記錄。主鍵為 8 的記錄的下一條記錄就是槽 3 當(dāng)中主鍵最小的 9 記錄，然后開始向下搜索 2 次，定位到主鍵為 11 的記錄，取出該條記錄的信息即為我們想要查找的內(nèi)容。

看到第三步的時候，可能有的同學(xué)會疑問，如果某個槽內(nèi)的記錄很多，然后因為記錄都是單向鏈表串起來的，那這樣在槽內(nèi)查找某個記錄的時間復(fù)雜度不就是 O(n) 了嗎？

這點不用擔(dān)心，InnoDB 對每個分組中的記錄條數(shù)都是有規(guī)定的，槽內(nèi)的記錄就只有幾條：

• 第一個分組中的記錄只能有 1 條記錄；
• 最后一個分組中的記錄條數(shù)范圍只能在 1-8 條之間；
• 剩下的分組中記錄條數(shù)范圍只能在 4-8 條之間。

從圖可以看到，頁目錄就是由多個槽組成的，槽相當(dāng)于分組記錄的索引。然后，因為記錄是按照「主鍵值」從小到大排序的，所以我們通過槽查找記錄時，可以使用二分法快速定位要查詢的記錄在哪個槽（哪個記錄分組），定位到槽后，再遍歷槽內(nèi)的所有記錄，找到對應(yīng)的記錄，無需從最小記錄開始遍歷整個頁中的記錄鏈表。

B+ 樹是如何進行查詢

上面都是在說一個數(shù)據(jù)頁中的記錄檢索，因為一個數(shù)據(jù)頁中的記錄是有限的，且主鍵值是有序的，所以通過對所有記錄進行分組，然后將組號（槽號）存儲到頁目錄，使其起到索引作用，通過二分查找的方法快速檢索到記錄在哪個分組，來降低檢索的時間復(fù)雜度。

當(dāng)我們需要存儲大量的記錄時，就需要多個數(shù)據(jù)頁，這時我們就需要考慮如何建立合適的索引，才能方便定位記錄所在的頁。

為了解決這個問題，InnoDB 采用了 B+ 樹作為索引。磁盤的 I/O 操作次數(shù)對索引的使用效率至關(guān)重要，因此在構(gòu)造索引的時候，我們更傾向于采用“矮胖”的 B+ 樹數(shù)據(jù)結(jié)構(gòu)，這樣所需要進行的磁盤 I/O 次數(shù)更少，而且 B+ 樹 更適合進行關(guān)鍵字的范圍查詢。

InnoDB 里的 B+ 樹中的每個節(jié)點都是一個數(shù)據(jù)頁，結(jié)構(gòu)示意圖如下：

通過上圖，我們看出 B+ 樹的特點：

• 只有葉子節(jié)點（最底層的節(jié)點）才存放了數(shù)據(jù)，非葉子節(jié)點（其他上層節(jié)）僅用來存放目錄項作為索引。
• 非葉子節(jié)點分為不同層次，通過分層來降低每一層的搜索量；
• 所有節(jié)點按照索引鍵大小排序，構(gòu)成一個雙向鏈表，便于范圍查詢；

我們再看看 B+ 樹如何實現(xiàn)快速查找主鍵為 6 的記錄，以上圖為例子：

• 從根節(jié)點開始，通過二分法快速定位到符合頁內(nèi)范圍包含查詢值的頁，因為查詢的主鍵值為 6，在[1, 7)范圍之間，所以到頁 30 中查找更詳細的目錄項；
• 在非葉子節(jié)點（頁30）中，繼續(xù)通過二分法快速定位到符合頁內(nèi)范圍包含查詢值的頁，主鍵值大于 5，所以就到葉子節(jié)點（頁16）查找記錄；
• 接著，在葉子節(jié)點（頁16）中，通過槽查找記錄時，使用二分法快速定位要查詢的記錄在哪個槽（哪個記錄分組），定位到槽后，再遍歷槽內(nèi)的所有記錄，找到主鍵為 6 的記錄。

可以看到，在定位記錄所在哪一個頁時，也是通過二分法快速定位到包含該記錄的頁。定位到該頁后，又會在該頁內(nèi)進行二分法快速定位記錄所在的分組（槽號），最后在分組內(nèi)進行遍歷查找。

總結(jié)

• InnoDB 的數(shù)據(jù)是按「數(shù)據(jù)頁」為單位來讀寫的，默認(rèn)數(shù)據(jù)頁大小為 16 KB。每個數(shù)據(jù)頁之間通過雙向鏈表的形式組織起來，物理上不連續(xù)，但是邏輯上連續(xù)。
• 數(shù)據(jù)頁內(nèi)包含用戶記錄，每個記錄之間用單向鏈表的方式組織起來，為了加快在數(shù)據(jù)頁內(nèi)高效查詢記錄，設(shè)計了一個頁目錄，頁目錄存儲各個槽（分組），且主鍵值是有序的，于是可以通過二分查找法的方式進行檢索從而提高效率。
• 為了高效查詢記錄所在的數(shù)據(jù)頁，InnoDB 采用 b+ 樹作為索引，每個節(jié)點都是一個數(shù)據(jù)頁。