一、二叉樹

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

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

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

二、平衡二叉樹

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

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

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

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

三、紅黑樹

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

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

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

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

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

四、B樹(B-tree)

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

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

2??規(guī)則
①排序方式：所有節(jié)點(diǎn)關(guān)鍵字是按遞增次序排列，并遵循左小右大原則。
②子節(jié)點(diǎn)數(shù)：非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)>1，且<=M ，且M>=2，空樹除外(注：M階代表一個樹節(jié)點(diǎn)最多有多少個查找路徑，M=M路，當(dāng)M=2則是2叉樹，M=3則是3叉)。
③關(guān)鍵字?jǐn)?shù)：枝節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量大于等于ceil(m/2)-1個且小于等于M-1個(注：ceil()是個朝正無窮方向取整的函數(shù)。如ceil(1.1)結(jié)果為2)。
④所有葉子節(jié)點(diǎn)均在同一層、葉子節(jié)點(diǎn)除了包含了關(guān)鍵字和關(guān)鍵字記錄的指針外也有指向其子節(jié)點(diǎn)的指針只不過其指針地址都為null對應(yīng)下圖最后一層節(jié)點(diǎn)的空格子。

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

3??B樹的查詢流程
如要從上圖中找到E，查找流程如下：
①獲取根節(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，當(dāng)前根節(jié)點(diǎn)關(guān)鍵字為M，E<M(26個字母順序)，所以往找到指向左邊的子節(jié)點(diǎn)(二分法規(guī)則，左小右大，左邊放小于當(dāng)前節(jié)點(diǎn)值的子節(jié)點(diǎn)、右邊放大于當(dāng)前節(jié)點(diǎn)值的子節(jié)點(diǎn))。
②拿到關(guān)鍵字D和G，D<E<G 所以直接找到D和G中間的節(jié)點(diǎn)。
③拿到E和F，因為E=E，所以直接返回關(guān)鍵字和指針信息(如果樹結(jié)構(gòu)里面沒有包含所要查找的節(jié)點(diǎn)則返回null)。

4??B樹的插入節(jié)點(diǎn)流程
定義一個5階樹(平衡5路查找樹)，現(xiàn)在要把3、8、31、11、23、29、50、28這些數(shù)字構(gòu)建出一個5階樹出來。遵循規(guī)則：
①節(jié)點(diǎn)拆分規(guī)則：當(dāng)前是要組成一個5路查找樹，那么此時m=5，關(guān)鍵字?jǐn)?shù)必須<=5-1(這里關(guān)鍵字?jǐn)?shù)>4就要進(jìn)行節(jié)點(diǎn)拆分)。
②排序規(guī)則：滿足節(jié)點(diǎn)本身比左邊節(jié)點(diǎn)大，比右邊節(jié)點(diǎn)小。

先插入 3、8、31、11：

再插入23、29：

再插入50、28：

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

規(guī)則：
①節(jié)點(diǎn)合并規(guī)則：當(dāng)前是要組成一個5路查找樹，那么此時m=5，關(guān)鍵字?jǐn)?shù)必須大于等于ceil(5/2)(這里關(guān)鍵字?jǐn)?shù)<2就要進(jìn)行節(jié)點(diǎn)合并)。
②滿足節(jié)點(diǎn)本身比左邊節(jié)點(diǎn)大，比右邊節(jié)點(diǎn)小的排序規(guī)則。

③關(guān)鍵字?jǐn)?shù)小于二時先從子節(jié)點(diǎn)取，子節(jié)點(diǎn)沒有符合條件時就向父節(jié)點(diǎn)取，取中間值往父節(jié)點(diǎn)放。

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

五、B+樹

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

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

百度百科算法結(jié)構(gòu)示意圖

維基百科算法結(jié)構(gòu)示意圖

3??特點(diǎn)
①B+樹的層級更少：相較于B樹B+每個非葉子節(jié)點(diǎn)存儲的關(guān)鍵字?jǐn)?shù)更多，樹的層級更少所以查詢數(shù)據(jù)更快。
②B+樹查詢速度更穩(wěn)定：B+所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定。
③B+樹天然具備排序功能：B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會比B樹高。
④B+樹全節(jié)點(diǎn)遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點(diǎn)即可，而不需要像B樹對每一層進(jìn)行遍歷，這有利于數(shù)據(jù)庫做全表掃描。
⑤B樹相對于B+樹的優(yōu)點(diǎn)是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點(diǎn)很近，而B樹的非葉子節(jié)點(diǎn)本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時候會要比B+樹快。

六、B*樹

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

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

七、 總結(jié)

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

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

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

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