阿里面試官：為什么MySQL數(shù)據(jù)庫索引選擇使用B+樹而不是跳表？

來源：https://www.cnblogs.com/andydao/p/12891690.html

二叉查找樹

（1）二叉樹簡介：

二叉查找樹也稱為有序二叉查找樹，滿足二叉查找樹的一般性質(zhì)，是指一棵空樹具有如下性質(zhì)：

1、任意節(jié)點左子樹不為空,則左子樹的值均小于根節(jié)點的值；

2、任意節(jié)點右子樹不為空,則右子樹的值均大于于根節(jié)點的值；

3、任意節(jié)點的左右子樹也分別是二叉查找樹；

4、沒有鍵值相等的節(jié)點； 

 

（2）局限性及應用

AVL樹

（1）簡介

AVL樹是帶有平衡條件的二叉查找樹，一般是用平衡因子差值判斷是否平衡并通過旋轉(zhuǎn)來實現(xiàn)平衡，左右子樹樹高不超過1，和紅黑樹相比，它是嚴格的平衡二叉樹，平衡條件必須滿足（所有節(jié)點的左右子樹高度差不超過1）。不管我們是執(zhí)行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉(zhuǎn)來保持平衡，而旋轉(zhuǎn)是非常耗時的，由此我們可以知道AVL樹適合用于插入刪除次數(shù)比較少，但查找多的情況。 

 
從上面是一個普通的平衡二叉樹，這張圖我們可以看出，任意節(jié)點的左右子樹的平衡因子差值都不會大于1。

（2）局限性

（3）應用

1、Windows NT內(nèi)核中廣泛存在；

紅黑樹

（1）簡介

一種二叉查找樹，但在每個節(jié)點增加一個存儲位表示節(jié)點的顏色，可以是red或black。通過對任何一條從根到葉子的路徑上各個節(jié)點著色的方式的限制，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍。它是一種弱平衡二叉樹(由于是若平衡，可以推出，相同的節(jié)點情況下，AVL樹的高度低于紅黑樹)，相對于要求嚴格的AVL樹來說，它的旋轉(zhuǎn)次數(shù)變少，所以對于搜索、插入、刪除操作多的情況下，我們就用紅黑樹。

（2）性質(zhì)

1、每個節(jié)點非紅即黑； 
2、根節(jié)點是黑的； 
3、每個葉節(jié)點(葉節(jié)點即樹尾端NULL指針或NULL節(jié)點)都是黑的； 
4、如果一個節(jié)點是紅的,那么它的兩兒子都是黑的； 
5、對于任意節(jié)點而言，其到葉子點樹NULL指針的每條路徑都包含相同數(shù)目的黑節(jié)點； 
6、每條路徑都包含相同的黑節(jié)點；

（3）應用

B/B+樹

說了上述的三種樹：二叉查找樹、AVL和紅黑樹，似乎我們還沒有摸到MySQL為什么要使用B+樹作為索引的實現(xiàn)，不要急，接下來我們就先探討一下什么是B樹。

（1）簡介

（2）B樹的性質(zhì)

這里只是一個簡單的B樹，在實際中B樹節(jié)點中關(guān)鍵字很多的，上面的圖中比如35節(jié)點，35代表一個key(索引)，而小黑塊代表的是這個key所指向的內(nèi)容在內(nèi)存中實際的存儲位置，是一個指針。

B+樹

（1）簡介

B+樹是應文件系統(tǒng)所需而產(chǎn)生的一種B樹的變形樹（文件的目錄一級一級索引，只有最底層的葉子節(jié)點（文件）保存數(shù)據(jù)）非葉子節(jié)點只保存索引，不保存實際的數(shù)據(jù)，數(shù)據(jù)都保存在葉子節(jié)點中，這不就是文件系統(tǒng)文件的查找嗎?

我們就舉個文件查找的例子：有3個文件夾a、b、c， a包含b，b包含c，一個文件yang.c，a、b、c就是索引（存儲在非葉子節(jié)點）， a、b、c只是要找到的yang.c的key，而實際的數(shù)據(jù)yang.c存儲在葉子節(jié)點上。

所有的非葉子節(jié)點都可以看成索引部分！

（2）B+樹的性質(zhì)(下面提到的都是和B樹不相同的性質(zhì))

非葉子節(jié)點（比如5，28，65）只是一個key（索引），實際的數(shù)據(jù)存在葉子節(jié)點上（5，8，9）才是真正的數(shù)據(jù)或指向真實數(shù)據(jù)的指針。

（3）應用　　

B/B+樹性能分析

n個節(jié)點的平衡二叉樹的高度為H(即logn)，而n個節(jié)點的B/B+樹的高度為logt((n+1)/2)+1； 

若要作為內(nèi)存中的查找表，B樹卻不一定比平衡二叉樹好，尤其當m較大時更是如此。因為查找操作CPU的時間在B-樹上是O(mlogtn)=O(lgn(m/lgt))，而m/lgt>1；所以m較大時O(mlogtn)比平衡二叉樹的操作時間大得多。因此在內(nèi)存中使用B樹必須取較小的m。（通常取最小值m=3，此時B-樹中每個內(nèi)部結(jié)點可以有2或3個孩子，這種3階的B-樹稱為2-3樹）。

為什么說B+樹比B樹更適合數(shù)據(jù)庫索引？

1、 B+樹的磁盤讀寫代價更低：B+樹的內(nèi)部節(jié)點并沒有指向關(guān)鍵字具體信息的指針，因此其內(nèi)部節(jié)點相對B樹更小，如果把所有同一內(nèi)部節(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字數(shù)量也越多，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多，相對IO讀寫次數(shù)就降低了。

2、B+樹的查詢效率更加穩(wěn)定：由于非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，導致每一個數(shù)據(jù)的查詢效率相當。

3、由于B+樹的數(shù)據(jù)都存儲在葉子結(jié)點中，分支結(jié)點均為索引，方便掃庫，只需要掃一遍葉子結(jié)點即可，但是B樹因為其分支結(jié)點同樣存儲著數(shù)據(jù)，我們要找到具體的數(shù)據(jù)，需要進行一次中序遍歷按序來掃，所以B+樹更加適合在區(qū)間查詢的情況，所以通常B+樹用于數(shù)據(jù)庫索引。

PS：我在知乎上看到有人是這樣說的,我感覺說的也挺有道理的：

他們認為數(shù)據(jù)庫索引采用B+樹的主要原因是：B樹在提高了IO性能的同時并沒有解決元素遍歷的我效率低下的問題，正是為了解決這個問題，B+樹應用而生。B+樹只需要去遍歷葉子節(jié)點就可以實現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作或者說效率太低。

B+樹的原理，基本上講完了，限于篇幅，關(guān)于MySQL為啥不用跳表？而Redis鐘情于跳表？咱們下篇再來講述。

參考文章：

1、http://blog.csdn.net/whoamiyang/article/details/51926985 
2、https://www.cnblogs.com/George1994/p/7008732.html 
3、《MySQL技術(shù)內(nèi)幕 InnoDB存儲引擎 姜承堯 第2版》