深入理解Mysql的B+Tree索引原理

首先，正確的創建合適的索引，是提升資料庫查詢效能的基礎。

索引是什麼？

索引是為了加速資料行在資料行的擷取而建立的一種分散儲存的資料結構。

索引的工作機制是怎麼樣的？

如上圖中，如果現在有一個sql語句select * from teacher where id = 101，如果沒有索引的條件下，我們要找到這條記錄，我們就需要就行全表掃描，匹配id = 101的資料。如果有了索引，我們就可以快速的透過索引找到101所對應的行記錄在磁碟中的位址，再根據給定的位址取出對應的行資料。

MYSQL資料庫為什麼要使用B TREE作為索引的資料結構？

對資料的加速檢索，首先想到的是二元樹，二元樹的尋找時間複雜度可以達到O(log2(n))。下面看一下二元樹的儲存結構：

二元樹搜尋相當於一個二分查找。二元查找能大幅提升查詢的效率，但是它有一個問題：二元樹以第一個插入的資料作為根節點，如上圖中，如果只看右側，就會發現，就是一個線性鍊錶結構。如果我們現在的資料只包含1, 2, 3, 4，5, 6，就會出現一下情況：

如果我們要查詢的資料為6則需要遍歷所有的節點才能找到6，即，相當於全表掃描，就是由於有這種問題，所以二元查找樹不適合用來作為索引的資料結構。

基於這樣的推演，為了解決存在線性鍊錶的問題，很容易就能夠想到平衡二元查找樹。下面看看平衡二元樹是怎麼樣的：

#平衡二元查找樹定義為：節點的子節點高度差不能超過1,如上圖中的節點20，左節點高度為1，右邊節點高度0，差為1，所以上圖沒有違反定義，他就是平衡二元樹。確保二元樹平衡的方式為左旋，右旋等操作，至於若左旋右旋，可以自行去搜尋相關的知識。

如果上圖中平衡二元樹保存的是id索引，現在要從id = 8的數據，首先要把根節點加載進內存，用8和10進行比較，發現8比10小，繼續載入10的左子樹。把5裝進內存，用8和5比較，同理，載入5節點的右子樹。此時發現命中，現在要載入id為8的索引所對應的資料。

怎麼找到索引對應的資料呢？

索引保存資料的方式一般有兩種，第一種為在節點的資料區保存id = 8的行資料的所有資料具體內容。另外一種方式，資料區保存的是真正保存資料的磁碟位址。

到這裡，平衡二元樹解決了存在線性鍊錶的問題，資料查詢的效率好像也還可以，基本能達到O(log2(n))， 那為什麼mysql不選擇這樣的資料結構呢，他又存在什麼樣的問題呢？

問題1： 搜尋效率不足，一般來說，在樹結構中，資料所處的深度，決定了搜尋時的IO次數。如上圖搜尋id = 8的數據，需要進行3次IO。當資料量到達幾百萬的時候，樹的高度就會很恐怖。

問題2：查詢不不穩定，如果查詢的資料落在根節點，只需要一次IO，如果是葉子節點或是支節點，會需要多次IO才可以。

問題3： 節點儲存的資料內容太少。沒有很好利用作業系統和磁碟資料交換特性，也沒有利用好磁碟IO的預讀能力。因為作業系統和磁碟之間一次資料交換是已頁為單位的，一頁 = 4K，即每次IO作業系統會將4K資料載入進記憶體。但是，在二元樹每個節點的結構只保存一個關鍵字，一個資料區，兩個子節點的引用，並不能夠填滿4K的內容。幸好苦苦做了一次的IO操作，卻只載入了一個關鍵字，在樹的高度很高，剛好又搜尋的關鍵字位於葉子節點或支節點的時候，取一個關鍵字要做很多次的IO。

那有沒有一種結構能夠解決二元樹的這種問題呢？

有，多路平衡查找樹：（Balance Tree）：

B Tree 是絕對平衡樹，所有的葉子節點在同一高度，如下圖所示：

B Tree有什麼優勢，又是怎麼去解決一些問題的呢？

先看定義，上圖為一個2-3樹（每個節點儲存2個關鍵字，有3路），多路平衡找出樹也就是多叉的意思，從上圖中可以看出，每個節點保存的關鍵字的個數和路數關係為：

關鍵字個數= 路數– 1。

假設要從上圖中去尋找id = 28的數據，B TREE 搜尋過程如下：

先把根節點載入進內存，載入了17,35兩個關鍵字，判斷規則為：

根據上述規則命中28後，接下來載入28對應的數據， 就去找28對應的資料區，資料區中儲存的是具體的數據或者是指向數據的指標。

為什麼說這種結構能夠解決平衡二元樹存在的問題呢？

能夠很好的利用作業系統和磁碟的互動特性， MYSQL為了很好的利用磁碟的預讀能力，將頁大小為16K，即將一個節點（磁碟區塊）的大小設置為16K，一次IO將一個節點（16K）內容載入進記憶體。這裡，假設關鍵字類型為int，即4字節，若每個關鍵字對應的資料區也是4字節，不考慮子節點引用的情況下，則上圖中的每個節點大約能夠儲存（ 16 * 1000）/ 8 = 2000個關鍵字，則共2001個路數。對於二元樹，三層高度，最多可以保存7個關鍵字，而對於這種有2001路的B樹，三層高度能夠搜尋的關鍵字個數遠遠的大於二元樹。

