首頁 > 文章 > 資料庫 > 終於理解 MySQL 索引要用 B+tree ，而且還這麼快

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

coldplay.xixi轉載: 2020-11-18 17:36:201775瀏覽

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

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

前言

當你現在遇到了一條慢SQL 需要進行最佳化時，你第一時間能想到的最佳化手段是什麼？大部分人第一反應可能都是添加索引，在大多數情況下面，索引能夠將一條SQL 語句的查詢效率提高幾個數量級。索引的本質：用於快速尋找記錄的一種資料結構。索引的常用資料結構：

二元樹
紅黑樹
B-tree（B樹，不叫什麼B減樹）
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 路搜尋樹。它可能是空樹，或滿足以下特點：

除根節點和葉子節點外，其它每個節點至少有 $\lceil \dfrac{m}{2}\rceil$
####################### #############################2#################### ######################m############################ ########################⌉############### 個子節點;###
$⌈ \frac{#m}{##2} ⌉ \lceil \dfrac{m}{2}\rceil$
$\frac{}{} #2$ 2
⌉

###########################################################################################################如果######\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### 的找出分兩步驟：###