為什么MySQL索引要用B+tree？

前言

當你在遇到了一條慢?SQL?需要進行優(yōu)化時，你第一時間能想到的優(yōu)化手段是什么？

大部分人第一反應可能都是添加索引，在大多數(shù)情況下面，索引能夠?qū)⒁粭l?SQL?語句的查詢效率提高幾個數(shù)量級。

索引的本質(zhì)：用于快速查找記錄的一種數(shù)據(jù)結(jié)構(gòu)。

索引的常用數(shù)據(jù)結(jié)構(gòu)：

二叉樹

紅黑樹

Hash 表

B-tree?（B樹，并不叫什么B減樹）

B+tree

數(shù)據(jù)結(jié)構(gòu)圖形化網(wǎng)址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查詢

大家知道?select * from t where col = 88?這么一條?SQL?語句如果不走索引進行查找的話，正常地查就是全表掃描：從表的第一行記錄開始逐行找，把每一行的?col?字段的值和?88?進行對比，這明顯效率是很低的。

而如果走索引的話，查詢的流程就完全不一樣了（假設(shè)現(xiàn)在用一棵平衡二叉樹數(shù)據(jù)結(jié)構(gòu)存儲我們的索引列）

此時該二叉樹的存儲結(jié)構(gòu)（Key - Value）：Key 就是索引字段的數(shù)據(jù)，Value 就是索引所在行的磁盤文件地址。

當最后找到了?88?的時候，就可以把它的 Value 對應的磁盤文件地址拿出來，然后就直接去磁盤上去找這一行的數(shù)據(jù)，這時候的速度就會比全表掃描要快很多。

但實際上?MySQL?底層并沒有用二叉樹來存儲索引數(shù)據(jù)，是用的?B+tree（B+樹）。

為什么不采用二叉樹

假設(shè)此時用普通二叉樹記錄?id?索引列，我們在每插入一行記錄的同時還要維護二叉樹索引字段。

此時當我要找?id = 7?的那條數(shù)據(jù)時，它的查找過程如下：

此時找?id = 7?這一行記錄時找了?7?次，和我們?nèi)頀呙枰矝]什么很大區(qū)別。顯而易見，二叉樹對于這種依次遞增的數(shù)據(jù)列其實是不適合作為索引的數(shù)據(jù)結(jié)構(gòu)。

為什么不采用 Hash 表

“

Hash 表：一個快速搜索的數(shù)據(jù)結(jié)構(gòu)，搜索的時間復雜度 O(1)

Hash 函數(shù)：將一個任意類型的 key，可以轉(zhuǎn)換成一個 int 類型的下標

”

假設(shè)此時用 Hash 表記錄?id?索引列，我們在每插入一行記錄的同時還要維護 Hash 表索引字段。

這時候開始查找?id = 7?的樹節(jié)點僅找了?1?次，效率非常高了。

但?MySQL?的索引依然不采用能夠精準定位的Hash 表。因為它不適用于范圍查詢。

為什么不采用紅黑樹

“

紅黑樹是一種特化的 AVL樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡；

若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹。

”

假設(shè)此時用紅黑樹記錄?id?索引列，我們在每插入一行記錄的同時還要維護紅黑樹索引字段。

插入過程中會發(fā)現(xiàn)它與普通二叉樹不同的是當一棵樹的左右子樹高度差 > 1 時，它會進行自旋操作，保持樹的平衡。

這時候開始查找?id = 7?的樹節(jié)點只找了?3?次，比所謂的普通二叉樹還是要更快的。

但?MySQL?的索引依然不采用能夠精確定位和范圍查詢都優(yōu)秀的紅黑樹。

因為當?MySQL?數(shù)據(jù)量很大的時候，索引的體積也會很大，可能內(nèi)存放不下，所以需要從磁盤上進行相關(guān)讀寫，如果樹的層級太高，則讀寫磁盤的次數(shù)（I/O交互）就會越多，性能就會越差。

B-tree

“

紅黑樹目前的唯一不足點就是樹的高度不可控，所以現(xiàn)在我們的切入點就是樹的高度。

