[[440384]]

本文轉(zhuǎn)載自微信公眾號「小林coding」，作者小林coding 。轉(zhuǎn)載本文請聯(lián)系小林coding公眾號。

大家好，我是小林。

大家背八股文的時(shí)候，都知道 MySQL 里 InnoDB 存儲引擎是采用 B+ 樹來組織數(shù)據(jù)的。

這點(diǎn)沒錯(cuò)，但是大家知道 B+ 樹里的節(jié)點(diǎn)里存放的是什么呢?查詢數(shù)據(jù)的過程又是怎樣的?

這次，我們從數(shù)據(jù)頁的角度看 B+ 樹，看看每個(gè)節(jié)點(diǎn)長啥樣。

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

MySQL 支持多種存儲引擎，不同的存儲引擎，存儲數(shù)據(jù)的方式也是不同的，我們最常使用的是 InnoDB 存儲引擎，所以就跟大家圖解下InnoDB 是如何存儲數(shù)據(jù)的。

記錄是按照行來存儲的，但是數(shù)據(jù)庫的讀取并不以「行」為單位，否則一次讀取(也就是一次 I/O 操作)只能處理一行數(shù)據(jù)，效率會非常低。

因此，InnoDB 的數(shù)據(jù)是按「數(shù)據(jù)頁」為單位來讀寫的，也就是說，當(dāng)需要讀一條記錄的時(shí)候，并不是將這個(gè)記錄本身從磁盤讀出來，而是以頁為單位，將其整體讀入內(nèi)存。

數(shù)據(jù)庫的 I/O 操作的最小單位是頁，InnoDB 數(shù)據(jù)頁的默認(rèn)大小是 16KB，意味著數(shù)據(jù)庫每次讀寫都是以 16KB 為單位的，一次最少從磁盤中讀取 16K 的內(nèi)容到內(nèi)存中，一次最少把內(nèi)存中的 16K 內(nèi)容刷新到磁盤中。

數(shù)據(jù)頁包括七個(gè)部分，結(jié)構(gòu)如下圖：

這 7 個(gè)部分的作用如下圖：

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

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

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

數(shù)據(jù)頁中的記錄按照「主鍵」順序組成單向鏈表，單向鏈表的特點(diǎn)就是插入、刪除非常方便，但是檢索效率不高，最差的情況下需要遍歷鏈表上的所有節(jié)點(diǎn)才能完成檢索。

因此，數(shù)據(jù)頁中有一個(gè)頁目錄，起到記錄的索引作用，就像我們書那樣，針對書中內(nèi)容的每個(gè)章節(jié)設(shè)立了一個(gè)目錄，想看某個(gè)章節(jié)的時(shí)候，可以查看目錄，快速找到對應(yīng)的章節(jié)的頁數(shù)，而數(shù)據(jù)頁中的頁目錄就是為了能快速找到記錄。

那 InnoDB 是如何給記錄創(chuàng)建頁目錄的呢?頁目錄與記錄的關(guān)系如下圖：

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

• 將所有的記錄劃分成幾個(gè)組，這些記錄包括最小記錄和最大記錄，但不包括標(biāo)記為“已刪除”的記錄;
• 每個(gè)記錄組的最后一條記錄就是組內(nèi)最大的那條記錄，并且最后一條記錄的頭信息中會存儲該組一共有多少條記錄，作為 n_owned 字段(上圖中粉紅色字段)
• 頁目錄用來存儲每組最后一條記錄的地址偏移量，這些地址偏移量會按照先后順序存儲起來，每組的地址偏移量也被稱之為槽(slot)，每個(gè)槽相當(dāng)于指針指向了不同組的最后一個(gè)記錄。

從圖可以看到，頁目錄就是由多個(gè)槽組成的，槽相當(dāng)于分組記錄的索引。然后，因?yàn)橛涗浭前凑铡钢麈I值」從小到大排序的，所以我們通過槽查找記錄時(shí)，可以使用二分法快速定位要查詢的記錄在哪個(gè)槽(哪個(gè)記錄分組)，定位到槽后，再遍歷槽內(nèi)的所有記錄，找到對應(yīng)的記錄，無需從最小記錄開始遍歷整個(gè)頁中的記錄鏈表。

以上面那張圖舉個(gè)例子，5 個(gè)槽的編號分別為 0，1，2，3，4，我想查找主鍵為 11 的用戶記錄：

• 先二分得出槽中間位是 (0+4)/2=2 ，2號槽里最大的記錄為 8。因?yàn)?11 > 8，所以需要從 2 號槽后繼續(xù)搜索記錄;
• 再使用二分搜索出 2 號和 4 槽的中間位是 (2+4)/2= 3，3 號槽里最大的記錄為 12。因?yàn)?11 < 12，所以主鍵為 11 的記錄在 3 號槽里;
• 再從 3 號槽指向的主鍵值為 9 記錄開始向下搜索 2 次，定位到主鍵為 11 的記錄，取出該條記錄的信息即為我們想要查找的內(nèi)容。

