終於理解 MySQL 索引要用 B+tree ，而且還這麼快

mysql教學欄位介紹理解索引的B tree。

免費推薦：mysql教學(影片)

前言

當你現在遇到了一條慢SQL 需要進行最佳化時，你第一時間能想到的最佳化手段是什麼？

大部分人第一反應可能都是添加索引，在大多數情況下面，索引能夠將一條SQL 語句的查詢效率提高幾個數量級。

索引的本質：用於快速尋找記錄的一種資料結構。

索引的常用資料結構：

1. 二元樹
2. 紅黑樹
##Hash 表
4. B-tree（B樹，不叫什麼B減樹）
5. B tree

資料結構圖形化網址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查詢

大家知道

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

而如果走索引的話，查詢的流程就完全不一樣了（假設現在用一棵

平衡二元樹資料結構儲存我們的索引列）

此時該二元樹的儲存結構（Key - Value）：Key 是索引欄位的數據，Value 是索引所在行的磁碟檔案位址。

當最後找到了

88 的時候，就可以把它的Value 對應的磁碟檔案位址拿出來，然後就直接去磁碟上去找這一行的數據，這時候的速度就會比全表掃描快很多。

但

實際上 MySQL 底層並沒有用二元樹來儲存索引數據，是用的B tree（B 樹）。

為什麼不採用二元樹

假設此時用普通二元樹記錄

id 索引列，我們在每插入一行記錄的同時還要維護二元樹索引字段。

此時當我要找

id ​​= 7 的那條資料時，它的尋找過程如下：

#此時找

id ​​= 7 這行記錄時找了7 次，和我們全表掃描也沒什麼很大差別。顯而易見，二元樹對於這種依序遞增的資料列其實是不適合作為索引的資料結構。

為什麼不採用Hash 表

Hash 表：快速搜尋的資料結構，搜尋的時間複雜度O(1)

Hash 函數：將一個任意型別的key，可以轉換成一個int 類型的下標

假設此時用Hash 表記錄

id 索引列，我們在每插入一行記錄的同時還要維護Hash 表索引欄位。

這時候開始找

id ​​= 7 的樹節點只找了 1 次，效率非常高了。

但

MySQL 的索引仍然不採用能夠精確定位的Hash 表。因為它不適用於範圍查詢。

為什麼不採用紅黑樹

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

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

假設此時用紅黑樹記錄 id 索引列，我們在每插入一行記錄的同時也要維護紅黑樹索引欄位。

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

這時候開始找 id ​​= 7 的樹節點只找了 3 次，比所謂的普通二元樹還是要更快的。

但MySQL 的索引仍然不採用能夠精確定位和範圍查詢都優秀的紅黑樹。

因為當MySQL 資料量很大的時候，索引的體積也會很大，可能內存放不下，所以需要從磁碟上進行相關讀寫，如果樹的層級太高，則讀寫磁碟的次數（I/O互動）就會越多，效能就會越差。

B-tree

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

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

B-tree 是一顆絕對平衡的多路樹。它的結構中還有兩個概念

度（Degree）：一個節點擁有的子節點（子樹）的數量。 （有的地方是以度來說明B-tree 的，這裡解釋一下）

階（order）：一個節點的子節點的最大數。 （通常用 m 表示）

關鍵字：資料索引。

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

