本文所述的各種數(shù)據(jù)結(jié)構(gòu)(二叉樹等)梦裂，均不考慮重復(fù)值的情況似枕，本文簡述各種數(shù)據(jù)結(jié)構(gòu)的區(qū)別僅僅只是為了理解MySQL索引的需要而做的鋪墊。

什么是索引

提起索引年柠，大家都知道菠净，建立索引可以讓數(shù)據(jù)庫查詢更快，那么索引究竟是什么彪杉？我想這就不是每個人都能說得出來了毅往。

索引，是數(shù)據(jù)庫管理系統(tǒng)中一個排序的數(shù)據(jù)結(jié)構(gòu)派近，并用以協(xié)助快速查詢攀唯、 更新數(shù)據(jù)庫表中數(shù)據(jù)。

是的渴丸，索引是一種數(shù)據(jù)結(jié)構(gòu)侯嘀，但是那么多的數(shù)據(jù)結(jié)構(gòu)中為何MySQL要選擇B+樹呢？接下來就讓我們一起來了解下B+樹相對于其他數(shù)據(jù)結(jié)構(gòu)有何獨(dú)特之處谱轨！

二分查找法(Binary Search)

首先讓我們自己想一想戒幔，如果讓我們?nèi)ピO(shè)計(jì)，我們會怎么去存儲土童？我想大部分人想到就是用鏈表或者數(shù)組去存儲數(shù)據(jù)诗茎，然后再按默認(rèn)的順序排好，再去查找献汗，而一個排好順序的鏈表我們就可以通過二分查找法來高效查詢敢订。

二分查找也稱折半查找，是一種效率較高的查找方法罢吃。比如有1-10十個數(shù)楚午，我們要找到8，先從中間開始找5尿招，然后發(fā)現(xiàn)8比5大矾柜，可以把5左邊的數(shù)去掉阱驾，剩下6-10，再從中間開始找怪蔑，依次類推啊易，直到找到8為止。但是這種查找法有一個前提是數(shù)據(jù)必須是有序的饮睬，而且這種屬于鏈表式的存儲租谈，我們一但要插入或者修改一個數(shù)據(jù)，可能會伴隨著大量的下標(biāo)移動捆愁，比如我們把1-10放在數(shù)組里面割去，下標(biāo)分別對應(yīng)0-9，然后現(xiàn)在要插入一個0昼丑，為了保證有序呻逆，0必須排在第一位，那么1-10所有的數(shù)據(jù)下標(biāo)都要往后移動一位菩帝，這種就有點(diǎn)大動干戈了咖城，所以為了解決這個問題，我們就有了二叉樹呼奢。

二叉查找樹(BST）

二叉查找樹簡稱二叉樹(BST)宜雀，英文全稱：Binary Search Tree，這是一種什么樣的數(shù)據(jù)結(jié)構(gòu)呢握础？請看下圖

在上面這棵樹中辐董，我們要找到8，先從根節(jié)點(diǎn)6開始比較禀综，發(fā)現(xiàn)8比6大简烘，就往右邊走，就可以找到8

二叉樹的特點(diǎn)

二叉樹有兩個特點(diǎn)：

1定枷、左子樹所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn)

2孤澎、右子樹所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)

二叉樹存在的問題

二叉樹有一個嚴(yán)重的問題，那就是它的查找耗時是和這棵樹的深度相關(guān)的欠窒，在最壞的情況下時間復(fù)雜度會退化成 O(n)覆旭。

如下圖：

上面就是一種極端情況下的二叉樹，會退化成線性鏈表贱迟，這種如果要找到最后一個數(shù)6姐扮，就要從1開始遍歷完整棵樹絮供，效率就會非常低衣吠。那么有沒有一種相對平衡一點(diǎn)，不要出現(xiàn)這種極端情況的數(shù)據(jù)結(jié)構(gòu)呢壤靶，所以就有了平衡二叉樹缚俏。

平衡二叉樹(AVL Tree)

平衡二叉樹，英文全名叫做 Balanced binary search trees，簡稱AVL樹忧换，這個AVL并不是英文名的簡稱恬惯，而是發(fā)明者(G. M. Adelson-Velsky和E. M. Landis)兩個人的人名縮寫，請看下圖一個平衡二叉樹示例：

上圖中也是從1開始插入6亚茬，如果是二叉樹就會變成一種線性結(jié)構(gòu)酪耳，但是平衡二叉樹就會通過左旋和右旋操作，最終會生成上圖所示的結(jié)構(gòu)刹缝，感興趣的可以進(jìn)入網(wǎng)站自己操作觀察旋轉(zhuǎn)過程.

平衡二叉樹的特點(diǎn)

