導(dǎo)讀平衡二叉樹B樹和B樹平衡二叉樹概念平衡二叉樹是基于二分法的策略提高數(shù)據(jù)的查找速度的二叉樹的數(shù)據(jù)結(jié)構(gòu)。特點(diǎn)平衡二叉樹是采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個(gè)樹形....平衡二叉樹B樹和B 樹平衡二叉樹概念

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

特點(diǎn)

平衡二叉樹是采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)，用這個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)減少無關(guān)數(shù)據(jù)的檢索，大大的提升了數(shù)據(jù)檢索的速度；平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)組裝過程有以下規(guī)則：

1. 非葉子節(jié)點(diǎn)只能允許最多兩個(gè)子節(jié)點(diǎn)存在。
2. 每一個(gè)非葉子節(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)

因?yàn)槠胶舛鏄洳樵冃阅芎蜆涞膶蛹?jí)（h 高度）成反比，h 值越小查詢?cè)娇臁榱吮ＷC樹的結(jié)構(gòu)左右兩端數(shù)據(jù)大致平衡降低二叉樹的查詢難度一般會(huì)采用一種算法機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的平衡，實(shí)現(xiàn)了這種算法的有比如 Treap、紅黑樹，使用平衡二叉樹能保證數(shù)據(jù)的左右兩邊的節(jié)點(diǎn)層級(jí)相差不會(huì)大于 1。

通過這樣避免樹形結(jié)構(gòu)由于刪除增加變成線性鏈表影響查詢效率，保證數(shù)據(jù)平衡的情況下查找數(shù)據(jù)的速度近于二分法查找：

總結(jié)

總結(jié)平衡二叉樹特點(diǎn)：

1. 非葉子節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)；
2. 非葉子節(jié)值大于左邊子節(jié)點(diǎn)、小于右邊子節(jié)點(diǎn)；
3. 樹的左右兩邊的層級(jí)數(shù)相差不會(huì)大于 1;
4. 沒有值相等重復(fù)的節(jié)點(diǎn);

B樹(B-tree)概念

B 樹和平衡二叉樹稍有不同的是 B 樹屬于多叉樹又名平衡多路查找樹（查找路徑不只兩個(gè)），數(shù)據(jù)庫索引技術(shù)里大量使用者 B 樹和 B 樹的數(shù)據(jù)結(jié)構(gòu)，讓我們來看看他有什么特點(diǎn)。

規(guī)則

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

最后我們用一個(gè)圖和一個(gè)實(shí)際的例子來理解 B 樹（這里為了理解方便我就直接用實(shí)際字母的大小來排列 C>B>A）

B樹的查詢流程

如上圖我要從上圖中找到 E 字母，查找流程如下

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

B樹的插入節(jié)點(diǎn)流程

定義一個(gè) 5 階樹（平衡 5 路查找樹），現(xiàn)在我們要把 3、8、31、11、23、29、50、28 這些數(shù)字構(gòu)建出一個(gè) 5 階樹出來，遵循如下規(guī)則：

1. 節(jié)點(diǎn)拆分規(guī)則：當(dāng)前是要組成一個(gè) 5 路查找樹，那么此時(shí) m=5，關(guān)鍵字?jǐn)?shù)必須 <=5-1（這里關(guān)鍵字?jǐn)?shù) >4 就要進(jìn)行節(jié)點(diǎn)拆分）；
2. 排序規(guī)則：滿足節(jié)點(diǎn)本身比左邊節(jié)點(diǎn)大，比右邊節(jié)點(diǎn)小的排序規(guī)則；

先插入 3、8、31、11

再插入 23、29

再插入 50、28

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

1. 節(jié)點(diǎn)合并規(guī)則：當(dāng)前是要組成一個(gè) 5 路查找樹，那么此時(shí) m=5，關(guān)鍵字?jǐn)?shù)必須大于等于 ceil（5/2）（這里關(guān)鍵字?jǐn)?shù) <2 就要進(jìn)行節(jié)點(diǎn)合并）；
2. 滿足節(jié)點(diǎn)本身比左邊節(jié)點(diǎn)大，比右邊節(jié)點(diǎn)小的排序規(guī)則；
3. 關(guān)鍵字?jǐn)?shù)小于二時(shí)先從子節(jié)點(diǎn)取，子節(jié)點(diǎn)沒有符合條件時(shí)就向向父節(jié)點(diǎn)取，取中間值往父節(jié)點(diǎn)放；

特點(diǎn)

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

B 樹概念

B 樹是 B 樹的一個(gè)升級(jí)版，相對(duì)于 B 樹來說 B 樹更充分的利用了節(jié)點(diǎn)的空間，讓查詢速度更加穩(wěn)定，其速度完全接近于二分法查找。為什么說 B 樹查找的效率要比 B 樹更高、更穩(wěn)定；我們先看看兩者的區(qū)別。

規(guī)則

1. B 跟 B 樹不同 B 樹的非葉子節(jié)點(diǎn)不保存關(guān)鍵字記錄的指針，只進(jìn)行數(shù)據(jù)索引，這樣使得 B 樹每個(gè)非葉子節(jié)點(diǎn)所能保存的關(guān)鍵字大大增加；
2. B 樹葉子節(jié)點(diǎn)保存了父節(jié)點(diǎn)的所有關(guān)鍵字記錄的指針，所有數(shù)據(jù)地址必須要到葉子節(jié)點(diǎn)才能獲取到。所以每次數(shù)據(jù)查詢的次數(shù)都一樣；
3. B 樹葉子節(jié)點(diǎn)的關(guān)鍵字從小到大有序排列，左邊結(jié)尾數(shù)據(jù)都會(huì)保存右邊節(jié)點(diǎn)開始數(shù)據(jù)的指針；
4. 非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)=關(guān)鍵字?jǐn)?shù)。

特點(diǎn)

1. B 樹的層級(jí)更少：相較于 B 樹 B 樹每個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)的關(guān)鍵字?jǐn)?shù)更多，樹的層級(jí)更少所以查詢數(shù)據(jù)更快。
2. B 樹查詢速度更穩(wěn)定：B 樹所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定。
3. B 樹天然具備排序功能：B 樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會(huì)比 B 樹高。
4. B 樹全節(jié)點(diǎn)遍歷更快：B 樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點(diǎn)即可，，而不需要像 B 樹一樣需要對(duì)每一層進(jìn)行遍歷，這有利于數(shù)據(jù)庫做全表掃描。

B 樹相對(duì)于 B 樹的優(yōu)點(diǎn)是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點(diǎn)很近，而 B 樹的非葉子節(jié)點(diǎn)本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時(shí)候會(huì)要比 B 樹快。

B*樹規(guī)則

B* 樹是 B 樹的變種，相對(duì)于 B 樹他們的不同之處如下：

1. 首先是關(guān)鍵字個(gè)數(shù)限制問題，B 樹初始化的關(guān)鍵字初始化個(gè)數(shù)是 cei(m/2)，b* 樹的初始化個(gè)數(shù)為（cei(2/3*m)）。
2. B 樹節(jié)點(diǎn)滿時(shí)就會(huì)分裂，而 B* 樹節(jié)點(diǎn)滿時(shí)會(huì)檢查兄弟節(jié)點(diǎn)是否滿（因?yàn)槊總€(gè)節(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)建一個(gè)新的節(jié)點(diǎn)出來。

特點(diǎn)

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