在B TREE保證樹的平衡的過程中，每次關鍵字的變化，都會導致結構發生很大的變化，這個過程是特別浪費時間的，所以創建索引一定要創建合適的索引，而不是把所有的字段都創建索引，創建冗餘索引只會在對資料進行新增，刪除，修改時增加效能消耗。

既然B樹已經很好的解決了問題，為什麼MYSQL還要用B TREE？

先看看B TREE是怎樣的，B TREE是B TREE的變種，在B 樹種，B樹種的路數和關鍵字的個數的關係不再成立了，B在TREE中，資料檢索規則採用的是左閉合區間，路數和關鍵個數關係為1比1，具體如下圖所示：

##如果上圖是用ID做的索引，如果是搜尋id = 1的數據，搜尋規則如下：

根據如上規則，最終在葉子節點中命中數據，根據葉子節點中節點1的資料區取得真正的資料。

B TREE和B TREE差別是什麼？

1、B TREE 關鍵字的搜尋採用的是左閉合區間，之所以採用左閉合區間是因為他要最好的去支援自增id，這也是mysql的設計初衷。即，如果id = 1命中，會繼續往下查找，直到找到葉子節點中的1。

2、B TREE 根節點和支節點沒有資料區，關鍵字對應的資料只保存在葉子節點中。也就是只有葉子節點中的關鍵字資料區才會保存真正的資料內容或是內容的位址。而在B樹種，如果根節點命中，則會直接回傳資料。並且在B TREE中，葉子節點不會去保存子節點的引用。

3、B TREE葉子節點是順序排列的，並且相鄰的節點具有順序引用的關係，如上圖中葉子節點之間有指標相連接。

MYSQL為什麼最後要去選擇B TREE？

1、B TREE是B TREE的變種，B TREE能解決的問題，B TREE也能夠解決（降低樹的高度，增大節點儲存資料量）

2. B TREE掃庫和掃表能力更強，如果我們要根據索引去進行資料表的掃描，對B TREE進行掃描，需要把整棵樹遍歷一遍，而B TREE只需要遍歷他的所有葉子節點即可（葉子節點之間有引用）。

3、B TREE磁碟讀寫能力更強，他的根節點和支節點不保存資料區，所有根節點和支節點同樣大小的情況下，保存的關鍵字要比B TREE要多。而葉節點不保存子節點引用。所以，B TREE讀寫一次磁碟載入的關鍵字比B TREE更多。

4、B TREE排序能力更強，如上面的圖可以看出，B TREE天然具有排序功能。

5、B TREE查詢效率更穩定，每次查詢數據，查詢IO次數一定是穩定的。當然這個每個人的理解都不同，因為在B TREE如果根節點命中直接返回，確實效率更高。

MYSQL B TREE具體落實形式#

這裡主要講解的是MYSQL根據B TREE索引結構不同的兩種儲存引擎（MYISAM 和INNODB）的實現，首先找到MYSQL保存資料的資料夾，看看mysql是如何保存資料的：

進入到這個目錄下，這個目錄下保存的是所有資料庫，然後再進入到具體的一個資料庫目錄下。在這裡，有多種資料的儲存引擎，這裡講解MYISAM和innodb，如圖中所示：

#MYISAM儲存引擎索引：

##從圖中可以看出，使用MYISAM儲存引擎儲存資料庫數據，一共有三個檔案：

Frm，表格的定義檔。 MYD：資料文件，所有的資料都保存在這個文件中。 MYI：索引檔。

在MYISAM儲存引擎中，資料和索引的關係如下：

如何找出資料的呢？如果要查詢id = 101的數據，先根據MYI索引檔案（如上圖左）去找id = 101的節點，透過這個節點的資料區拿到真正儲存資料的磁碟位址，再透過這個位址從MYD資料檔案（如上圖右）載入對應的記錄。

如果有多個索引，表現形式如下：

所以在MYISAM儲存引擎中，主鍵索引和輔助索引是同等級的，沒有主次之分。

Innodb儲存引擎：

首先看一下聚集索引的概念，聚集索引定義為：資料庫表格行中資料的物理順序和鍵值的邏輯順序相同。

Innodb以主鍵為索引來聚集組織資料的存儲，以下來看看Innodb是如何組織資料的。

Innodb只有兩個文件，Frm文件： 表的定義文件，和Ibd文件，沒有專門保存資料的文件。資料以主鍵進行聚集存儲，把真正的資料保存在葉子節點中。 innodb設計初衷認為主鍵才是最主要的索引。具體如下圖所示：

如上圖中，葉子節點的資料區保存的就是真實的數據，在透過索引進行檢索的時候，命中葉子節點，就可以直接從葉節點中取出行資料。 mysql5.5版本之前採用的是MYISAM引擎，5.5之後採用的是innodb引擎。

在innodb中，輔助索引的格式如下圖所示？

