深入了解MySQL索引之B+Tree

正确的建立合适的索引，是提升資料庫查詢性能的基礎。在正式講解之前，對後面舉例中使用的表結構先簡單看一下：

create table user
(
    id     bigint  not null comment 'id' primary key,
    name   varchar(200) null comment 'name',
    age    bigint       null comment 'age',
    gender int          null comment 'gender',
    key (name)
);
           

1 索引是什麼及工作機制？

索引是為了加速對表中資料行的檢索而建立的一種分散存儲的資料結構。其工作機制如下圖：

上圖中，如果現在有一條sql語句

select * from user where id = 40

，如果沒有索引的條件下，我們要找到這條記錄，我們就需要在資料中進行全表掃描，比對id = 13的資料。

如果有了索引，我們就可以通過索引進行快速查找，如上圖中，可以先在索引中通過id = 40進行二分查找，再根據定位到的位址取出對應的行資料。

2. MySQL資料庫為什麼要使用B+TREE作為索引的資料結構？

2.1 二叉樹為什麼不可行

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

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

如果我們要查詢的資料為4，則需要周遊所有的節點才能找到4，即，相當于全表掃描，就是由于存在這種問題，是以二叉查找樹不适合用于作為索引的資料結構。

2.2 平衡二叉樹為什麼不可行

為了解決二叉樹存線上性連結清單的問題，會想到用平衡二叉查找樹來解決。下面看看平衡二叉樹是怎樣的：

平衡二叉查找樹定義為：節點的子節點高度差不能超過1,如上圖中的節點20，左節點高度為1，右節點高度0，差為1，是以上圖沒有違反定義，它就是一個平衡二叉樹。保證二叉樹平衡的方式為左旋，右旋等操作，至于如何左旋右旋，可以自行去搜尋相關的知識。

如果上圖中平衡二叉樹儲存的是id索引，現在要查找id = 8的資料，過程如下：

1. 把根節點加載進記憶體，用8和10進行比較，發現8比10小，繼續加載10的左子樹。
2. 把5加載進記憶體，用8和5比較，同理，加載5節點的右子樹。
3. 此時發現命中，則讀取id為8的索引對應的資料。

索引儲存資料的方式一般有兩種：

• 資料區儲存id 對應行資料的所有資料具體内容。
• 資料區儲存的是真正儲存資料的磁盤位址。

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

1. 搜尋效率不足。一般來說，在樹結構中，資料所處的深度，決定了搜尋時的IO次數（MySql中将每個節點大小設定為一頁大小，一次IO讀取一頁 / 一個節點）。如上圖中搜尋id = 8的資料，需要進行3次IO。當資料量到達幾百萬的時候，樹的高度就會很恐怖。
2. 查詢不不穩定。如果查詢的資料落在根節點，隻需要一次IO，如果是葉子節點或者是支節點，會需要多次IO才可以。
3. 存儲的資料内容太少。沒有很好利用作業系統和磁盤資料交換特性，也沒有利用好磁盤IO的預讀能力。因為作業系統和磁盤之間一次資料交換是以頁為機關的，一頁大小為 4K，即每次IO作業系統會将4K資料加載進記憶體。但是，在二叉樹每個節點的結構隻儲存一個關鍵字，一個資料區，兩個子節點的引用，并不能夠填滿4K的内容。幸幸苦苦做了一次的IO操作，卻隻加載了一個關鍵字。在樹的高度很高，恰好又搜尋的關鍵字位于葉子節點或者支節點的時候，取一個關鍵字要做很多次的IO。

那有沒有一種結構能夠解決二叉樹的這種問題呢？有，那就是多路平衡查找樹。

2.3 多路平衡查找樹(Balance Tree)

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

上圖為一個2-3樹（每個節點存儲2個關鍵字，有3路），多路平衡查找樹也就是多叉的意思，從上圖中可以看出，每個節點儲存的關鍵字的個數和路數關系為：關鍵字個數 = 路數 – 1。

假設要從上圖中查找id = X的資料，B TREE 搜尋過程如下：

1. 取出根磁盤塊，加載40和60兩個關鍵字。
2. 如果X等于40，則命中；如果X小于40走P1；如果40 < X < 60走P2；如果X = 60，則命中；如果X > 60走P3。
3. 根據以上規則命中後，接下來加載對應的資料， 資料區中存儲的是具體的資料或者是指向資料的指針。

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

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

這裡順便說一下：在B Tree保證樹的平衡的過程中，每次關鍵字的變化，都會導緻結構發生很大的變化，這個過程是特别浪費時間的，是以建立索引一定要建立合适的索引，而不是把所有的字段都建立索引，建立備援索引隻會在對資料進行新增，删除，修改時增加性能消耗。