平衡二叉樹相比較二叉樹具有一個特點(diǎn)就是：左右子樹深度差絕對值不能超過 1碗暗，當(dāng)然，平衡二叉樹首先是一顆二叉樹梢夯，只不過通過左旋和右旋實(shí)現(xiàn)左右子樹深度差不超過1言疗，避免了二叉樹的極端情況的出現(xiàn)。

MySQL為何不選擇平衡二叉樹

既然平衡二叉樹解決了普通二叉樹的問題颂砸，那么mysql為何不選擇平衡二叉樹作為索引呢?

索引需要存儲什么

讓我們想一想噪奄，如果我們要把索引存起來，那么應(yīng)該存哪些信息呢人乓，它應(yīng)該存儲三塊信息：

索引的值：就是表里面索引列對應(yīng)的值勤篮。

數(shù)據(jù)的磁盤地址(通過磁盤地址找到當(dāng)前數(shù)據(jù))或者直接存儲整條數(shù)據(jù)。

子節(jié)點(diǎn)的引用：我們需要從根節(jié)點(diǎn)往下走色罚，所以需要知道左右子節(jié)點(diǎn)的地址叙谨。

根據(jù)這三點(diǎn)，可以有如下大致的一個簡單的結(jié)構(gòu)圖：

上圖中數(shù)字表示的是索引的值保屯，0x開頭的表示磁盤地址手负，根節(jié)點(diǎn)中存了左右節(jié)點(diǎn)的引用。

AVL樹用來存儲索引存在什么問題

我們知道姑尺，頁（Page）是 Innodb 存儲引擎用于管理數(shù)據(jù)的最小磁盤單位竟终，頁的默認(rèn)大小為16KB。頁也就是上圖中的節(jié)點(diǎn)切蟋，每查詢一次節(jié)點(diǎn)就需要進(jìn)行一次IO操作统捶，IO操作是一種非常耗時的操作，很多業(yè)務(wù)系統(tǒng)的瓶頸都是卡在IO操作上柄粹，所以如果我們需要提高查詢效率的辦法之一就是減少IO次數(shù)喘鸟，那么問題就來了，AVL樹一個節(jié)點(diǎn)上只存了一個關(guān)鍵字(索引值)+一個磁盤地址+左右節(jié)點(diǎn)的引用驻右，這是遠(yuǎn)遠(yuǎn)達(dá)不到16KB的什黑，會浪費(fèi)了大量的空間。

上圖中如果我們要找到6這條數(shù)據(jù)堪夭，需要進(jìn)行3次IO(獲取一個節(jié)點(diǎn)就是一個IO操作)愕把，如果這棵樹很高的話拣凹，就會進(jìn)行大量的IO操作，所以說AVL樹存在的最大問題就是空間利用不足恨豁，浪費(fèi)了大量空間嚣镜，數(shù)據(jù)量大的時候就會成為一顆瘦高的樹。

那么我們可以怎么改進(jìn)呢橘蜜？答案很明顯了菊匿，那就是每個磁盤塊多存一點(diǎn)東西，也就是說每個磁盤多存幾個關(guān)鍵字计福，因?yàn)殛P(guān)鍵字越多捧请，路數(shù)越多；路數(shù)越多棒搜，樹也就越矮越胖疹蛉，相應(yīng)的操作IO次數(shù)就會越少。

多路平衡樹(Balanced Tree)

多路平衡樹簡稱B樹力麸，又稱B-樹可款，和AVL樹一樣，B樹在枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)存儲鍵值克蚂、磁盤地址闺鲸、左右節(jié)點(diǎn)引用。請看下圖的一個多路平衡樹的示例：

B樹的特點(diǎn)

相比較AVL樹埃叭，B樹一個磁盤上可以存多個關(guān)鍵字(值)摸恍，而且有一個特點(diǎn)就是：

分叉數(shù)（路數(shù)）永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多1。

我們可以畫出如下簡圖(下圖中只畫了3路赤屋，即兩個關(guān)鍵字立镶，實(shí)際取決于一頁能存儲多少個關(guān)鍵字)：

從上圖可以很明顯的看出，同樣高度的樹类早，B樹能存的數(shù)據(jù)遠(yuǎn)遠(yuǎn)大于平衡二叉樹媚媒。

B樹是如何查找數(shù)據(jù)的

以上圖為例，假如我們要找key=32這個數(shù)字涩僻，首先獲取到根節(jié)點(diǎn)缭召，發(fā)現(xiàn)18小于key，所以往右邊走逆日，獲取到右邊的數(shù)據(jù)嵌巷，54和76，這時候遵循以下原則：

key<54,命中最左邊分叉室抽；

