InnoDB 為什么使用 B+樹(shù)實(shí)現(xiàn)索引？說(shuō)到這個(gè)話題，就需要先聊一聊 InnoDB 的索引類型有哪些？

InnoDB 中的索引類型

InnoDB 存儲(chǔ)引擎支持兩種常見(jiàn)的索引數(shù)據(jù)結(jié)構(gòu)：B+樹(shù)索引和哈希索引，其中 B+樹(shù)索引是目前關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中最為常見(jiàn)、最為高效的索引之一。

數(shù)據(jù)庫(kù)中的 B+樹(shù)索引可分為聚簇索引和非聚簇索引。聚簇索引按照每張表的主鍵構(gòu)建一個(gè) B+樹(shù)，其葉子節(jié)點(diǎn)記錄著表中每行記錄的所有值。只需訪問(wèn)葉子節(jié)點(diǎn)即可獲取整行記錄的信息。非聚簇索引的葉子節(jié)點(diǎn)中并不包含完整的行記錄信息，而僅包含索引值和對(duì)應(yīng)的主鍵值。

根據(jù)索引的唯一性，索引可分為唯一索引和普通索引。唯一索引要求索引列的值必須唯一，不可重復(fù)。

此外，在 MySQL 5.6 版本中引入了全文索引，在 5.7 版本及以后，通過(guò)使用 ngram 插件開(kāi)始支持中文全文搜索。

B+樹(shù)的特點(diǎn)

首先來(lái)看一下 B+樹(shù)的特點(diǎn)：

1. B+樹(shù)是一棵平衡樹(shù)，每個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度相同，從而提高了查找效率；
2. 所有關(guān)鍵字都存儲(chǔ)在 B+樹(shù)的葉子節(jié)點(diǎn)上，因此進(jìn)行范圍查詢時(shí)只需遍歷一次葉子節(jié)點(diǎn)即可；
3. 葉子節(jié)點(diǎn)按照關(guān)鍵字大小順序存放，因此能夠快速支持按關(guān)鍵字大小進(jìn)行排序；
4. 非葉子節(jié)點(diǎn)不存儲(chǔ)實(shí)際數(shù)據(jù)，這使得可以存儲(chǔ)更多的索引數(shù)據(jù)；
5. 非葉子節(jié)點(diǎn)使用指針連接子節(jié)點(diǎn)，從而能夠迅速支持范圍查詢和倒序查詢；
6. 葉子節(jié)點(diǎn)之間通過(guò)雙向鏈表連接，便于進(jìn)行范圍查詢。

圖片

使用 B+樹(shù)實(shí)現(xiàn)索引具有以下幾個(gè)優(yōu)點(diǎn)：

1. 支持范圍查詢：B+樹(shù)在執(zhí)行范圍查找時(shí)，只需從根節(jié)點(diǎn)遍歷至葉子節(jié)點(diǎn)，因?yàn)閿?shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)上，并且葉子節(jié)點(diǎn)之間有指針連接，便于進(jìn)行范圍查找。
2. 支持排序：B+樹(shù)的葉子節(jié)點(diǎn)按關(guān)鍵字順序存儲(chǔ)，能夠快速支持排序操作，提升排序效率。
3. 存儲(chǔ)更多的索引數(shù)據(jù)：由于非葉子節(jié)點(diǎn)僅存儲(chǔ)索引關(guān)鍵字而不存儲(chǔ)實(shí)際數(shù)據(jù)，可容納更多索引數(shù)據(jù)。
4. 減少 IO 操作：B+樹(shù)的葉子節(jié)點(diǎn)大小固定，一般設(shè)置為一頁(yè)大小，使得節(jié)點(diǎn)分裂和合并時(shí)的 IO 操作較少，只需讀取和寫(xiě)入一頁(yè)。
5. 利用磁盤(pán)預(yù)讀：節(jié)點(diǎn)大小固定有利于利用磁盤(pán)預(yù)讀特性，一次性讀取多個(gè)節(jié)點(diǎn)到內(nèi)存中，減少 IO 操作次數(shù)，提高查詢效率。
6. 優(yōu)化緩存利用：B+樹(shù)的非葉子節(jié)點(diǎn)僅存儲(chǔ)指向子節(jié)點(diǎn)的指針，不存儲(chǔ)數(shù)據(jù)，可使緩存容納更多索引數(shù)據(jù)，提高緩存命中率，加速查詢速度。

為什么不用紅黑樹(shù)或者 B 樹(shù)？

因?yàn)?B+樹(shù)的特點(diǎn)是只有葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，而非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，并且節(jié)點(diǎn)大小固定，葉子節(jié)點(diǎn)之間通過(guò)雙向鏈表鏈接，所以，使用 B+樹(shù)實(shí)現(xiàn)索引具有諸多優(yōu)勢(shì)，比如支持范圍查詢、有利于磁盤(pán)預(yù)讀、優(yōu)化排序等等。而這些是紅黑樹(shù)和 B 樹(shù)無(wú)法實(shí)現(xiàn)的。

B+樹(shù)索引和 Hash 索引有什么區(qū)別？

B+樹(shù)索引和哈希索引是常見(jiàn)的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)，它們之間存在以下幾個(gè)主要區(qū)別：

B+樹(shù)索引將索引列的值按大小排序后存儲(chǔ)，因此適合范圍查找和排序操作；而哈希索引則通過(guò)哈希函數(shù)計(jì)算索引列的值，得到一個(gè)桶的編號(hào)，然后將桶內(nèi)記錄保存在鏈表或樹(shù)結(jié)構(gòu)中。因此，哈希索引適合等值查詢，但不適合范圍查詢和排序操作。

在插入和刪除數(shù)據(jù)時(shí)，B+樹(shù)索引需要調(diào)整索引結(jié)構(gòu)，可能涉及頁(yè)分裂和頁(yè)合并等操作，因此維護(hù)成本較高；而哈希索引只需計(jì)算哈希值并操作鏈表中的記錄，維護(hù)成本相對(duì)較低。

B+樹(shù)索引在磁盤(pán)上有序存儲(chǔ)，可利用磁盤(pán)預(yù)讀提高區(qū)間查詢效率；而哈希索引在磁盤(pán)上無(wú)序存儲(chǔ)，可能需要隨機(jī)訪問(wèn)磁盤(pán)，導(dǎo)致查詢效率下降。

由于 B+樹(shù)索引在節(jié)點(diǎn)中存儲(chǔ)多個(gè)鍵值對(duì)，能充分利用磁盤(pán)塊空間，提高空間利用率；而哈希索引需要額外存儲(chǔ)哈希值和指針，空間利用率相對(duì)較低。