B+樹
B+樹是B樹的一種變體，也屬于平衡多路查找樹，大體結構與B樹相同，包含根節(jié)點、內部節(jié)點和葉子節(jié)點。多用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中，由于B+樹內部節(jié)點不保存數(shù)據(jù)，所以能在內存中存放更多索引，增加緩存命中率。另外因為葉子節(jié)點相連遍歷操作很方便，而且數(shù)據(jù)也具有順序性，便于區(qū)間查找。
B+樹特點
1.B+樹可以定義一個m值作為預定范圍，即m路(階)B+樹。
根節(jié)點可能是葉子節(jié)點，也可能是包含兩個或兩個以上子節(jié)點的節(jié)點。
2.內部節(jié)點如果擁有k個關鍵字則有k+1個子節(jié)點。
3.非葉子節(jié)點不保存數(shù)據(jù)，只保存關鍵字用作索引，所有數(shù)據(jù)都保存在葉子節(jié)點中。
4.非葉子節(jié)點有若干子樹指針，如果非葉子節(jié)點關鍵字為k1,k2,...kn，其中n=m-1，那么第一個子樹關鍵字判斷條件為小于k1，第二個為大于等于k1而小于k2，以此類推，最后一個為大于等于kn，總共可以劃分出m個區(qū)間，即可以有m個分支。（判斷條件其實沒有嚴格的要求，只要能實現(xiàn)對B+樹的數(shù)據(jù)進行定位劃分即可，有些實現(xiàn)使用了m個關鍵字來劃分區(qū)間，也是可以的）
5.所有葉子節(jié)點通過指針鏈相連，且葉子節(jié)點本身按關鍵字的大小從小到大順序排列。
6.自然插入而不進行刪除操作時，葉子節(jié)點項的個數(shù)范圍為[floor(m/2),m-1]，內部節(jié)點項的個數(shù)范圍為[ceil(m/2)-1,m-1]。
7.另外通常B+樹有兩個頭指針，一個指向根節(jié)點一個指向關鍵字最小的葉子節(jié)點。
8.在進行刪除操作時，涉及到索引節(jié)點填充因子和葉子節(jié)點填充因子，一般可設葉子節(jié)點和索引節(jié)點的填充因子都不少于50%。
以下是一棵4階B+樹，
插入操作
假設現(xiàn)在構建一棵四階B+樹，開始插入“A”，直接作為根節(jié)點，
插入“B”，大于“A”，放右邊，
插入“C”，按順序排到最后，
繼續(xù)插入“D”，直接添加的結果如下圖，此時超過了節(jié)點可以存放容量，對于四階B+樹每個節(jié)點最多存放3個項，此時需要執(zhí)行分裂操作，
分裂操作為，先選取待分裂節(jié)點中間位置的項，這里選“C”，然后將“C”項放到父節(jié)點中，因為這里還沒有父節(jié)點，那么直接創(chuàng)建一個新的父節(jié)點存放“C”，而原來小于“C”的那些項作為左子樹，原來大于等于“C”的那些項作為右子樹。這里注意下非葉子節(jié)點存放的都是關鍵字，用作索引的，所以父節(jié)點存放的“C”項不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹。此外，還需要添加一個指針，由左子樹指向右子樹。
繼續(xù)插入“M”，“M”大于“C”，往右子節(jié)點，
分別與“C”“D”比較，大于它們，放到最右邊，
插入“L”，“L”大于“B”，往右子樹，
“L”逐一與節(jié)點內項的值比較，根據(jù)大小放到指定位置，此時觸發(fā)分裂操作，
選取待分裂節(jié)點中間位置的項“L”，然后將“L”項放到父節(jié)點中，按大小順序將“L”放到指定位置，而原來小于“L”的那些項作為左子樹，原來大于等于“L”的那些項作為右子樹。父節(jié)點存放的“L”項不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹。此外，還需要在左子樹中添加一個指向右子樹的指針。
繼續(xù)插入“K”，從根節(jié)點開始查找，逐一比較關鍵字，“K”大于“C”而小于“L”，往第二個分支，
在子節(jié)點中逐一比較，“K”最終落在最右邊，
繼續(xù)插入“J”，從根節(jié)點開始查找，逐一比較關鍵字，“J”大于“C”而小于“L”，往第二個分支，
在子節(jié)點中找到“J”的相應位置，此時超過了節(jié)點的容量，需要進行分裂操作，
選取待分裂節(jié)點中間位置的項“J”，然后將“J”項放到父節(jié)點中，按大小順序將“J”放到指定位置，而原來小于“J”的那些項作為左子樹，原來大于等于“J”的那些項作為右子樹。父節(jié)點存放的“J”項不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹。此外，還需要在左子樹中添加一個指向右子樹的指針。
繼續(xù)插入“I”，從根節(jié)點開始查找，逐一比較關鍵字，“I”大于“C”而小于“J”“L”，往第二個分支，
逐一比較找到“I”的插入位置，
繼續(xù)插入“H”，從根節(jié)點開始查找，逐一比較關鍵字，“H”大于“C”而小于“J”“L”，往第二個分支，
“H”逐一與節(jié)點內的值比較，根據(jù)大小放到指定位置，此時觸發(fā)分裂操作，
選取待分裂節(jié)點中間位置的項“H”，然后將“H”項放到父節(jié)點中，按大小順序將“H”放到指定位置，而原來小于“H”的那些項作為左子樹，原來大于等于“H”的那些項作為右子樹。父節(jié)點存放的“H”項不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹。此外，還需要在左子樹中添加一個指向右子樹的指針。
但此時父節(jié)點超出了容量，父節(jié)點需要繼續(xù)分裂操作，
選取待分裂節(jié)點中間位置的項“J”，然后將“J”項放到父節(jié)點中，但還不存在父節(jié)點，需要創(chuàng)建一個作為父節(jié)點。原來小于“J”的那些項作為左子樹，原來大于“J”的那些項作為右子樹。這是非葉子節(jié)點的分裂，操作對象都是用作索引的關鍵字，不必考慮數(shù)據(jù)存放問題。
插入“G”，從根節(jié)點開始查找，“G”小于“J”，往第一個分支，
逐一比較節(jié)點內項的值，“G”大于“C”小于“H”，往第二個分支，
逐一比較節(jié)點內項的值，找到“G”的位置并插入，
插入“F”，從根節(jié)點開始查找，“F”小于“J”，往第一個分支，
逐一比較節(jié)點內項的值，“F”大于“C”小于“H”，往第二個分支，
逐一比較節(jié)點內項的值，找到“F”的位置并插入，此時觸發(fā)分裂操作，
選取待分裂節(jié)點中間位置的項“F”，然后將“F”項放到父節(jié)點中，按大小順序將“F”放到指定位置，而原來小于“F”的那些項作為左子樹，原來大于等于“F”的那些項作為右子樹。父節(jié)點存放的“F”項不包括數(shù)據(jù)，數(shù)據(jù)仍然存放在右子樹。此外，還需要在左子樹中添加一個指向右子樹的指針。
最后插入“E”，從根節(jié)點開始查找，“E”小于“J”，往第一個分支，
逐一比較節(jié)點內項的值，“E”大于“C”小于“F”，往第二個分支，
逐一比較節(jié)點內項的值，找打“E”適當?shù)奈恢貌⒉迦搿?/p>
從上面插入操作可以總結，插入主要就是涉及到分裂操作，而且要注意到非節(jié)點只保存了關鍵字作為索引，而數(shù)據(jù)都保存在葉子節(jié)點上，此外還需要使用指針將葉子節(jié)點連接起來。最終我們可以看到葉子節(jié)點的項按從小到大排列，因為有了指針使得可以很方便遍歷數(shù)據(jù)。
查找操作
對B+樹的查找與B樹的查找差不多，從根節(jié)點開始查找，通過比較項的值找到對應的分支，然后繼續(xù)往子樹上查找。
比如查找“H”，“H”小于“J”，往第一個分支，
逐一比較節(jié)點中的項，發(fā)現(xiàn)應該往第四個分支，
逐一比較，找到“H”。
遍歷操作
遍歷操作首先是要先找到樹最左邊的葉子節(jié)點，然后就可以通過指針完成整棵樹的遍歷了。
從根節(jié)點開始，一直往第一個分支走，
繼續(xù)往第一個分支走，
發(fā)現(xiàn)已經到葉子節(jié)點了，這就是要找的遍歷的開端，
第一個葉子節(jié)點有兩個項，接著根據(jù)指針跳到第二個葉子節(jié)點，
第二個節(jié)點有三個項，根據(jù)指針繼續(xù)往下一個節(jié)點，
該節(jié)點有兩個項，根據(jù)指針繼續(xù)往下一個節(jié)點，
不斷根據(jù)指針往下，
往下，
完成整棵樹的遍歷。
轉自：https://blog.csdn.net/wangyangzhizhou/article/details/82453443