目前一個節(jié)點是只分配了一個存儲 1 個元素，如果要控制高度，我們就可以把一個節(jié)點分配的空間更大一點，讓它橫向存儲多個元素，這個時候高度就可控了。這么個改造過程，就變成了?B-tree。

”

B-tree?是一棵絕對平衡的多路樹。它的結(jié)構(gòu)中還有兩個概念

“

度（Degree）：一個節(jié)點擁有的子節(jié)點（子樹）的數(shù)量。（有的地方是以度來說明?B-tree?的，這里解釋一下）

階（order）：一個節(jié)點的子節(jié)點的最大個數(shù)。（通常用?m?表示）

關(guān)鍵字：數(shù)據(jù)索引。

”

一棵 m 階?B-tree?是一棵平衡的 m 路搜索樹。它可能是空樹，或者滿足以下特點：

除根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有??個子節(jié)點；

為 m / 2 然后向上取整

每個非根節(jié)點所包含的關(guān)鍵字個數(shù) j 滿足：?- 1 ≤ j ≤ m - 1；

節(jié)點的關(guān)鍵字從左到右遞增排列，有 k 個關(guān)鍵字的非葉子節(jié)點正好有 (k + 1) 個子節(jié)點；

所有的葉子結(jié)點都位于同一層。

名字取義（題外話，放松一下）

以下摘自維基百科

魯?shù)婪颉ぐ轄枺≧udolf Bayer）和 艾華·M·麥克雷（Ed M. McCreight）于1972年在波音研究實驗室（Boeing Research Labs）工作時發(fā)明了?B-tree，但是他們沒有解釋 B 代表什么意義（如果有的話）。

道格拉斯·科默爾（Douglas Comer）解釋說：兩位作者從來都沒解釋過?B-tree?的原始意義。我們可能覺得 balanced, broad 或 bushy 可能適合。其他人建議字母 B 代表 Boeing。源自于他的贊助，不過，看起來把?B-tree?當作 Bayer 樹更合適些。

高德納（Donald Knuth）在他1980年5月發(fā)表的題為 "CS144C classroom lecture about disk storage and B-trees" 的論文中推測了?B-tree?的名字取義，提出 B 可能意味 Boeing 或者 Bayer 的名字。

查找

B-tree?的查找其實和二叉樹很相似：

二叉樹是每個節(jié)點上有一個關(guān)鍵字和兩個分支，B-tree?上每個節(jié)點有 k 個關(guān)鍵字和 (k + 1) 個分支。

二叉樹的查找只考慮向左還是向右走，而?B-tree?中需要由多個分支決定。

B-tree?的查找分兩步：

首先查找節(jié)點，由于?B-tree?通常是在磁盤上存儲的所以這步需要進行磁盤IO操作；

查找關(guān)鍵字，當找到某個節(jié)點后將該節(jié)點讀入內(nèi)存中然后通過順序或者折半查找來查找關(guān)鍵字。若沒有找到關(guān)鍵字，則需要判斷大小來找到合適的分支繼續(xù)查找。

操作流程

現(xiàn)在需要查找元素：88

第一次：磁盤IO

第二次：磁盤IO

第三次：磁盤IO

然后這有一次內(nèi)存比對，分別跟 70 與 88 比對，最后找到 88。

從查找過程中發(fā)現(xiàn)，B-tree?比對次數(shù)和磁盤IO的次數(shù)其實和二叉樹相差不了多少，這么看來并沒有什么優(yōu)勢。

但是仔細一看會發(fā)現(xiàn)，比對是在內(nèi)存中完成中，不涉及到磁盤IO，耗時可以忽略不計。

另外?B-tree?中一個節(jié)點中可以存放很多的關(guān)鍵字（個數(shù)由階決定），相同數(shù)量的關(guān)鍵字在?B-tree?中生成的節(jié)點要遠遠少于二叉樹中的節(jié)點，相差的節(jié)點數(shù)量就等同于磁盤IO的次數(shù)。這樣到達一定數(shù)量后，性能的差異就顯現(xiàn)出來了。

插入

當?B-tree?要進行插入關(guān)鍵字時，都是直接找到葉子節(jié)點進行操作。

根據(jù)要插入的關(guān)鍵字查找到待插入的葉子節(jié)點；