看到第三步的時(shí)候，可能有的同學(xué)會疑問，如果某個(gè)槽內(nèi)的記錄很多，然后因?yàn)橛涗浂际菃蜗蜴湵泶饋淼?，那這樣在槽內(nèi)查找某個(gè)記錄的時(shí)間復(fù)雜度不就是 O(n) 了嗎?

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

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

B+ 樹是如何進(jìn)行查詢的?

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

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

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

更詳細(xì)的為什么采用 B+ 樹作為索引的原因可以看我之前寫的這篇：「索引為什么能提高查詢性能?」

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

通過上圖，我們看出 B+ 樹的特點(diǎn)：

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

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

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

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

聚集索引和二級索引

另外，索引又可以分成聚集索引和非聚集索引(二級索引)，它們區(qū)別就在于葉子節(jié)點(diǎn)存放的是什么數(shù)據(jù)：

• 聚集索引的葉子節(jié)點(diǎn)存放的是實(shí)際數(shù)據(jù)，所有完整的用戶記錄都存放在聚集索引的葉子節(jié)點(diǎn);
• 二級索引的葉子節(jié)點(diǎn)存放的是主鍵值，而不是實(shí)際數(shù)據(jù)。

因?yàn)楸淼臄?shù)據(jù)都是存放在聚集索引的葉子節(jié)點(diǎn)里，所以 InnoDB 存儲引擎一定會為表創(chuàng)建一個(gè)聚集索引，且由于數(shù)據(jù)在物理上只會保存一份，所以聚簇索引只能有一個(gè)。

InnoDB 在創(chuàng)建聚簇索引時(shí)，會根據(jù)不同的場景選擇不同的列作為索引：

• 如果有主鍵，默認(rèn)會使用主鍵作為聚簇索引的索引鍵;
• 如果沒有主鍵，就選擇第一個(gè)不包含 NULL 值的唯一列作為聚簇索引的索引鍵;
• 在上面兩個(gè)都沒有的情況下，InnoDB 將自動(dòng)生成一個(gè)隱式自增 id 列作為聚簇索引的索引鍵;

一張表只能有一個(gè)聚簇索引，那為了實(shí)現(xiàn)非主鍵字段的快速搜索，就引出了二級索引(非聚簇索引/輔助索引)，它也是利用了 B+ 樹的數(shù)據(jù)結(jié)構(gòu)，但是二級索引的葉子節(jié)點(diǎn)存放的是主鍵值，不是實(shí)際數(shù)據(jù)。

二級索引的 B+ 樹如下圖，數(shù)據(jù)部分為主鍵值：

因此，如果某個(gè)查詢語句使用了二級索引，但是查詢的數(shù)據(jù)不是主鍵值，這時(shí)在二級索引找到主鍵值后，需要去聚簇索引中獲得數(shù)據(jù)行，這個(gè)過程就叫作「回表」，也就是說要查兩個(gè) B+ 樹才能查到數(shù)據(jù)。不過，當(dāng)查詢的數(shù)據(jù)是主鍵值時(shí)，因?yàn)橹辉诙壦饕湍懿樵兊?，不用再去聚簇索引查，這個(gè)過程就叫作「索引覆蓋」，也就是只需要查一個(gè) B+ 樹就能找到數(shù)據(jù)。

總結(jié)

InnoDB 的數(shù)據(jù)是按「數(shù)據(jù)頁」為單位來讀寫的，默認(rèn)數(shù)據(jù)頁大小為 16 KB。每個(gè)數(shù)據(jù)頁之間通過雙向鏈表的形式組織起來，物理上不連續(xù)，但是邏輯上連續(xù)。

數(shù)據(jù)頁內(nèi)包含用戶記錄，每個(gè)記錄之間用單項(xiàng)鏈表的方式組織起來，為了加快在數(shù)據(jù)頁內(nèi)高效查詢記錄，設(shè)計(jì)了一個(gè)頁目錄，頁目錄存儲各個(gè)槽(分組)，且主鍵值是有序的，于是可以通過二分查找法的方式進(jìn)行檢索從而提高效率。

為了高效查詢記錄所在的數(shù)據(jù)頁，InnoDB 采用 b+ 樹作為索引，每個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)據(jù)頁。

如果葉子節(jié)點(diǎn)存儲的是實(shí)際數(shù)據(jù)的就是聚簇索引，一個(gè)表只能有一個(gè)聚簇索引;如果葉子節(jié)點(diǎn)存儲的不是實(shí)際數(shù)據(jù)，而是主鍵值則就是二級索引，一個(gè)表中可以有多個(gè)二級索引。

在使用二級索引進(jìn)行查找數(shù)據(jù)時(shí)，如果查詢的數(shù)據(jù)能在二級索引找到，那么就是「索引覆蓋」操作，如果查詢的數(shù)據(jù)不在二級索引里，就需要先在二級索引找到主鍵值，需要去聚簇索引中獲得數(shù)據(jù)行，這個(gè)過程就叫作「回表」。

關(guān)于索引的內(nèi)容還有很多，比如索引失效、索引優(yōu)化等等，這些內(nèi)容我下次在講啦!