一、二叉樹

1??二叉查找樹的特點就是左子樹的節(jié)點值比父親節(jié)點小街夭，而右子樹的節(jié)點值比父親節(jié)點大砰碴，如圖：

基于二叉查找樹的這種特點，在查找某個節(jié)點的時候板丽，可以采取類似于二分查找的思想呈枉，快速找到某個節(jié)點。n 個節(jié)點的二叉查找樹埃碱，正常的情況下猖辫，查找的時間復雜度為 O(logN)。之所以說是正常情況下砚殿，是因為二叉查找樹有可能出現(xiàn)一種極端的情況啃憎，例如：

這種情況也是滿足二叉查找樹的條件，然而似炎，此時的二叉查找樹已經(jīng)近似退化為一條鏈表辛萍，這樣的二叉查找樹的查找時間復雜度頓時變成了 O(n)。由此必須防止這種情況發(fā)生羡藐，為了解決這個問題贩毕，于是引申出了平衡二叉樹。

二仆嗦、平衡二叉樹

1??概念
平衡二叉樹是基于二分法的策略提高數(shù)據(jù)的查找速度的二叉樹的數(shù)據(jù)結構辉阶。

2??規(guī)則
平衡二叉樹是采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個樹形結構的數(shù)據(jù)，用這個樹形結構的數(shù)據(jù)減少無關數(shù)據(jù)的檢索瘩扼，大大的提升了數(shù)據(jù)檢索的速度谆甜；平衡二叉樹的數(shù)據(jù)結構組裝過程有以下規(guī)則：
①非葉子節(jié)點只能允許最多兩個子節(jié)點存在。
②每一個非葉子節(jié)點數(shù)據(jù)分布規(guī)則為左邊的子節(jié)點小當前節(jié)點的值集绰，右邊的子節(jié)點大于當前節(jié)點的值(這里值是基于自己的算法規(guī)則而定的规辱，比如hash值)。

平衡樹的層級結構：平衡二叉樹的查詢性能和樹的層級(高度h)成反比栽燕，h值越小查詢越快罕袋。為了保證樹的結構左右兩端數(shù)據(jù)大致平衡。降低二叉樹的查詢難度一般會采用一種算法機制實現(xiàn)節(jié)點數(shù)據(jù)結構的平衡纫谅，實現(xiàn)了這種算法的有比如Treap炫贤、紅黑樹。使用平衡二叉樹能保證數(shù)據(jù)的左右兩邊的節(jié)點層級相差不會大于1付秕，通過這樣避免樹形結構由于刪除增加變成線性鏈表影響查詢效率兰珍，保證數(shù)據(jù)平衡的情況下查找數(shù)據(jù)的速度近于二分法查找：

3??平衡二叉樹特點：
①非葉子節(jié)點最多擁有兩個子節(jié)點。
②非葉子節(jié)點值大于左邊子節(jié)點询吴、小于右邊子節(jié)點掠河。
③樹的左右兩邊的層級數(shù)相差不會大于1亮元。
④沒有值相等重復的節(jié)點。

三唠摹、紅黑樹

1??為什么有了平衡樹還需要紅黑樹爆捞？
雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點，能夠把查找時間控制在 O(logn)勾拉，不過卻不是最佳的煮甥，因為平衡樹要求每個節(jié)點的左子樹和右子樹的高度差至多等于1，這個要求實在是太嚴了藕赞，導致每次進行插入/刪除節(jié)點的時候成肘，幾乎都會破壞平衡樹的第二個規(guī)則，進而都需要通過左旋和右旋來進行調整斧蜕，使之再次成為一顆符合要求的平衡樹双霍。

2??紅黑樹的特性
顯然，如果在插入批销、刪除很頻繁的場景中洒闸，平衡樹需要頻繁調整，這會使平衡樹的性能大打折扣均芽，為了解決這個問題丘逸，于是有了紅黑樹，紅黑樹具有如下特點：
①每個節(jié)點或者是黑色骡技，或者是紅色鸣个。
②根節(jié)點是黑色羞反。
③每個葉子節(jié)點(NIL)是黑色布朦。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點]
④如果一個節(jié)點是紅色的昼窗，則它的子節(jié)點必須是黑色的是趴。
⑤從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。[這里指到葉子節(jié)點的路徑]

