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