1. 除根節點和葉子節點外，其它每個節點至少有$\lceil \dfrac{m}{2}\rceil$

   ####################### #############################2#################### ######################m############################ ########################⌉############### 個子節點;###

   $\lceil {\displaystyle \frac{\mathrm{\#m}}{\mathrm{}}}\rceil$

2. ⌈${\displaystyle \frac{}{\mathrm{}}}\#2$m2

3. ⌉

###########################################################################################################如果######\lceil \dfrac{m}{2}\rceil###########################⌈##### ####################################2############## ############################m##################### ##############################⌉############### - 1 ≤ j ≤ m - 1;############節點的關鍵字從左到右遞增排列，有k 個關鍵字的非葉子節點剛好有(k 1) 個子節點；#### ########所有的葉子結點都位於同一層。 ############名字取義（題外話，放鬆一下）#########以下摘自維基百科#########魯道夫·拜爾（ Rudolf Bayer）和艾華·M·麥克雷（Ed M. McCreight）於1972年在波音研究實驗室（Boeing Research Labs）工作時發明了###B-tree###，但他們沒有解釋B 代表什麼意義（如果有的話）。 ######道格拉斯·科默爾（Douglas Comer）解釋說：兩位作者從來都沒解釋過 ###B-tree### 的原始意義。我們可能覺得 balanced, broad 或 bushy 可能適合。其他人建議字母 B 代表 Boeing。源自於他的贊助，不過，看起來把 ###B-tree### 當作 Bayer 樹更合適些。 ######高德納（Donald Knuth）在1980年5月發表的題為"CS144C classroom lecture about disk storage and B-trees" 的論文中推測了###B-tree### 的名字取義，提出B 可能意味Boeing 或Bayer 的名字。 ######查找#########B-tree### 的查找其實和二元樹很相似：######二元樹是每個節點上有一個關鍵字和兩個分支，###B-tree### 上每個節點有k 個關鍵字和(k 1) 個分支。 ######二元樹的查找只考慮向左或向右走，而 ###B-tree### 中需要由多個分支決定。 #########B-tree### 的找出分兩步驟：###

1. 先找節點，由於B-tree 通常是在磁碟上儲存的所以這步驟需要進行磁碟IO操作；
2. 找出關鍵字，當找到某個節點後將該節點讀入記憶體中然後通過順序或折半查找來查找關鍵字。若沒有找到關鍵字，則需要判斷大小才能找到適當的分支繼續尋找。

操作流程

現在需要尋找元素：88

第一次：磁碟IO

第二次：磁碟IO

第三次：磁碟IO

然後這有一次記憶體比對，分別跟70 與88 比對，最後找到88。

從查找過程中發現，B-tree 比對次數和磁碟IO的次數其實和二元樹相差不了多少，這麼看來並沒有什麼優勢。

但是仔細一看會發現，比對是在記憶體中完成中，不涉及磁碟IO，耗時可以忽略不計。

另外B-tree 中一個節點中可以存放很多的關鍵字（個數由階決定），相同數量的關鍵字在B-tree 中產生的節點要遠遠少於二元樹中的節點，相差的節點數量就等同於磁碟IO的次數。這樣到達一定數量後，性能的差異就顯現出來了。

插入

當 B-tree 要進行插入關鍵字時，都是直接找到葉子節點進行操作。

1. 根據要插入的關鍵字查找到待插入的葉子節點；
2. 因為一個節點的子節點的最大個數（階）為m ，所以需要判斷目前節點關鍵字的個數是否小於(m - 1)。
   • 是：直接插入
   • #否：發生節點分割，以節點的中間的關鍵字將該節點分成左右兩部分，中間的關鍵字放到父節點中即可。

操作流程

例如我們現在需要在Max Degree（階）為3 的B-tree 插入元素：72

1. 尋找待插入的葉子節點

   

2. #節點分裂：本來應該要和[70,88] 在同一個磁碟區塊上，但是當一個節點有3 個關鍵字的時候，它就有可能有4 個子節點，就超過了我們所定義限制的最大度數3，所以此時必須進行分裂：以中間關鍵字為界將節點一分為二，產生一個新節點，並把中間關鍵字移到父節點中。

Tip : 當中間關鍵字有兩個時，通常會將左關鍵字進行上移分裂。

刪除

刪除操作就會比尋找和插入要麻煩一些，因為要刪除的關鍵字可能在葉子節點上，也可能不在，而且刪除後還可能導致B-tree 的不平衡，又要進行合併、旋轉等操作去維持整棵樹的平衡。

隨便拿棵樹（5 階）舉例

以上是終於理解 MySQL 索引要用 B+tree ，而且還這麼快的詳細內容。更多資訊請關注PHP中文網其他相關文章！