key=54,直接命中搪哪，返回?cái)?shù)據(jù)；

54<key<76,走中間的一個分叉狠半；

key=76,直接命中噩死，返回?cái)?shù)據(jù)颤难；

key>76神年，命中右邊分支已维；

這里因?yàn)閗ey=32，所以走得是第1條已日，命中左邊分支垛耳，這時候再去獲取左邊分支，獲取到32和50飘千，比較發(fā)現(xiàn)key=32堂鲜，命中，返回?cái)?shù)據(jù)护奈。

從上面我們可以看出B樹效率相對于AVL樹缔莲，在數(shù)據(jù)量大的情況效率已經(jīng)提高了很多，那么為什么MySQL還是不選擇B樹作為索引呢霉旗？

那么接下來讓我們先看看改良版的B+樹痴奏，然后再下結(jié)論吧！

B+樹

B+樹由B樹改良而來厌秒，屬于改良版的多路平衡查找樹读拆。

首先讓我們來看看B+樹到底長什么樣呢：

對比B+樹，我們可以發(fā)現(xiàn)一個很明顯的區(qū)別就是葉子節(jié)點(diǎn)有一個箭頭指引而且從左到右是有序的鸵闪。

InnoDB中使用的B+樹相比較于傳統(tǒng)B+樹檐晕，改進(jìn)之后的B+樹具有以下特點(diǎn)

InnoDB中B+樹的特點(diǎn)

它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的。

B+樹的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會存儲數(shù)據(jù)蚌讼，只有葉子節(jié)點(diǎn)才存儲數(shù)據(jù)辟灰。而搜索到關(guān)鍵字不會直接返回，會到最后一層的葉子節(jié)點(diǎn)篡石。

B+樹的每個葉子節(jié)點(diǎn)增加了一個指向相鄰葉子節(jié)點(diǎn)的指針伞矩，它的最后一個數(shù)據(jù)會指向下一個葉子節(jié)點(diǎn)的第一個數(shù)據(jù)，形成了一個有序鏈表的結(jié)構(gòu)夏志。

它是根據(jù)左閉右開的區(qū)間來檢索數(shù)據(jù)的

按照B+樹的特點(diǎn)乃坤，我們可以畫出一個存儲數(shù)據(jù)的簡圖，如下：

B+樹是如何查找數(shù)據(jù)的

假設(shè)我們現(xiàn)在要找一個key=66沟蔑，遵循如下步驟：

1湿诊、獲取到根節(jié)點(diǎn)，依據(jù)左閉右開有如下區(qū)間：[1,28)瘦材，[28,66),[66,+∞)厅须，命中了最后一個區(qū)間，雖然66在根節(jié)點(diǎn)食棕，但是因?yàn)楦?jié)點(diǎn)不存儲數(shù)據(jù)朗和，所以是會往下繼續(xù)搜索右邊的節(jié)點(diǎn)

2错沽、獲取到右邊節(jié)點(diǎn)，依據(jù)左閉右開有如下區(qū)間：[66,78),[78,89),[89,+∞)眶拉，命中左邊的范圍千埃。

3、獲取到第三排倒數(shù)第二塊磁盤忆植，找到66放可，返回?cái)?shù)據(jù)。

B+樹相對于B樹的改進(jìn)點(diǎn)

B+樹是由B樹改進(jìn)而來的朝刊，所以B樹能解決的問題耀里，B+樹都能解決，那么B+樹能解決哪些B樹所不能解決的問題呢拾氓？

1冯挎、掃庫、掃表能力更強(qiáng)：如果我們要對表進(jìn)行全表掃描咙鞍，只需要遍歷葉子節(jié)點(diǎn)就可以 了房官，不需要遍歷整棵B+Tree

2、B+Tree 的磁盤讀寫能力相對于 B Tree 來說更強(qiáng)：根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)區(qū)奶陈， 所以一個節(jié)點(diǎn)可以保存更多的關(guān)鍵字易阳，一次磁盤加載(IO操作)能獲取到相對更多的關(guān)鍵字。

3吃粒、天然具備排序能力：葉子節(jié)點(diǎn)上有下一個數(shù)據(jù)區(qū)的指針潦俺，數(shù)據(jù)形成了鏈表。

4徐勃、效率穩(wěn)定：B+Tree 永遠(yuǎn)是在葉子節(jié)點(diǎn)拿到數(shù)據(jù)事示，所以 IO 次數(shù)是穩(wěn)定的，而B樹運(yùn)氣好根節(jié)點(diǎn)就拿到數(shù)據(jù)僻肖，運(yùn)氣不好就要到葉子節(jié)點(diǎn)才能拿到數(shù)據(jù)肖爵，所花費(fèi)的時間會有差異。