包含n個內部節(jié)點的紅黑樹的高度是 O(log(n))澄惊。如圖：

3??紅黑樹的使用場景
java中使用到紅黑樹的有TreeSet和JDK1.8的HashMap唆途。紅黑樹的插入和刪除都要滿足以上5個特性，操作非常復雜掸驱，為什么要使用紅黑樹肛搬？原因：
紅黑樹是一種平衡樹，復雜的定義和規(guī)則都是為了保證樹的平衡性毕贼。如果樹不保證平衡性就是下圖：很顯然這就變成一個鏈表了温赔。

保證平衡性的最大的目的就是降低樹的高度，因為樹的查找性能取決于樹的高度鬼癣。所以樹的高度越低搜索的效率越高陶贼！

四啤贩、B樹(B-tree)

B樹和B-tree，其實是同一種樹拜秧。

1??概念
B樹和平衡二叉樹稍有不同的是B樹屬于多叉樹又名平衡多路查找樹(查找路徑不只兩個)痹屹，數(shù)據(jù)庫索引技術里大量使用B樹和B+樹的數(shù)據(jù)結構。

2??規(guī)則
①排序方式：所有節(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é)點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節(jié)點的指針只不過其指針地址都為null對應下圖最后一層節(jié)點的空格子爷速。

用一個圖和一個實際的例子來理解B樹(便于理解直接用實際字母的大小來排列C>B>A)：

3??B樹的查詢流程
如要從上圖中找到E央星，查找流程如下：
①獲取根節(jié)點的關鍵字進行比較，當前根節(jié)點關鍵字為M惫东，E<M(26個字母順序)莉给，所以往找到指向左邊的子節(jié)點(二分法規(guī)則，左小右大廉沮，左邊放小于當前節(jié)點值的子節(jié)點颓遏、右邊放大于當前節(jié)點值的子節(jié)點)。
②拿到關鍵字D和G滞时，D<E<G 所以直接找到D和G中間的節(jié)點叁幢。
③拿到E和F，因為E=E坪稽，所以直接返回關鍵字和指針信息(如果樹結構里面沒有包含所要查找的節(jié)點則返回null)曼玩。

4??B樹的插入節(jié)點流程
定義一個5階樹(平衡5路查找樹)，現(xiàn)在要把3窒百、8黍判、31、11篙梢、23顷帖、29、50、28這些數(shù)字構建出一個5階樹出來窟她。遵循規(guī)則：
①節(jié)點拆分規(guī)則：當前是要組成一個5路查找樹陈症，那么此時m=5，關鍵字數(shù)必須<=5-1(這里關鍵字數(shù)>4就要進行節(jié)點拆分)震糖。
②排序規(guī)則：滿足節(jié)點本身比左邊節(jié)點大录肯，比右邊節(jié)點小。

先插入 3吊说、8论咏、31、11：

再插入23颁井、29：

再插入50厅贪、28：

5??B樹節(jié)點的刪除

規(guī)則：
①節(jié)點合并規(guī)則：當前是要組成一個5路查找樹，那么此時m=5雅宾，關鍵字數(shù)必須大于等于ceil(5/2)(這里關鍵字數(shù)<2就要進行節(jié)點合并)养涮。
②滿足節(jié)點本身比左邊節(jié)點大，比右邊節(jié)點小的排序規(guī)則眉抬。

③關鍵字數(shù)小于二時先從子節(jié)點取贯吓，子節(jié)點沒有符合條件時就向父節(jié)點取，取中間值往父節(jié)點放蜀变。

特點：
B樹相對于平衡二叉樹的不同是悄谐，每個節(jié)點包含的關鍵字增多了，特別是在B樹應用到數(shù)據(jù)庫中的時候库北，數(shù)據(jù)庫充分利用了磁盤塊的原理(磁盤數(shù)據(jù)存儲是采用塊的形式存儲的爬舰，每個塊的大小為4K，每次IO進行數(shù)據(jù)讀取時寒瓦，同一個磁盤塊的數(shù)據(jù)可以一次性讀取出來)把節(jié)點大小限制和充分使用在磁盤快大小范圍情屹；把樹的節(jié)點關鍵字增多后樹的層級比原來的二叉樹少了，減少數(shù)據(jù)查找的次數(shù)和復雜度孵构。

