<article class="syl-article-base tt-article-content syl-page-article syl-device-pc" style="box-sizing: border-box; display: block; padding: 0px; text-align: justify; word-wrap: break-word; word-break: break-word; overflow: hidden; color: rgb(34, 34, 34); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", "Helvetica Neue", Arial, sans-serif; line-height: 1.667; font-size: 18px; margin-bottom: 20px;">
背景
一般說MySQL的索引条霜，都清楚其索引主要以B+樹為主，此外還有Hash啃匿、RTree蛔外、FullText蛆楞。本文簡要說明一下MySQL的B+Tree索引，以及和其相關的二叉樹夹厌、平衡二叉樹豹爹、B-Tree，相關的知識網上很多矛纹，為了方便自己更快臂聋、清楚的了解，文本聚合一些內容以及個人的一些理解或南。
說明
二叉查找樹（BST）
概念
二叉查找樹是基于二分查找法來提高數(shù)據(jù)查找速度的二叉樹的數(shù)據(jù)結構孩等；
特點
二叉查找樹是采用二分查找法把數(shù)據(jù)按規(guī)則組裝成一個樹形結構的數(shù)據(jù)，減少無關數(shù)據(jù)的檢索采够，提升了數(shù)據(jù)檢索的速度肄方；二叉樹的數(shù)據(jù)結構有以下規(guī)則：
（1）非葉子節(jié)點只能允許最多兩個子節(jié)點存在。
（2）每一個非葉子節(jié)點數(shù)據(jù)分布規(guī)則為左邊的子節(jié)點小當前節(jié)點的值蹬癌，右邊的子節(jié)點大于當前節(jié)點的值权她；
即二叉查找樹的特點就是任何節(jié)點的左子節(jié)點的鍵值都小于當前節(jié)點的鍵值，右子節(jié)點的鍵值都大于當前節(jié)點的鍵值逝薪。頂端的節(jié)點稱為根節(jié)點隅要，沒有子節(jié)點的節(jié)點我們稱之為葉節(jié)點。以下圖中的圓為二叉查找樹的節(jié)點董济，節(jié)點中存儲了鍵(key)和數(shù)據(jù)(data)
查找結點值的方法就是二分查找法：查找次數(shù)就是樹的高度步清。二叉查找樹可以任意地構造 如果向一方傾斜的二叉樹是不平衡的，查詢效率就低了虏肾，二叉查找樹變成了一個鏈表廓啊。如下圖：
在上面的2張圖中，查找鍵值為17的數(shù)據(jù)询微，第一張圖里需要3次IO崖瞭，第2張圖里需要7次IO狂巢。原因是二叉查找樹變得不平衡了撑毛，也就是高度太高了，從而導致查找效率的不穩(wěn)定唧领。為了解決這個問題藻雌，需要保證二叉查找樹一直保持平衡，就需要用到平衡二叉樹了斩个。
平衡二叉樹（AVL）
在滿足二叉查找樹特性的基礎上胯杭，如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹受啥，并且高度之差的絕對值不超過 1做个。類似于：
關于平衡二叉樹的可以看 什么是平衡二叉樹（AVL）該文章說明鸽心，平衡二叉樹相比于二叉查找樹來說，查找效率更穩(wěn)定居暖，總體的查找速度也更快顽频。需要注意的是平衡二叉樹是每個節(jié)點只存儲一個鍵值和數(shù)據(jù)的。
B樹(B-Tree)
概念：
B樹和平衡二叉樹不同太闺，B樹屬于多叉樹又名平衡多路查找樹（查找路徑不只兩個）糯景，數(shù)據(jù)庫索引里大量使用者B-Tree和B+Tree的數(shù)據(jù)結構。
特點：
- 排序方式：所有節(jié)點關鍵字是按遞增次序排列省骂，并遵循左小右大原則蟀淮；
- 子節(jié)點數(shù)：非葉節(jié)點的子節(jié)點數(shù)>1，且<=M 钞澳，且M>=2怠惶，空樹除外（注：M階代表一個樹節(jié)點最多有多少個查找路徑，M=M路轧粟，當M=2則是2叉樹,M=3則是3叉）甚疟；
- 關鍵字數(shù)：枝節(jié)點的關鍵字數(shù)量大于等于ceil(M/2)-1個且小于等于M-1個（注：ceil()是個朝正無窮方向取整的函數(shù) 如ceil(1.1)結果為2);
- 所有葉子節(jié)點均在同一層、葉子節(jié)點除了包含了關鍵字還包含了數(shù)據(jù);
最后我們用一個圖和一個實際的例子來理解B樹（這里為了理解方便我就直接用實際字母的大小來排列C>B>A）
圖中可以看到BTree的單個節(jié)點可以存儲多個鍵值和數(shù)據(jù)的平衡樹逃延。和平衡二叉樹相比：比如要存儲海量的數(shù)據(jù)览妖，因為（平衡）二叉樹的每個節(jié)點只存儲一個鍵值和數(shù)據(jù)的，二叉樹的節(jié)點將會非常多揽祥，高度也會及其高讽膏，當查找數(shù)據(jù)時也會進行很多次磁盤IO，查找的效率將會極低拄丰，大致的二叉樹結構如下：
為了解決平衡二叉樹的這個弊端府树，需要一種單個節(jié)點可以存儲多個鍵值和數(shù)據(jù)的平衡樹（BTree）：
從上圖可以看出，B樹相對于平衡二叉樹料按，每個節(jié)點存儲了更多的鍵值(key)和數(shù)據(jù)(data)奄侠，并且每個節(jié)點擁有更多的子節(jié)點，子節(jié)點的個數(shù)一般稱為階载矿，上述圖中的B樹為3階B樹垄潮，高度也會很低∶瓶基于這個特性弯洗，B樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會很少，數(shù)據(jù)的查找效率也會比平衡二叉樹高很多逢勾。
假如我們要查找id=28的用戶信息牡整，那么我們在上圖B樹中查找的流程如下：
- 先找到根節(jié)點也就是頁1，判斷28在鍵值17和35之間溺拱，我們那么我們根據(jù)頁1中的指針p2找到頁3逃贝。
- 將28和頁3中的鍵值相比較谣辞，28在26和30之間，我們根據(jù)頁3中的指針p2找到頁8沐扳。
- 將28和頁8中的鍵值相比較潦闲，發(fā)現(xiàn)有匹配的鍵值28，鍵值28對應的用戶信息為(28,bv)迫皱。
區(qū)別:B樹相對于平衡二叉樹的不同是：每個節(jié)點包含的關鍵字增多了歉闰，特別是在B樹應用到數(shù)據(jù)庫中的時候，數(shù)據(jù)庫充分利用了磁盤塊的原理（磁盤數(shù)據(jù)存儲是采用塊的形式存儲的卓起，每個塊的大小為4K和敬，每次IO進行數(shù)據(jù)讀取時，同一個磁盤塊的數(shù)據(jù)可以一次性讀取出來）把節(jié)點大小限制和充分使用在磁盤快大小范圍戏阅；把樹的節(jié)點關鍵字增多后樹的層級比原來的二叉樹少了昼弟，減少數(shù)據(jù)查找的次數(shù)和復雜度。
相同數(shù)量的key在B-Tree中生成的節(jié)點要遠遠少于二叉樹中的節(jié)點奕筐，相差的節(jié)點數(shù)量就等同于磁盤IO的次數(shù)舱痘。這樣到達一定數(shù)量后，性能的差異就顯現(xiàn)出來了离赫。
B+樹（B+Tree）
概念
B+樹是B樹的一個進化芭逝，相對于B樹來說B+樹更充分得利用了節(jié)點的空間，讓查詢速度更加穩(wěn)定渊胸，其速度完全接近于二分法查找旬盯。結構如下：
[圖片上傳失敗...(image-fd3493-1648794941453)]
為什么說B+樹查找的效率要比B樹更高、更穩(wěn)定翎猛；我們先看看兩者的區(qū)別：
- B+樹的非葉子節(jié)點不保存數(shù)據(jù)胖翰，只進行數(shù)據(jù)索引（關鍵字記錄的指針），這樣使得B+樹每個非葉子節(jié)點所能保存的關鍵字大大增加切厘；
- B+樹葉子節(jié)點保存了父節(jié)點的所有關鍵字記錄的指針萨咳，所有數(shù)據(jù)地址必須要到葉子節(jié)點才能獲取到。所以每次數(shù)據(jù)查詢的次數(shù)都一樣疫稿；
- B+樹葉子節(jié)點的關鍵字從小到大有序排列培他，左邊結尾數(shù)據(jù)都會保存右邊節(jié)點開始數(shù)據(jù)的指針；
- B+樹非葉子節(jié)點的子節(jié)點數(shù)=關鍵字數(shù);
特點
- B+樹的層級更少：相較于B樹而克，B+每個非葉子節(jié)點存儲的關鍵字數(shù)更多靶壮，樹的層級更少所以查詢數(shù)據(jù)更快怔毛；
- B+樹查詢速度更穩(wěn)定：B+所有關鍵字數(shù)據(jù)地址都存在葉子節(jié)點上员萍，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定;
- B+樹天然具備排序功能：B+樹所有的葉子節(jié)點數(shù)據(jù)構成了一個有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時候更方便拣度，數(shù)據(jù)緊密性很高碎绎，緩存的命中率也會比B樹高螃壤。
- B+樹全節(jié)點遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點即可，而不需要像B樹一樣需要對每一層進行遍歷筋帖，這有利于數(shù)據(jù)庫做全表掃描奸晴。
B樹相對于B+樹的優(yōu)點是：如果經常訪問的數(shù)據(jù)離根節(jié)點很近，而B樹的非葉子節(jié)點本身存有關鍵字其數(shù)據(jù)的地址日麸，所以這種數(shù)據(jù)檢索的時候會要比B+樹快寄啼。
根據(jù)上圖我們來看下B+樹和B樹有什么不同：
- B+Tree 非葉子節(jié)點上是不存儲數(shù)據(jù)的，僅存儲鍵值代箭，數(shù)據(jù)存儲在同一層的葉節(jié)點墩划，而B-Tree節(jié)點中不僅存儲鍵值，也會存儲數(shù)據(jù)嗡综。之所以這么做是因為在數(shù)據(jù)庫中頁的大小是固定的乙帮，innodb中頁的默認大小是16KB。如果不存儲數(shù)據(jù)极景，那么就會存儲更多的鍵值察净，相應的樹的階數(shù)(節(jié)點的子節(jié)點樹)就會更大，樹就會更矮更胖盼樟，如此一來我們查找數(shù)據(jù)進行磁盤的IO次數(shù)有會再次減少氢卡，數(shù)據(jù)查詢的效率也會更快。另外晨缴，B+Tree的階數(shù)是等于鍵值的數(shù)量的异吻，如果B+Tree一個節(jié)點可以存儲1000個鍵值，那么3層B+樹可以存儲1000×1000×1000=10億個數(shù)據(jù)喜庞。一般根節(jié)點是常駐內存的诀浪，所以一般我們查找10億數(shù)據(jù)，只需要2次磁盤IO延都。
- 因為B+Tree索引的所有數(shù)據(jù)均存儲在葉子節(jié)點雷猪，而且數(shù)據(jù)是按照順序排列的。那么B+樹使得范圍查找晰房，排序查找求摇，分組查找以及去重查找變得異常簡單。而B-Tree 因為數(shù)據(jù)分散在各個節(jié)點殊者，要實現(xiàn)這一點是很不容易的与境。
B+Tree 中各個頁之間是通過雙向鏈表連接的，葉子節(jié)點中的數(shù)據(jù)是通過單向鏈表連接的猖吴。
其實上面的B-Tree也可以對各個節(jié)點加上鏈表摔刁。其實這些不是它們之前的區(qū)別，是因為在mysql的innodb存儲引擎中海蔽，索引就是這樣存儲的共屈。也就是說上圖中的B+Tree索引就是innodb中B+Tree索引真正的實現(xiàn)方式绑谣，準確地說應該是聚集索引。
通過上圖可以看到拗引，在innodb中借宵，數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。
注意：MyISAM中的B+樹索引實現(xiàn)與innodb中的略有不同矾削。在MyISAM中壤玫，B+樹索引的葉子節(jié)點并不存儲數(shù)據(jù)，而是存儲數(shù)據(jù)的文件地址哼凯。
B+Tree 結構是從二叉查找樹垦细，平衡二叉樹和B-Tree這三種數(shù)據(jù)結構演化來的，他們之前的區(qū)別上面已經介紹過挡逼，現(xiàn)在大致的總結下括改，如下：
1. 二叉查找樹是基于二分查找法來提高數(shù)據(jù)查找速度的二叉樹的數(shù)據(jù)結構，減少無關數(shù)據(jù)的檢索家坎，提升了數(shù)據(jù)檢索的速度嘱能。非葉子節(jié)點只能允許最多兩個子節(jié)點存在，每一個非葉子節(jié)點數(shù)據(jù)分布規(guī)則為左邊的子節(jié)點小當前節(jié)點的值虱疏，右邊的子節(jié)點大于當前節(jié)點的值惹骂，每個節(jié)點只存儲一個鍵值和數(shù)據(jù)的。
2. 平衡二叉樹滿足二叉查找樹特性的基礎上做瞪，如不是空樹对粪，任何一個結點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過 1装蓬。
3. B-TreeB和平衡二叉樹不同著拭，B-Tree屬于多叉樹又名平衡多路查找樹， B-Tree相對于平衡二叉樹牍帚，每個節(jié)點存儲了更多的鍵值(key)和數(shù)據(jù)(data)儡遮，并且每個節(jié)點擁有更多的子節(jié)點。
4. B+Tree和B-Tree不同暗赶，B+Tree在非葉子節(jié)點上鄙币，不保存數(shù)據(jù)，只存儲鍵指針蹂随，能存儲更多的鍵值十嘿，相應的樹的階數(shù)(節(jié)點的子節(jié)點樹)就會更大，樹就會更矮更胖岳锁，如此一來我們查找數(shù)據(jù)進行磁盤的IO次數(shù)有會再次減少绩衷，數(shù)據(jù)查詢的效率也會更快。并且B+樹索引的所有數(shù)據(jù)均存儲在葉子節(jié)點，而且數(shù)據(jù)是按照順序排列的唇聘。那么B+Tree使得范圍查找版姑，排序查找柱搜，分組查找以及去重查找變得異常簡單迟郎。
</article>