B樹确實已經很好的解決了問題，我先這裡先繼續看一下B+Tree結構，再來讨論BTree和B+Tree的差別。

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

如果上圖中是用ID做的索引，如果是搜尋X = 1的資料，搜尋規則如下：

1. 取出根磁盤塊，加載1，28，66三個關鍵字。
2. X <= 1 走P1，取出磁盤塊，加載1，10，20三個關鍵字。
3. X <= 1 走P1，取出磁盤塊，加載1，8，9三個關鍵字。
4. 已經到達葉子節點，命中1，接下來加載對應的資料，圖中資料區中存儲的是具體的資料。

2.4 B TREE和B+TREE差別是什麼？

1. B+Tree 關鍵字的搜尋采用的是左閉合區間，之是以采用左閉合區間是因為他要最好的去支援自增id，這也是mysql的設計初衷。即，如果id = 1命中，會繼續往下查找，直到找到葉子節點中的1。
2. B+Tree 根節點和支節點沒有資料區，關鍵字對應的資料隻儲存在葉子節點中。即隻有葉子節點中的關鍵字資料區才會儲存真正的資料内容或者是内容的位址。而在B樹種，如果根節點命中，則會直接傳回資料。
3. 在B+Tree中，葉子節點不會去儲存子節點的引用。
4. B+Tree葉子節點是順序排列的，并且相鄰的節點具有順序引用的關系，如上圖中葉子節點之間有指針相連接配接。

2.5 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查詢性能穩定。B+Tree資料隻儲存在葉子節點，每次查詢資料，查詢IO次數一定是穩定的。當然這個每個人的了解都不同，因為在B TREE如果根節點命中直接傳回，确實效率更高。

3 MySQL B+Tree具體落地形式

這裡主要講解的是MySQL根據B+Tree索引結構不同的兩種存儲引擎（MYISAM 和 INNODB）的實作。

首先找到MySQL儲存資料的檔案夾，看看MySQL是如何儲存資料的：

mysql> show variables like '%datadir%';
+---------------+------------------------+
| Variable_name | Value                  |
+---------------+------------------------+
| datadir       | /usr/local/mysql/data/ |
+---------------+------------------------+
           

進入到這個目錄下，這個目錄下儲存的是所有資料庫，再進入到具體的一個資料庫目錄下。就能夠看到MySQL存儲資料和索引的檔案了。

這裡我建立了兩張表，user_innod和user_myisam，分别指定索引為innodb和myisam。對于每張表，MySQL會建立相應的檔案儲存資料和索引，具體如下：

-rw-rw----. 1 mysql mysql      8652 May  3 21:11 user_innodb.frm
-rw-rw----. 1 mysql mysql 109051904 May  7 21:26 user_innodb.ibd
-rw-rw----. 1 mysql mysql      8682 May 16 18:27 user_myisam.frm
-rw-rw----. 1 mysql mysql         0 May 16 18:27 user_myisam.MYD
-rw-rw----. 1 mysql mysql      1024 May 16 18:27 user_myisam.MYI
           

從圖中可以看出：

• MYISAM存儲引擎存儲資料庫資料，一共有三個檔案：

  Frm：表的定義檔案。

  MYD：資料檔案，所有的資料儲存在這個檔案中。

  MYI：索引檔案。

• Innodb存儲引擎存儲資料庫資料，一共有兩個檔案(沒有專門儲存資料的檔案)：

  Frm檔案： 表的定義檔案。

  Ibd檔案：資料和索引存儲檔案。資料以主鍵進行聚集存儲，把真正的資料儲存在葉子節點中。

3.1 MyISAM存儲引擎

說明：為了畫圖簡便，下面部分圖使用線上資料結構工具進行組織資料，組織的B+Tree為右閉合區間，但不影響了解存儲引擎資料存儲結構。

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

如何查找資料的呢？

如果要查詢id = 40的資料：先根據MyISAM索引檔案（如上圖左）去找id = 40的節點，通過這個節點的資料區拿到真正儲存資料的磁盤位址，再通過這個位址從MYD資料檔案（如上圖右）中加載對應的記錄。

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

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

3.2 Innodb存儲引擎

Innodb主鍵索引為聚集索引，首先簡單了解一下聚集索引的概念：資料庫表行中資料的實體順序和鍵值的邏輯順序相同。

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

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

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

如上圖，主鍵索引的葉子節點儲存的是真正的資料。而輔助索引葉子節點的資料區儲存的是主鍵索引關鍵字的值。