五屁商、B+樹

1??概念
B+樹是B樹的一個升級版烟很，B+樹更充分的利用了節(jié)點的空間颈墅，讓查詢速度更加穩(wěn)定，其速度完全接近于二分法查找雾袱。為什么說B+樹查找的效率要比B樹更高恤筛、更穩(wěn)定？

2??規(guī)則
①B+跟B樹不同芹橡。B+樹的非葉子節(jié)點不保存關鍵字記錄的指針毒坛，只進行數(shù)據(jù)索引，這樣使得B+樹每個非葉子節(jié)點所能保存的關鍵字大大增加。
②B+樹葉子節(jié)點保存了父節(jié)點的所有關鍵字記錄的指針煎殷，所有數(shù)據(jù)地址必須要到葉子節(jié)點才能獲取到屯伞。所以每次數(shù)據(jù)查詢的次數(shù)都一樣。
③B+樹葉子節(jié)點的關鍵字從小到大有序排列豪直，左邊結尾數(shù)據(jù)都會保存右邊節(jié)點開始數(shù)據(jù)的指針劣摇。
④非葉子節(jié)點的子節(jié)點數(shù)=關鍵字數(shù)(百度百科。根據(jù)各種資料弓乙，這里有兩種算法的實現(xiàn)方式末融，另一種為非葉節(jié)點的關鍵字數(shù)=子節(jié)點數(shù)-1(維基百科)，雖然數(shù)據(jù)排列結構不一樣暇韧，但其原理還是一樣的勾习。Mysql 的 B+樹是用第一種方式實現(xiàn))。

百度百科算法結構示意圖

維基百科算法結構示意圖

3??特點
①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)點是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點很近荧库，而B樹的非葉子節(jié)點本身存有關鍵字其數(shù)據(jù)的地址堰塌，所以這種數(shù)據(jù)檢索的時候會要比B+樹快。

六分衫、B*樹

1??規(guī)則
B樹是B+樹的變種场刑，區(qū)別如下：
①首先是關鍵字個數(shù)限制問題，B+樹初始化的關鍵字初始化個數(shù)是cei(m/2)蚪战，B樹的初始化個數(shù)為cei(2/3m)牵现。
②B+樹節(jié)點滿時就會分裂，而B樹節(jié)點滿時會檢查兄弟節(jié)點是否滿(因為每個節(jié)點都有指向兄弟的指針)邀桑，如果兄弟節(jié)點未滿則向兄弟節(jié)點轉移關鍵字瞎疼，如果兄弟節(jié)點已滿曾掂，則從當前節(jié)點和兄弟節(jié)點各拿出1/3的數(shù)據(jù)創(chuàng)建一個新的節(jié)點出來拿愧。

2??特點
在B+樹的基礎上因其初始化的容量變大，使得節(jié)點空間使用率更高鹏溯，而又存有兄弟節(jié)點的指針，可以向兄弟節(jié)點轉移關鍵字的特性使得B*樹額分解次數(shù)變得更少太抓；

七空闲、 總結

1??相同思想和策略
從平衡二叉樹、B樹走敌、B+樹进副、B*樹總體來看它們的貫徹的思想是相同的，都是采用二分法和數(shù)據(jù)平衡策略來提升查找數(shù)據(jù)的速度悔常。

2??不同的方式的磁盤空間利用
不同點是它們一個一個在演變的過程中通過IO從磁盤讀取數(shù)據(jù)的原理進行一步步的演變影斑，每一次演變都是為了讓節(jié)點的空間更合理的運用起來，從而使樹的層級減少達到快速查找數(shù)據(jù)的目的机打。

作者：日常更新
鏈接：http://www.reibang.com/p/b597aa97c9de

簡書號 同 公號 【碼農(nóng)開花】一起學習成長
我會一直分享Java干貨矫户，也會分享免費的學習資料課程和面試寶典
回復：【計算機】【設計模式】【面試】有驚喜哦