如上圖，主鍵索引的葉子節點保存的是真正的資料。而輔助索引葉子節點的資料區則保存的是主鍵索引關鍵字的值。搜尋過程為：假如要查詢name = seven的數據，先在輔助索引中查詢最後找到主鍵id = 101，再在主鍵索引中搜尋id為101的數據，最終在主鍵索引的葉子節點中獲取到真正的數據。所以透過輔助索引進行檢索，需要檢索兩個索引。

把Innodb 和MYISAM差異放在一張圖中看，就如下所示：

建立索引的幾大原則：

1、列的離散型：

離散型的計算公式：count(distinct col):count(col)，離散型越高，選擇型越好。

如下表中各個字段，哪一列的離散型最好：

上圖中，顯然可以看出，name的離散型最好，如果用sex建立索引：

為什麼說離散型越高，選擇型越好？

如下圖，如果對Sex建立索引，則索引結構將會如下：

#如果此時檢索sex = 1的數據，根節點判斷的時候，結果是查詢左子樹，但是當在左子樹第二層再進行判斷的時候，因為左右分支都滿足條件，所以很難抉擇選擇哪一個分支繼續搜索，或者是把兩個分支同時進行搜尋。

2、最左邊匹配原則

對於索引中的關鍵字進行對比的時候，一定是從左到右以此對比，且不可跳過。之前講解的id都為int型數據，如果id為字串的時候，如下圖：

當進行配對的時候，會把字串轉換成ascll碼，如abc變成97 98 99，然後從左往右一個字元一個字元進行比較。所以在sql查詢中使用like %a 時候索引會失效，因為%表示全匹配，如果已經全匹配就不需要索引，不如直接全表掃描。

3、最少空間原則

前面已經說過，當關鍵字佔用的空間越小，則每個節點保存的關鍵字個數就越多，每次加載進內存的關鍵字個數就越多，檢索效率就越高。

聯合索引：

單列索引：節點中的關鍵字[name]

#聯合索引：節點中的關鍵字[name, phoneNum]

可以把單列索引看成特殊的聯合索引，聯合索引的比較也是根據最左邊匹配原則。

聯合索引列的選擇原則：

（1） 常用的列優先（最左匹配原則）

#（2） 離散度高的列優先（離散度高原則）

（3） 寬度小的列優先，（最少空間原則）

下面簡單舉例平時常會遇到的問題：

#如，平時常用的查詢sql如下：

Select * from users where name = ?

Select * from users where name = ? and pahoneNum = ?

為了加快檢索速度，為上面的查詢sql建立索引如下：

Create index idx_name on users(name)

Create index idx_name_phoneNum on users(name, phoneNum)

在上面解決方案中，根據最左匹配原則，idx_name為冗餘索引， where name = ?同樣可以利用索引idx_name_phoneNum進行檢索。冗餘索引會增減維護B TREE平衡時的效能消耗，並且佔用磁碟空間。

覆寫索引：

如果查詢的列，透過索引項目的資訊可直接傳回，則該索引稱為查詢SQL的覆蓋索引。覆蓋索引可以提高查詢的效率。

下面透過範例說明覆蓋索引。

表：teacher

#：PK（id）， key（name，phoneNum）， unique（teacherNo）

下面哪些sql使用到了覆蓋索引？

Select teacherNo from teacher where teacherNo = ?：使用到了，檢索到teacherNo 時候，可以直接將索引中的teacherNo 值傳回，不需要進入資料區。

Select id，teacherNo from teacher where teacherNo = ?：使用到了，輔助索引的葉子節點保存了主索引的值，所以檢索到輔助索引的葉子節點的時候就可以之間返回id。

Select name，phoneNum from teacher where teacherNo = ?：沒有用到

Select phoneNum from teacher where name = ?, 使用到了。

知道了覆蓋索引，就知道了為什麼sql中要求盡量不要使用select *，要寫明具體要查詢的字段，一個原因就是，這樣在使用到覆蓋索引的情況下，不需要進入到資料區，資料就能直接返回，提升了查詢效率。

透過前面的學習，我們可以很容易的明白如下一下結論：

1、索引列的資料長度滿足業務的情況下能少則少。

2、表中的索引並不是越多越好。

3、Where 條件中，like 9%， like %9%， like%9，三種方式都用不到索引。後兩種方式對於索引是無效的。第一種9%是不確定的，決定於列的離散型，結論上講可以用到，如果發現離散情況特別差的情況下，查詢優化器覺得走索引查詢性能更差，還不如全表掃描。

4、Where條件中 NOT IN 無法使用索引

5、多用指定查詢，只回傳自己想要的列，少用select *。

6、查詢條件中使用函數，索引將會失效，這和列的離散型有關，一旦使用到函數，函數具有不確定性。

7、聯合索引中，如果不是依照索引最左列開始查找，無法使用索引。

8、對聯合索引精確匹配最左前列併範圍匹配另一列，可以使用到索引。

9、聯合索引中，如果查詢有某個欄位的範圍查詢，其右邊所有的欄位都無法使用索引。

推薦Mysql教學《Mysql教學》

以上是深入理解Mysql的B+Tree索引原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！