B+樹特征
B+ 樹是一種樹數(shù)據(jù)結(jié)構(gòu)，是一個n叉樹，每個節(jié)點通常有多個孩子，一顆B+樹包含根節(jié)點、內(nèi)部節(jié)點和葉子節(jié)點。B+ 樹通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中。 B+ 樹的特點是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對數(shù)時間復(fù)雜度。 B+ 樹元素自底向上插入。
一個m階的B樹具有如下幾個特征：
1.根結(jié)點至少有兩個子女。
2.每個中間節(jié)點都至少包含ceil(m / 2)個孩子，最多有m個孩子。
3.每一個葉子節(jié)點都包含k-1個元素，其中 m/2 <= k <= m。
4.所有的葉子結(jié)點都位于同一層。
5.每個節(jié)點中的元素從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域分劃。
在本例中每一個父節(jié)點都出現(xiàn)在子節(jié)點中，是子節(jié)點最大或者最小的元素。而下面的例子中存在如果父結(jié)點存儲的為子節(jié)點最小值，那么便不需要存儲第一個子節(jié)點的內(nèi)容。【例如子節(jié)點5、8--->10、15--->16、17、18意味著我父節(jié)點存10與16即可。而同樣的例子如果父節(jié)點存最大值，那么便需要存8、15、18 】
在這里，根節(jié)點中最大的元素是15，也就是整個樹中最大的元素。以后無論插入多少元素要始終保持最大元素在根節(jié)點當(dāng)中。
每個葉子節(jié)點都有一個指針，指向下一個數(shù)據(jù)，形成一個有序鏈表。
而只有葉子節(jié)點才會有data，其他都是索引。
B+樹與B樹的區(qū)別
- 有k個子結(jié)點的結(jié)點必然有k個關(guān)鍵碼；
- 非葉結(jié)點僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點中。
- 樹的所有葉結(jié)點構(gòu)成一個有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。
B+樹的查詢操作
在單元查詢的時候，B+樹會自頂向下逐層查找，最終找到匹配的葉子節(jié)點。例如我們查找3 。
而B+樹中間節(jié)點沒有Data數(shù)據(jù)，所以同樣大小的磁盤頁可以容納更多的節(jié)點元素。所以數(shù)據(jù)量相同的情況下，B+樹比B樹更加“矮胖“，因此使用的IO查詢次數(shù)更少。
由于B樹的查找并不穩(wěn)定（最好的情況是查詢根節(jié)點，最壞查詢?nèi)~子節(jié)點）。而B+樹每一次查找都是穩(wěn)定的。
比起B(yǎng)樹，B+樹
①IO次數(shù)更少
②查詢性能很穩(wěn)定
③范圍查詢更簡便
下面我放入一個講解的很好的博客：https://blog.csdn.net/Fmuma/article/details/80287924
B+樹的插入操作
①若為空樹，那么創(chuàng)建一個節(jié)點并將記錄插入其中，此時這個葉子結(jié)點也是根結(jié)點，插入操作結(jié)束。
此處的圖片中例子的介數(shù)為5 。
a）空樹中插入5。
②針對葉子類型結(jié)點：根據(jù)key值找到葉子結(jié)點，向這個葉子結(jié)點插入記錄。插入后，若當(dāng)前結(jié)點key的個數(shù)小于等于m-1（5-1 = 4），則插入結(jié)束。否則將這個葉子結(jié)點分裂成左右兩個葉子結(jié)點，左葉子結(jié)點包含前m/2個（2個）記錄，右結(jié)點包含剩下的記錄，將第m/2+1個（3個）記錄的key進(jìn)位到父結(jié)點中（父結(jié)點一定是索引類型結(jié)點），進(jìn)位到父結(jié)點的key左孩子指針向左結(jié)點，右孩子指針向右結(jié)點。將當(dāng)前結(jié)點的指針指向父結(jié)點，然后執(zhí)行第3步。
b）依次插入8，10，15。
c）插入16
插入16后超過了關(guān)鍵字的個數(shù)限制，所以要進(jìn)行分裂。在葉子結(jié)點分裂時，分裂出來的左結(jié)點2個記錄，右邊3個記錄，中間第三個數(shù)成為索引結(jié)點中的key（10），分裂后當(dāng)前結(jié)點指向了父結(jié)點（根結(jié)點）。結(jié)果如下圖所示。
③針對索引類型結(jié)點：若當(dāng)前結(jié)點key的個數(shù)小于等于m-1（4），則插入結(jié)束。否則，將這個索引類型結(jié)點分裂成兩個索引結(jié)點，左索引結(jié)點包含前(m-1)/2個key（2個），右結(jié)點包含m-(m-1)/2個key（3個），將第m/2個key進(jìn)位到父結(jié)點中，進(jìn)位到父結(jié)點的key左孩子指向左結(jié)點,，進(jìn)位到父結(jié)點的key右孩子指向右結(jié)點。將當(dāng)前結(jié)點的指針指向父結(jié)點，然后重復(fù)第3步。
d）插入17
e）插入18，插入后如下圖所示
當(dāng)前結(jié)點的關(guān)鍵字個數(shù)大于5，進(jìn)行分裂。分裂成兩個結(jié)點，左結(jié)點2個記錄，右結(jié)點3個記錄，關(guān)鍵字16進(jìn)位到父結(jié)點（索引類型）中，將當(dāng)前結(jié)點的指針指向父結(jié)點。
f）插入若干數(shù)據(jù)后
g）在上圖中插入7，結(jié)果如下圖所示
當(dāng)前結(jié)點的關(guān)鍵字個數(shù)超過4，需要分裂。左結(jié)點2個記錄，右結(jié)點3個記錄。分裂后關(guān)鍵字7進(jìn)入到父結(jié)點中，將當(dāng)前結(jié)點的指針指向父結(jié)點，結(jié)果如下圖所示。
當(dāng)前結(jié)點的關(guān)鍵字個數(shù)超過4，需要繼續(xù)分裂。左結(jié)點2個關(guān)鍵字，右結(jié)點2個關(guān)鍵字，關(guān)鍵字16進(jìn)入到父結(jié)點中，將當(dāng)前結(jié)點指向父結(jié)點，結(jié)果如下圖所示。
當(dāng)前結(jié)點的關(guān)鍵字個數(shù)滿足條件，插入結(jié)束。
此處參考了：https://blog.csdn.net/Fmuma/article/details/80287924
B+樹的刪除操作
下面是一顆5階B樹的刪除過程，5階B數(shù)的結(jié)點最少2個key，最多4個key。
如果葉子結(jié)點中沒有相應(yīng)的key，則刪除失敗。否則執(zhí)行下面的步驟。
①刪除葉子結(jié)點中對應(yīng)的key。刪除后若結(jié)點的key的個數(shù)大于等于Math.ceil(m/2) – 1（>=2），刪除操作結(jié)束，否則執(zhí)行第2步。
a）初始狀態(tài)
b）刪除22,刪除后結(jié)果如下圖
刪除后葉子結(jié)點中key的個數(shù)大于等于2，刪除結(jié)束。
②若結(jié)點的key的個數(shù)小于Math.ceil(m/2) – 1（<2），且兄弟結(jié)點key有富余（大于Math.ceil(m/2)– 1）（>2），向兄弟結(jié)點借一個記錄，同時用借到的key替換父結(jié)（指當(dāng)前結(jié)點和兄弟結(jié)點共同的父結(jié)點）點中的key，刪除結(jié)束。否則執(zhí)行第3步。
c）刪除15，刪除后的結(jié)果如下圖所示。
刪除后當(dāng)前結(jié)點只有一個key，不滿足條件，而兄弟結(jié)點有三個key，可以從兄弟結(jié)點借一個關(guān)鍵字為9的記錄,同時更新將父結(jié)點中的關(guān)鍵字由10也變?yōu)?，刪除結(jié)束。
③若結(jié)點的key的個數(shù)小于Math.ceil(m/2) – 1（<2），且兄弟結(jié)點中沒有富余的key（小于Math.ceil(m/2)– 1），則當(dāng)前結(jié)點和兄弟結(jié)點合并成一個新的葉子結(jié)點，并刪除父結(jié)點中的key，將當(dāng)前結(jié)點指向父結(jié)點（必為索引結(jié)點），執(zhí)行第4步（第4步以后的操作和B樹就完全一樣了，主要是為了更新索引結(jié)點）。
d）刪除7，刪除后的結(jié)果如下圖所示
當(dāng)前結(jié)點關(guān)鍵字個數(shù)小于2，（左）兄弟結(jié)點中的也沒有富余的關(guān)鍵字（當(dāng)前結(jié)點還有個右兄弟，不過選擇任意一個進(jìn)行分析就可以了，這里我們選擇了左邊的），所以當(dāng)前結(jié)點和兄弟結(jié)點合并，并刪除父結(jié)點中的key，當(dāng)前結(jié)點指向父結(jié)點。
④若索引結(jié)點的key的個數(shù)大于等于Math.ceil(m/2) – 1（>=2），則刪除操作結(jié)束。否則執(zhí)行第5步。
⑤若兄弟結(jié)點有富余，父結(jié)點key下移，兄弟結(jié)點key上移，刪除結(jié)束。否則執(zhí)行第6步
⑥當(dāng)前結(jié)點和兄弟結(jié)點及父結(jié)點下移key合并成一個新的結(jié)點。將當(dāng)前結(jié)點指向父結(jié)點，重復(fù)第4步。
此時當(dāng)前結(jié)點的關(guān)鍵字個數(shù)小于2，兄弟結(jié)點的關(guān)鍵字也沒有富余，所以父結(jié)點中的關(guān)鍵字下移，和兩個孩子結(jié)點合并，結(jié)果如下圖所示。
注意，通過B+樹的刪除操作后，索引結(jié)點中存在的key，不一定在葉子結(jié)點中存在對應(yīng)的記錄。
