推薦：https://ivanzz1001.github.io/records/post/data-structure/2018/06/16/ds-bplustree
一、B樹和B+樹的區(qū)別
這都是由于B+樹和B具有這不同的存儲(chǔ)結(jié)構(gòu)所造成的區(qū)別，以一個(gè)m階樹為例。
（1）關(guān)鍵字的數(shù)量不同；B+樹中分支結(jié)點(diǎn)有m個(gè)關(guān)鍵字，其葉子結(jié)點(diǎn)也有m個(gè)，其關(guān)鍵字只是起到了一個(gè)索引的作用，但是B樹雖然也有m個(gè)子結(jié)點(diǎn)，但是其只擁有m-1個(gè)關(guān)鍵字。
（2）存儲(chǔ)的位置不同；B+樹中的數(shù)據(jù)都存儲(chǔ)在葉子結(jié)點(diǎn)上，也就是其所有葉子結(jié)點(diǎn)的數(shù)據(jù)組合起來就是完整的數(shù)據(jù)，但是B樹的數(shù)據(jù)存儲(chǔ)在每一個(gè)結(jié)點(diǎn)中，并不僅僅存儲(chǔ)在葉子結(jié)點(diǎn)上。
（3）分支結(jié)點(diǎn)的構(gòu)造不同；B+樹的分支結(jié)點(diǎn)僅僅存儲(chǔ)著關(guān)鍵字信息和兒子的指針（這里的指針指的是磁盤塊的偏移量），也就是說內(nèi)部結(jié)點(diǎn)僅僅包含著索引信息。
（4）查詢不同；B樹在找到具體的數(shù)值以后，則結(jié)束，而B+樹則需要通過索引找到葉子結(jié)點(diǎn)中的數(shù)據(jù)才結(jié)束，也就是說B+樹的搜索過程中走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。
二、B+樹的定義：
1、其定義基本與B-樹同；
2、非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同；?
3、非葉子結(jié)點(diǎn)的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；?
4、為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；
5、所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)。
B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中），其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；
三、B+的特性：
1、所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
2、不可能在非葉子結(jié)點(diǎn)命中；
3、非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
4、更適合文件索引系統(tǒng)。
四、B+樹的操作：查詢、插入、刪除
? ?1、查詢：有兩種查找運(yùn)算，
（1）從最小關(guān)鍵字起順序查找；
（2）從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找
在查找時(shí)，若非終端節(jié)點(diǎn)上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)向下直到葉子節(jié)點(diǎn)。因此，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子節(jié)點(diǎn)的路徑。其余同B-樹的查找類似。
B+樹的優(yōu)勢(shì)在于查找效率上，下面我們做一具體說明：
首先，Ｂ＋樹的查找和Ｂ樹一樣，類似于二叉查找樹。起始于根節(jié)點(diǎn)，自頂向下遍歷樹，選擇其分離值在要查找值的任意一邊的子指針。在節(jié)點(diǎn)內(nèi)部典型的使用是二分查找來確定這個(gè)位置。
?。?）、不同的是，Ｂ＋樹中間節(jié)點(diǎn)沒有衛(wèi)星數(shù)據(jù)（索引元素所指向的數(shù)據(jù)記錄），只有索引，而Ｂ樹每個(gè)結(jié)點(diǎn)中的每個(gè)關(guān)鍵字都有衛(wèi)星數(shù)據(jù)；這就意味著同樣的大小的磁盤頁可以容納更多節(jié)點(diǎn)元素，在相同的數(shù)據(jù)量下，Ｂ＋樹更加“矮胖”，ＩＯ操作更少
B樹的衛(wèi)星數(shù)據(jù)：
B+樹的衛(wèi)星數(shù)據(jù)：
需要補(bǔ)充的是，在數(shù)據(jù)庫的聚集索引（Clustered Index）中，葉子節(jié)點(diǎn)直接包含衛(wèi)星數(shù)據(jù)。在非聚集索引（NonClustered Index）中，葉子節(jié)點(diǎn)帶有指向衛(wèi)星數(shù)據(jù)的指針。
?。?）、其次，因?yàn)樾l(wèi)星數(shù)據(jù)的不同，導(dǎo)致查詢過程也不同；Ｂ樹的查找只需找到匹配元素即可，最好情況下查找到根節(jié)點(diǎn)，最壞情況下查找到葉子結(jié)點(diǎn)，所說性能很不穩(wěn)定，而Ｂ＋樹每次必須查找到葉子結(jié)點(diǎn)，性能穩(wěn)定
?。?）、在范圍查詢方面，B+樹的優(yōu)勢(shì)更加明顯
B樹的范圍查找需要不斷依賴中序遍歷。首先二分查找到范圍下限，在不斷通過中序遍歷，知道查找到范圍的上限即可。整個(gè)過程比較耗時(shí)。
而B+樹的范圍查找則簡單了許多。首先通過二分查找，找到范圍下限，然后同過葉子結(jié)點(diǎn)的鏈表順序遍歷，直至找到上限即可，整個(gè)過程簡單許多，效率也比較高。
例如：同樣查找范圍[3-11]，兩者的查詢過程如下：?
B樹的查找過程：?
B+樹的查找過程：
2、插入：
B+樹的插入與B樹的插入過程類似。不同的是B+樹在葉結(jié)點(diǎn)上進(jìn)行，如果葉結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)超過m，就必須分裂成關(guān)鍵碼數(shù)目大致相同的兩個(gè)結(jié)點(diǎn)，并保證上層結(jié)點(diǎn)中有這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵碼。
3、刪除：
B+樹中的關(guān)鍵碼在葉結(jié)點(diǎn)層刪除后，其在上層的復(fù)本可以保留，作為一個(gè)”分解關(guān)鍵碼”存在，如果因?yàn)閯h除而造成結(jié)點(diǎn)中關(guān)鍵碼數(shù)小于ceil(m/2)，其處理過程與B-樹的處理一樣。在此，我就不多做介紹了。
【小結(jié)】B+樹相比B樹的優(yōu)勢(shì)：?
1.單一節(jié)點(diǎn)存儲(chǔ)更多的元素，使得查詢的IO次數(shù)更少；?
2.所有查詢都要查找到葉子節(jié)點(diǎn)，查詢性能穩(wěn)定；?
3.所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢。
五、B+樹的用途：
B+樹主要適用于索引操作。為什么說B+樹比B-樹根適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？
B+樹的磁盤讀寫代價(jià)更低: B+樹的內(nèi)部節(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部節(jié)點(diǎn)先對(duì)B-樹更小。如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來說IO讀寫次數(shù)也就降低了。舉個(gè)例子：假設(shè)磁盤中的一個(gè)盤塊容納16bytes，而一個(gè)關(guān)鍵字2bytes, 一個(gè)關(guān)鍵字具體信息指針2bytes。一棵9階B-樹(一個(gè)節(jié)點(diǎn)最多8個(gè)關(guān)鍵字）的內(nèi)部節(jié)點(diǎn)需要2個(gè)盤塊。而B+樹內(nèi)部節(jié)點(diǎn)只需要1個(gè)盤塊。當(dāng)需要把內(nèi)部節(jié)點(diǎn)讀入內(nèi)存的時(shí)候，B-樹就比B+樹多一次盤塊查找時(shí)間（在磁盤中就是盤片旋轉(zhuǎn)時(shí)間）
B+樹的查詢效率更加穩(wěn)定: 由于非終節(jié)點(diǎn)并不是最終指向文件內(nèi)容的節(jié)點(diǎn)，而只是葉子節(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。
【注】：Mysql中B+樹的應(yīng)用：詳見：https://ivanzz1001.github.io/records/post/data-structure/2018/06/16/ds-bplustree
六、B*樹
是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針。
B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；
B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針；B*樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針；所以，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高。
【小結(jié)】
多路搜索樹，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)；所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中；
在B-樹基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引；B+樹總是到葉子結(jié)點(diǎn)才命中；
在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；
【注】不同樹的實(shí)際應(yīng)用場景：
1、AVL樹的應(yīng)用:
最早的平衡二叉樹之一。應(yīng)用相對(duì)其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對(duì)進(jìn)程地址空間的管理用到了AVL樹。
2、紅黑樹的應(yīng)用：
紅黑樹的應(yīng)用比較廣泛，主要是用它來存儲(chǔ)有序的數(shù)據(jù)，它的時(shí)間復(fù)雜度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內(nèi)存的管理，都是通過紅黑樹去實(shí)現(xiàn)的。
3、B+樹的應(yīng)用：詳見B+樹