因為一個節(jié)點的子節(jié)點的最大個數(shù)（階）為 m，所以需要判斷當前節(jié)點關(guān)鍵字的個數(shù)是否小于 (m - 1)。

是：直接插入

否：發(fā)生節(jié)點分裂，以節(jié)點的中間的關(guān)鍵字將該節(jié)點分為左右兩部分，中間的關(guān)鍵字放到父節(jié)點中即可。

操作流程

比如我們現(xiàn)在需要在 Max Degree（階）為 3 的?B-tree插入元素：72

查找待插入的葉子節(jié)點

節(jié)點分裂：本來應該和 [70,88] 在同一個磁盤塊上，但是當一個節(jié)點有 3 個關(guān)鍵字的時候，它就有可能有 4 個子節(jié)點，就超過了我們所定義限制的最大度數(shù) 3，所以此時必須進行分裂：以中間關(guān)鍵字為界將節(jié)點一分為二，產(chǎn)生一個新節(jié)點，并把中間關(guān)鍵字上移到父節(jié)點中。

Tip?: 當中間關(guān)鍵字有兩個時，通常將左關(guān)鍵字進行上移分裂。

刪除

刪除操作就會比查找和插入要麻煩一些，因為要被刪除的關(guān)鍵字可能在葉子節(jié)點上，也可能不在，而且刪除后還可能導致?B-tree?的不平衡，又要進行合并、旋轉(zhuǎn)等操作去保持整棵樹的平衡。

隨便拿棵樹（5 階）舉例子

情況一：直接刪除葉子節(jié)點的元素

刪除目標：50

查找元素 50 位置

在 [36, 50, 63] 節(jié)點移除 50 后，依然符合?B-tree?對節(jié)點內(nèi)關(guān)鍵字的要求：

┌m/2┐?-?1?≤?關(guān)鍵字個數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?3?-?1?≤?5?-?1

2?≤?2?≤?4?

?

?

刪除完成

情況二：刪除葉子節(jié)點的元素后合并+旋轉(zhuǎn)

刪除目標：11

查找元素 11 位置

在 [10, 11] 節(jié)點移除 11 后，違背?B-tree?對節(jié)點內(nèi)關(guān)鍵字的要求：

?

?

┌m/2┐?-?1?≤?關(guān)鍵字個數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?2?-?1?≤?5?-?1

2?≤?1?≤?4?

?

?

在它只剩1個關(guān)鍵字后，需要向兄弟節(jié)點借元素，這時候右兄弟有多的，它說：我愿意把14借給你

但不可能讓11和14放一起，因為?14 > 12?，這時候就要進行旋轉(zhuǎn)~

首先，將父節(jié)點的元素 12 移到該節(jié)點，然后 12 就讓位給14

這整個過程就是刪除葉子節(jié)點元素后的合并、旋轉(zhuǎn)操作

下面再來道菜

接著刪除 10

在 [10, 12] 節(jié)點移除 10 后，違背?B-tree?對節(jié)點內(nèi)關(guān)鍵字的要求

在它只剩1個關(guān)鍵字后，需要向兄弟節(jié)點借元素，這時候沒有兄弟有多的該怎么辦呢

首先，將父節(jié)點的元素 8 移到該節(jié)點，這時候 3、6、8、12 都小于14，就先把它們放一起

結(jié)果又發(fā)現(xiàn)父節(jié)點只剩個14了，它又違背了?B-tree?對節(jié)點內(nèi)關(guān)鍵字的要求，接著造?。?！

首先，還是將父節(jié)點的元素 20 移到該節(jié)點，這時候根節(jié)點都直接沒了，直接合并 14、20、26、72 關(guān)鍵字

在這整個過程包括刪除葉子節(jié)點和非葉子節(jié)點的合并、旋轉(zhuǎn)操作

情況三：刪除非葉子節(jié)點的元素后合并+旋轉(zhuǎn)

刪除目標：12

查找元素 12 位置

移除 12 后，違背?B-tree?對節(jié)點內(nèi)關(guān)鍵字的要求

