前言
本文将探究MySQL索引結構的技術選型，分析哈希表、二叉搜尋樹、AVL樹、紅黑樹、B樹與B+樹各自的優缺點。
解釋了MySQL最終選擇B+樹作為其索引的組織方式的原因，并在最後增加了3道常問的面試題。
哈希表(Hash)
哈希表查詢資料的時間複雜度為O(1)，是一種高效的資料結構。面試中常問的HashMap就是基于哈希表的思想，對HashMap不太深入的同學，可以參考我的另外一篇文章HashMap奪命連環問
例如将索引列作為key，對應行的實體位址作為value，非常适用于處理等值查詢。
select * from user where id=1; 但哈希表顯而易見的缺點就是，哈希表不适用于範圍查找。
例如執行以下語句時，哈希表就無能為力了。
select * from user where id>1; 二叉搜尋樹(Binary Search Tree)
經常刷LeetCode的同學，肯定是知道二叉搜尋樹的中序周遊是一個遞增序列。
一顆二叉搜尋樹，每個節點最多隻有2個子節點，左子節點的值小于父節點，右子節點的值大于父節點。
在二叉搜尋樹中進行查詢，可以利用到二分查找，是以查詢的時間複雜度為O(logN)。
例如查找元素23時，先從根節點開始，因為23>20，路由到右子節點32上。因為23<32，路由到其左子節點23上，發現相等，查詢結束。
僅需比較3次，就可以查詢到想要的資料。
另外，二叉搜尋樹的插入與删除操作的時間複雜度也為O(logN)，有興趣的同學可以做做LeetCode上的這道題701. 二叉搜尋樹中的插入操作
我們大可以将索引列作為節點的值，同樣每個節點還有個用于儲存相應行實體位址的變量。
二叉搜尋樹支援範圍查找，例如對以下的sql語句
select * from user where id>12 and id<32; 首先利用二分查找到節點12，再對此節點進行中序周遊，在周遊到節點32時停止即可。
二叉搜尋樹在搜尋、插入與删除保持較優的時間複雜度，而且又支援範圍查找。那MySQL為啥沒有使用它呢？
是因為二叉搜尋樹在插入、删除的過程中并不會保持自身的平衡！
例如我新增了3條使用者資料，初始的樹是這樣的（節點的值為主鍵）：
當我再次增加3條資料後，節點被依次加在右子樹上，最終形成連結清單的結構。
此時，二叉搜尋樹退化成了連結清單，時間複雜度由O(logN)提升到了O(N)，查詢性能大大降低。
是以，我們迫切需要一種能夠在變動中保持自平衡的二叉樹。
平衡二叉搜尋樹
AVL樹
AVL樹就是一種自平衡的二叉搜尋樹，對于它的任意一個節點，其左子樹高度與右子樹高度差最大為1，是以就不存在二叉樹退化為連結清單的極端情況。
下圖就是一個AVL樹：
在往AVL樹中插入節點時，需要通過左旋右旋操作來保證樹的平衡性。
AVL樹在查找、插入與删除操作的時間複雜度都為O(logN)。
AVL樹追求極緻的平衡性，是以就會進行多次的旋轉。在插入與删除次數比較多時，達成平衡的代價甚至比使用它的收益還要大。
那有沒有一種能夠稍微降低點平衡性，卻能帶來較大的整體性能上提升的平衡二叉搜尋樹呢？
紅黑樹
紅黑樹也是一種平衡二叉搜尋樹，相比于AVL樹。紅黑樹似乎對平衡性的追求沒有那麼執着，紅黑樹隻要求最長路徑不能超出最短路徑的兩倍。
在紅黑樹中，節點要麼是紅色，要麼是黑色。根節點與葉子節點（NIL）都是黑色的，任意一個路徑不能連續出現2個紅色節點。從根節點出發的所有路徑，黑色節點（不包含NIL）的數量都是相同的。
(不會有人沒看出來，我拿的是一開始的那張圖吧)
紅黑樹通過左旋、右旋與變色三種操作來保證一定的平衡性，相比于AVL樹，紅黑樹的查詢效率較低，但是删除與插入的效率大大提高，總體性能優于AVL樹。
而且在實際的應用中，紅黑樹的應用更加廣泛。例如HashMap在連結清單長度大于8時則轉化為紅黑樹，TreeMap使用紅黑樹來對鍵值進行排序，IO多路複用中epoll使用紅黑樹來對Socket進行管理。
那MySQL為啥沒有使用紅黑樹來組織索引資料呢？
如果索引資料能夠一次性加載到記憶體中，那麼使用紅黑樹是沒有問題的。
問題就在于，索引資料無法一次性加載到記憶體中，是以索引資料需要分批加載。
假設要查詢的資料位于葉子節點上，樹高為n。第一次先把根節點加載到記憶體中，進行一次磁盤IO。當一直查詢到葉子節點時，就需要進行n次IO。
當單表資料達到100萬時，樹的高度約為log1000000(以2為底)=20。一次磁盤IO平均耗時10ms，20次就是0.2秒。如果再考慮到範圍查詢、不走索引的查詢與多表聯查，速度慢得令人發指。
是以，我們現在的首要目标，就是降低IO次數，也就是降低樹的高度。
B樹
B樹又稱為B-樹，注意不是B減樹啊，“-”是一個連字元！！！
B樹是一種多叉平衡搜尋樹，在節點總數相同的情況下，B樹的高度明顯低于二叉樹。
B樹有以下幾個重要的特性：
- 每個節點可能存儲多個元素，節點内元素是有序的，每一個元素也會對應一份資料行（當然也有可能是主鍵索引項，或者資料行的位址）。
- 父節點中的元素不會出現在子節點當中
- 葉子節點都在同一層，且之間沒有通過指針相連
一顆具有3個分叉的B樹為：
可以看到，B樹的高度被壓縮得很厲害。
另外一個方面，B樹充分利用到了程式通路的局部性原理。也就是說，當程式通路磁盤或記憶體中的一份資料時，其周圍的資料将會有很大機率在接下來被使用到。
是以，B數每個節點不會隻存一個元素，而是存儲多份。我們查詢資料時，每進行一次IO，就會将B樹的一個節點讀進緩存中。這樣在接下通路其周圍的資料時，無需從磁盤讀取，直接從緩存讀取，緩存命中率大大提升。
也許會有人問？如果一個節點記憶體放大量元素，那麼從磁盤讀取的速度是否和個數相關，呈線性增長呢？
答案是不會的。第一次讀取一個節點時，進行的是随機讀，需要先進行磁盤尋道，是非常耗時的。之後讀取其他的元素，是進行的順序讀。之是以進行順序讀，是因為一個節點内的元素被順序存儲在磁盤上的。順序讀是非常快速的，其效率可能千倍于随機讀。
那麼，在B樹上讀取索引項為21的流程是怎樣的呢？
在節點内部，使用的是二分查找，用于找到下層指針。
看來B樹能有效解決平衡二叉樹io次數過多的問題，似乎已經能滿足所有的要求了。
但是MySQL最終采用的B+樹，而不是B樹。
相對來說，B樹還有以下的不足：
- 每個節點不僅存索引項，又存具體的資料，那麼每個節點可存放的索引項就比較少。索引項少，io次數就會變多。
- B樹不能做到快速的範圍查找，需要進行多次的查找，類似于中序周遊。
為了改進B樹，後來提出了B+樹。
B+樹
這個時候你又可以讀作B加樹了...
B+樹有以下的特性：
- 非葉子節點隻存放索引項，葉子節點既存放索引項，也存放具體的資料。
- 葉子節點會存放目前所有的索引項，就是說，可以與父節點的索引項重複。
- 葉子節點通過指針相連，形成有序的雙向連結清單結構。
一顆成熟的B+樹，應該是有如下的作風：
由于B+樹葉子節點才存放資料行，是以每次的查詢，都需要加載到葉子節點。而B樹每個節點都存放資料行，每次的查詢不一定非要到葉子節點。
是以這個時候會有人發出這樣的疑問：B+樹每次查詢必須要深入到葉子節點，那麼它的平均查詢效率不是應該低于B樹的嗎？
如果在樹高相同的情況下，确實是的。可實際情況是，在索引項相同的情況下，B+樹的高度明顯低于B樹的，因為B+樹的非葉子節點可以比B樹存放更多的元素，畢竟少了資料行嘛。是以考慮到io成本加上範圍查詢，B+樹的整體查詢效率是優于B樹的，但B+樹對單個資料的查詢效率是低于B樹的。
B+樹在範圍查詢上，是怎麼表現出不錯的性能的呢？
首先查找到範圍下限，直接使用葉子節點的指針來加載下一個資料塊，避免通過父節點來中轉。在周遊到範圍上限後，直接傳回周遊到的所有資料即可。
B+樹通過在葉子節點重複存儲元素，其整體占用的空間其實是略高于B樹的。但這點浪費的空間卻能夠換來巨大的性能提升，也是蠻不錯的。
鑒于B+樹用于以上的優點，MySQL最終采用了B+樹作為索引的組織方式。
各種資料結構的對比
在這裡直接以最簡單明了的方式突出各個資料結構的優缺點：
| 資料結構 | 特點 | 優點 | 缺點 |
| 哈希表 | 使用雜湊演算法，快速查找 | 查詢效率O(1) | 無法滿足範圍查找 |
| 二叉搜尋樹 | 使用二分查找算法，效率較高，且基本實作範圍查找 | 正常情況下，操作效率為O(logN) | 極端情況下退化為連結清單 |
| AVL樹 | 通過左旋、右旋實作嚴格自平衡 | 保持自平衡，操作效率為O(logN) | 追求極緻的平衡，是以旋轉效率低，IO次數多 |
| 紅黑樹 | 通過左旋、右旋與變色實作非嚴格自平衡 | 不追求極緻平衡，整體性能高 | 實作複雜，IO次數多 |
| B樹 | 多叉查找，一個節點存放多個索引項，也存放具體資料 | 樹的高度較低，IO次數少 | IO次數、範圍查找還有優化的空間 |
| B+樹 | 非葉子節點僅存放索引項，葉子節點為雙向連結清單 | 樹的高度更低，IO次數更少 | 存儲重複索引項，記憶體空間占用相對多一點 |
加餐
使用二級索引查詢資料，經曆的io次數怎麼算？
二級索引也是使用B+樹來組織的，其葉子節點不是存儲具體的資料行，而是存儲的主鍵值。
先通過在二級索引中查詢到主鍵值，再進行回表查詢主鍵索引樹，是以一共需要經曆的io次數=二級索引樹io次數+主鍵索引樹次數
有些同學可能會有一點想法，為什麼二級索引的葉子節點不直接存儲具體的資料，再回表一次不是降低了效率嗎？
一個表會有多個索引，如果每個索引數都儲存一份全表資料，資料備援度就會非常高！
3層的B+樹，大概可以存放多少條資料？
InnoDB每次會從磁盤中讀取一頁的資料，一頁大小為16KB，當然可以通過參數設定，是以B+樹中一個節點的大小一般也為16KB。
假設這16KB全部用來存儲節點資料，當然其中會有一小部分用來存儲中繼資料，可以忽略不計。
B+樹中的一個節點，包含索引項與指向下層的指針。
如果此時以int類型的主鍵作為索引項，int類型占用4個位元組，指針占用6個位元組。是以根節點擁有的索引項數為16KB/10B=16*1024/10=1638個。
則根節點擁有1638個子節點，且第二層也是非葉子節點，是以第二層能存放的索引項數為1638*1638約等于268萬個。
第三層為葉子節點，葉子節點存放索引項、前驅後驅指針與具體資料，具體的資料肯定是比索引項與指針大得多的，這時候就統一按一行資料1KB計算，也就是一個葉子節點可以儲存16條資料。
那麼3層的B+數總共可以儲存的資料行為2683044*16≈4千萬條。
當然，2層的B+樹可以儲存的資料行為1638*16≈3萬條。
為什麼MongoDB直接使用B樹？
MySQL作為一種關系型資料庫，大部分的情況下會進行多表聯查，多表聯查就涉及到對某個表的周遊。而B+樹葉子節點存在雙向指針，對周遊支援友好。