假如要查詢name = C 的資料，其搜尋過程如下：

1. 先在輔助索引中通過C查詢最後找到主鍵id = 9.
2. 在主鍵索引中搜尋id為9的資料，最終在主鍵索引的葉子節點中擷取到真正的資料。

是以通過輔助索引進行檢索，需要檢索兩次索引。

之是以這樣設計，一個原因就是：如果和MyISAM一樣在主鍵索引和輔助索引的葉子節點中都存放資料行指針，一旦資料發生遷移，則需要去重新組織維護所有的索引。

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

4 建立索引的幾大原則

4.1 列的離散型

離散型的計算公式：

count(distinct column_name):count(*)

，就是用去重後的列值個數比個數。值在 (0,1] 範圍内。離散型越高，選擇型越好。

如下表中各個字段，明顯能看出Id的選擇性比gender更高。

mysql> select * from user;
+----+--------------+------+--------+
| id | name         | age  | gender |
+----+--------------+------+--------+
| 20 | 君莫笑       |   15 |      1 |
| 40 | 蘇沐橙       |   12 |      0 |
| 50 | 張楚岚       |   25 |      1 |
| 60 | 諸葛青       |   27 |      1 |
| 61 | 若有人兮     |   38 |      0 |
| 64 | 馮寶寶       |   18 |      0 |
+----+--------------+------+--------+
           

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

因為離散度越高，通過索引最終确定的範圍越小，最終掃面的行數也就越少。

4.2 最左比對原則

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

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

4.3 最少空間原則

前面已經說過，當關鍵字占用的空間越小，則每個節點儲存的關鍵字個數就越多，每次加載進記憶體的關鍵字個數就越多，檢索效率就越高。建立索引的關鍵字要盡可能占用空間小。

5 聯合索引

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

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

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

5.1 聯合索引列的選擇原則

• 經常用的列優先（最左比對原則）
• 離散度高的列優先（離散度高原則）
• 寬度小的列優先（最少空間原則）

5.2 執行個體分析

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

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

select * from users where name = ?

select * from users where name = ? and age = ?

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

create index idx_name on users(name)

create index idx_name_age on users(name, age)

在上面解決方案中，根據最左比對原則，idx_name為備援索引， where name = ?同樣可以利用索引idx_name_age進行檢索。備援索引會增加維護B+TREE平衡時的性能消耗，并且占用磁盤空間。

6. 覆寫索引

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

如上圖，如果通過name進行資料檢索：

select * from users where name = ?

需要需要在name索引中找到name對應的Id，然後通過擷取的Id在主鍵索引中查到對應的行。整個過程需要掃描兩次索引，一次name，一次id。

如果我們查詢隻想查詢id的值，就可以改寫SQL為：

select id from users where name = ?

因為隻需要id的值，通過name查詢的時候，掃描完name索引，我們就能夠獲得id的值了，是以就不需要再去掃面id索引，就會直接傳回。

當然，如果你同時需要擷取age的值：

select id，age from users where name = ?

這樣就無法使用到覆寫索引了。

知道了覆寫索引，就知道了為什麼sql中要求盡量不要使用

select *

，要寫明具體要查詢的字段。其中一個原因就是在使用到覆寫索引的情況下，不需要進入到資料區，資料就能直接傳回，提升了查詢效率。在用不到覆寫索引的情況下，也盡可能的不要使用

select *

，如果行資料量特别多的情況下，可以減少資料的網絡傳輸量。當然，這都視具體情況而定，通過select傳回所有的字段，通用性會更強，一切有利必有弊。

7 總結

• 索引列的資料長度滿足業務的情況下能少則少。
• 表中的索引并不是越多越好，備援或者無用索引會占用磁盤空間并且會影響增删改的效率。
• Where 條件中，like 9%， like %9%， like%9，三種方式都用不到索引。後兩種方式對于索引是無效的。第一種9%是不确定的，決定于列的離散型，結論上講可以用到，如果發現離散情況特别差的情況下，查詢優化器覺得走索引查詢性能更差，還不如全表掃描。
• Where條件中IN可以使用索引， NOT IN 無法使用索引。
• 多用指定查詢，隻傳回自己想要的列，少用select *。
• 查詢條件中使用函數，索引将會失效，這和列的離散性有關，一旦使用到函數，函數具有不确定性。
• 聯合索引中，如果不是按照索引最左列開始查找，無法使用索引。
• 對聯合索引精确比對最左前列并範圍比對另一列，可以使用到索引。
• 聯合索引中，如果查詢有某個列的範圍查詢，其右邊所有的列都無法使用索引。