對于非葉子節(jié)點元素的刪除，我們需要用后繼元素覆蓋要被刪除的元素，然后在后繼元素所在的葉子中刪除該后繼元素。

小總結(jié)

“

B-tree 主要用于文件系統(tǒng)以及部分數(shù)據(jù)庫索引，例如：MongoDB。

從查找效率考慮一般要求 B-tree 的階數(shù) m ≥ 3

B-tree 上算法的執(zhí)行時間主要由讀、寫磁盤的次數(shù)來決定，故一次I/O操作應讀寫盡可能多的信息。

因此 B-tree 的節(jié)點規(guī)模一般以一個磁盤頁為單位。一個結(jié)點包含的關(guān)鍵字及其孩子個數(shù)取決于磁盤頁的大小。

”

B+tree

上面這些例子相信大家對?B-tree?已經(jīng)有一定了解了，而?MySQL?底層用的索引數(shù)據(jù)結(jié)構(gòu)正是在?B-tree?上面做了一些改造，變成了?B+tree。

B+tree?和?B-tree?區(qū)別：

所有的子節(jié)點，一定會出現(xiàn)在葉子節(jié)點上

相鄰的葉子節(jié)點之間，會用一個雙向鏈表連接起來（關(guān)鍵）

非葉子節(jié)點只存儲索引，不存儲數(shù)據(jù)，就為放更多索引

相比?B-tree?來說，進行范圍查找時只需要查找兩個節(jié)點，進行遍歷就行。而?B-tree?需要獲取所有節(jié)點，相比之下?B+tree?效率更高。

這里其實這個數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)頁畫的?B+tree?還是不夠清晰，只是畫了個大概，下面我們就來看看它底層實際具體的數(shù)據(jù)結(jié)構(gòu)

每個節(jié)點都被稱作一個磁盤頁

B+tree 的葉子節(jié)點包含所有索引數(shù)據(jù)，在非葉子節(jié)點會存儲不存儲數(shù)據(jù)，只存儲索引，從而來組成一棵 B+tree。

查找

B+tree?最大的優(yōu)勢就在查找上，主要是范圍查詢更加明顯。

“

B-tree 節(jié)點中的每個關(guān)鍵字都有數(shù)據(jù)，而 B+tree 中間節(jié)點沒有數(shù)據(jù)，只有索引；這就意味著相同大小的磁盤頁可以放更多的節(jié)點元素，也就是在相同的數(shù)據(jù)量下，I/O 操作更少

在范圍查詢上，B-tree 需要先找到指定范圍內(nèi)的下限，再找到上限，有了這兩個過程后再取出它們之間的元素。

B+tree 因為葉子節(jié)點通過雙向鏈表進行連接，找到指定范圍內(nèi)的下限后，直接通過鏈表順序遍歷就行，這樣就方便很多了。

”

在查詢單個關(guān)鍵字上，和?B-tree?差不多：先把通過磁盤 I/O 找到節(jié)點，再把節(jié)點加載到內(nèi)存中進行內(nèi)部關(guān)鍵字比對，然后通過大小關(guān)系再決定接下來走哪個分支。

但是差別就在于?B+tree?的高度更加可控一些。MySQL?默認給一個磁盤頁數(shù)據(jù)分配的大小是?16KB，也就是 16 × 1024 = 16384 字節(jié)

官網(wǎng)說明：https://dev.mysql.com/doc/refman/5.7/en/innodb-physical-structure.html

證明：直接在數(shù)據(jù)庫中通過?SQL?語句?show GLOBAL STATUS LIKE 'INNODB_page_size'進行驗證

當我們的葉子節(jié)點全部撐滿之后，可以來算一算它樹的高度。

我們拿阿里的《Java 開發(fā)手冊》嵩山版中對表主鍵的要求進行舉例

bigint?大概占?8Byte，索引旁邊放指向下一節(jié)點的磁盤文件地址那塊是6Byte，是?MySQL?底層寫死了的。

通過計算：16384 Byte / (8+6) Byte ≈ 1170，也就是說一個節(jié)點設(shè)置?16KB?大小的話可以放 1170個索引。

葉子節(jié)點一個關(guān)鍵字占用1KB時，那一個節(jié)點就可以放16個元素，當整棵樹葉子節(jié)點全部都被撐滿時，通過計算?1170 × 1170 × 16 = 21902400

