前言

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

大部分人第一反應(yīng)可能都是添加索引，在大多數(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?語句如果不走索引進(jìn)行查找的話，正常地查就是全表掃描：從表的第一行記錄開始逐行找，把每一行的?col?字段的值和?88?進(jìn)行對比，這明顯效率是很低的。

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

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

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

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

為什么不采用二叉樹

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

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

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

為什么不采用 Hash 表

“

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

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

”

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

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

但?MySQL?的索引依然不采用能夠精準(zhǔn)定位的Hash 表。因?yàn)樗贿m用于范圍查詢。

為什么不采用紅黑樹

“

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

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

”

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

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

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

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

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

B-tree

“

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

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

”

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

“

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

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

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

”

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

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

為 m / 2 然后向上取整

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

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

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

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

以下摘自維基百科

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

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

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

查找

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

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

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

B-tree?的查找分兩步：

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

查找關(guān)鍵字，當(dāng)找到某個節(jié)點(diǎn)后將該節(jié)點(diǎn)讀入內(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ù)其實(shí)和二叉樹相差不了多少，這么看來并沒有什么優(yōu)勢。

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

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

插入

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

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

因?yàn)橐粋€節(jié)點(diǎn)的子節(jié)點(diǎn)的最大個數(shù)（階）為 m，所以需要判斷當(dāng)前節(jié)點(diǎn)關(guān)鍵字的個數(shù)是否小于 (m - 1)。

是：直接插入

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

操作流程

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

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

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

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

刪除

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

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

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

刪除目標(biāo)：50

查找元素 50 位置

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

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

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

2?≤?2?≤?4?

?

?

刪除完成

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

刪除目標(biāo)：11

查找元素 11 位置

在 [10, 11] 節(jié)點(diǎn)移除 11 后，違背?B-tree?對節(jié)點(diǎn)內(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é)點(diǎn)借元素，這時(shí)候右兄弟有多的，它說：我愿意把14借給你

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

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

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

下面再來道菜

接著刪除 10

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

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

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

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

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

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

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

刪除目標(biāo)：12

查找元素 12 位置

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

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

小總結(jié)

“

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

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

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

因此 B-tree 的節(jié)點(diǎn)規(guī)模一般以一個磁盤頁為單位。一個結(jié)點(diǎn)包含的關(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é)點(diǎn)，一定會出現(xiàn)在葉子節(jié)點(diǎn)上

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

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

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

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

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

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

查找

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

“

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

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

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

”

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

但是差別就在于?B+tree?的高度更加可控一些。MySQL?默認(rèn)給一個磁盤頁數(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'進(jìn)行驗(yàn)證

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

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

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

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

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

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

插入

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

下面以5階(m)舉

操作流程

第一次在空樹中插入 1

再依次插入 2,3,4

插入 5

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

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

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

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

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

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

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

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

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

插入完畢

刪除

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

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

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

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

操作流程

目標(biāo)刪除元素：14

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

?

?

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

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

2?≤?1?≤?4?

?

?

準(zhǔn)備借元素！

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

刪除成功后

接著刪除元素：16

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

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

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

刪除成功后

總 結(jié)

“

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

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

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

”

編輯：黃飛

?