最后結(jié)果為2千多萬，樹的高度才為3，也就是我們要的高度可控。這也就是為什么?MySQL?的表有上千萬數(shù)據(jù)的情況下，查詢效率依然快的原因。

插入

插入還是挺簡單的：當節(jié)點內(nèi)元素數(shù)量大于 (m-1) 時，按中間元素分裂成左右兩部分，中間元素分裂到父節(jié)點當做索引存儲，本身中間元素也還會分裂右邊這一部分的。

下面以5階(m)舉

操作流程

第一次在空樹中插入 1

再依次插入 2,3,4

插入 5

當插入關(guān)鍵字 5 時，此時節(jié)點內(nèi)元素數(shù)量大于 (5-1) ，即超過了4個，這時候就要進行分裂；

以中間元素分裂，中間元素分裂到父節(jié)點當做索引存儲，由于葉子節(jié)點包含所有索引數(shù)據(jù)，所以本身它還會分裂至右邊部分。

這個過程是在葉子節(jié)點上進行分裂操作

下面再來個插入后的非葉子節(jié)點分裂操作（大差不差）

在以下的基礎(chǔ)上插入關(guān)鍵字：13

關(guān)鍵字13 插入到 [9, 10, 11, 12, 13] 后節(jié)點內(nèi)元素數(shù)量超過了4個，準備進行分裂；

以中間元素(11)分裂，中間元素分裂到父節(jié)點當做索引存儲，本身它也還會分裂右邊部分。

關(guān)鍵字11 被挪到父節(jié)點去之后，節(jié)點內(nèi)元素數(shù)量超過了4個，又要準備進行分裂

以中間元素(7)分裂，中間元素分裂到父節(jié)點當做（冗余）索引存儲。

插入完畢

刪除

在對應節(jié)點刪除目標關(guān)鍵字后，一樣需要看看節(jié)點內(nèi)剩余關(guān)鍵字是否符合：?- 1 ≤ 關(guān)鍵字個數(shù) ≤ m - 1

符合直接刪除就行，不符合就和?B-tree?一樣需要向兄弟節(jié)點借元素，不過會比?B-tree?稍簡單一點點

因為葉子節(jié)點（雙向鏈表）之間有指針關(guān)聯(lián)著，可以不需要再找它們的父節(jié)點了，直接通過兄弟節(jié)點進行移動，然后再更新父節(jié)點；

如果兄弟節(jié)點內(nèi)元素沒有多余的關(guān)鍵字，那就直接將當前節(jié)點和兄弟節(jié)點合并，再刪除父節(jié)點中的關(guān)鍵字。

操作流程

目標刪除元素：14

刪除 14 關(guān)鍵字后，它所在的節(jié)點只剩 13 一個關(guān)鍵字了

?

?

┌m/2┐?-?1?≤?關(guān)鍵字個數(shù)?≤?m?-?1

┌5/2┐?-?1?≤?2?-?1?≤?5?-?1

2?≤?1?≤?4?

?

?

準備借元素！

直接通過右兄弟節(jié)點（只有它有富余）進行移動，然后再更新父節(jié)點的索引

刪除成功后

接著刪除元素：16

刪除 16 關(guān)鍵字后，它所在的節(jié)點只剩 17 一個關(guān)鍵字了，又要準備借元素；

這時候兄弟節(jié)點都沒有多的，就直接把它和兄弟節(jié)點合并，再刪除父節(jié)點中的關(guān)鍵字

合并關(guān)鍵字 [13, 15, 17] ，在刪除父節(jié)點中的關(guān)鍵字 16

刪除成功后

總 結(jié)

“

單個節(jié)點存儲越多的元素，自然在整個過程中的磁盤I/O交互就越少；

相對 B-tree 來說，所有的查詢最終都會找到葉子節(jié)點，這也是 B+tree 性能穩(wěn)定的一個體現(xiàn)；

所有葉子節(jié)點通過雙向鏈表相連，范圍查詢非常方便，這也是 B+tree 最明顯的優(yōu)勢。

”

編輯：黃飛

?