目錄
一、2-3樹
二、B-樹
三、B+樹
一、2-3樹
2-3樹是最簡單的B-樹（或-樹）結構，其每個非葉節點都有兩個或三個子女，而且所有葉都在統一層上。2-3樹不是二叉樹，其節點可擁有3個孩子。不過，2-3樹與滿二叉樹相似。若某棵2-3樹不包含3-節點，則看上去像滿二叉樹，其所有内部節點都可有兩個孩子，所有的葉子都在同一級别。另一方面，2-3樹的一個内部節點确實有3個孩子，故比相同高度的滿二叉樹的節點更多。高為h的2-3樹包含的節點數大于等于高度為h的滿二叉樹的節點數，即至少有2^h-1個節點。換一個角度分析，包含n的節點的2-3樹的高度不大于[log2(n+1)](即包含n個節點的二叉樹的最小高度)。
例如，下圖顯示高度為3的2-3樹。包含兩個孩子的節點稱為2-節點，二叉樹中的節點都是2-節點；包含三個孩子的節點稱為3-節點。
将資料項放入2-3樹節點中的規則是：
（1）2-節點有兩個孩子，必含一個資料項，其查找關鍵字大于左孩子的查找關鍵字，而小于右孩子的查找關鍵字。
（2）3-節點有三個孩子 ，必含兩個資料項，其查找關鍵字S和L滿足下列關系：S大于左孩子的查找關鍵字，而小于中孩子的查找關鍵字；L大于中孩子的查找關鍵字，而小于右孩子的查找關鍵字。
（3）葉子可以包含一個或兩個資料項。
二、B-樹
B-樹和B樹其實是一個東西，B樹就是一種平衡的多路查找樹。
B-樹中所有結點中孩子結點個數的最大值成為B-樹的階，通常用m表示，從查找效率考慮，一般要求m>=3。一棵m階B-樹或者是一棵空樹，或者是滿足以下條件的m叉樹。
1）每個結點最多有m個分支（子樹）；而最少分支數要看是否為根結點，如果是根結點且不是葉子結點，則至少要有兩個分支，非根非葉結點至少有ceil(m/2)個分支，這裡ceil代表向上取整。
2）如果一個結點有n-1個關鍵字，那麼該結點有n個分支。這n-1個關鍵字按照遞增順序排列。
3）每個節點的結構為
節點個數：n；
關鍵字數組： k[n]，這n個關鍵字按照遞增順序排列
孩子指針數組：p[n + 1], p0<=k1, 之後所有 ki < pi <= ki+1;
查找操作
1）先讓key與根結點中的關鍵字比較，如果key等于k[i]（k[]為結點内的關鍵字數組），則查找成功
2）若key<k[1]，則到p[0]所訓示的子樹中進行繼續查找（p[]為結點内的指針數組），這裡要注意B-樹中每個結點的内部結構。
3）若key>k[n]，則道p[n]所訓示的子樹中繼續查找。
4）若k[i]<key<k[i+1]，則沿着指針p[I]所訓示的子樹繼續查找。
5）如果最後遇到空指針，則證明查找不成功。
如果查找22，過程為22小于30，往p0指針走，到達15,26這個内節點，然後對比發現屬于15到26區間，往p[1]走，找到22；
插入操作
要确定一下每個結點中關鍵字個數的範圍，如果B-樹的階數為m，則結點中關鍵字個數的範圍為ceil(m/2)-1 ~ m-1個。
對于關鍵字的插入，需要找到插入位置。在B-樹的查找過程中，當遇到空指針時，則證明查找不成功，同時也找到了插入位置，即根據空指針可以确定在最底層非葉結點中的插入位置，為了友善，我們稱最底層的非葉結點為終端結點，由此可見，B-樹結點的插入總是落在終端結點上。在插入過程中有可能破壞B-樹的特征，如新關鍵字的插入使得結點中關鍵字的個數超過規定個數，中間結點為m/2向上取整的位置，這是要進行按中間結點的拆分，将中間結點放到父節點，如果父節點也不滿足要求，就一直到網上分裂
按照關鍵字序列來，{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}
建立5階b數，每個節點的關鍵字範圍2-4
①根節點最多容納4個關鍵字，插入1,2,6,7，的b樹如圖所示
②插入11時，超過4，此時需要分裂5/2向上取整，中間結點上移
以此類推
删除操作
對于B-樹關鍵字的删除，需要找到待删除的關鍵字，在結點中删除關鍵字的過程也有可能破壞B-樹的特性，如舊關鍵字的删除可能使得結點中關鍵字的個數少于規定個數，這是可能需要向其兄弟結點借關鍵字或者和其孩子結點進行關鍵字的交換，也可能需要進行結點的合并。
①删除8,16，删除終端節點隻需要判斷删除後關鍵字的個數有沒有小于最小值即2，沒有直接删除，删除16的話，由于不是中端結點，取孩子來交換，隻能找小于16的最大的或者大于16最小的，這裡如果取15，會導緻15所在結點的個數小于2，更麻煩，是以取17替換。
②删除4
将其與根節點合并，高度－1
三、B+樹
1）在B+樹中，具有n個關鍵字的結點有n個分支，而在B-樹中，具有n個關鍵字的結點含有n+1個關鍵字。
2）在B+樹中，每個結點（除根結點外）中的關鍵字個數n的取值為ceil(m/2) <= n <=m,根結點的取值範圍為1<=n<=m，b樹他們的取值範圍分别是ceil(m/2) -1<= n <=m-1和1<=n<=m-1。
3）在B+樹中葉子結點包含資訊，并且包含了全部關鍵字，葉子結點引出的指針指向記錄。
4）在B+樹中的所有非葉子結點僅起到一個索引的作用，即結點中的每個索引項隻含有對應子樹的最大關鍵字和指向該子樹的指針。
每個父節點都出現在子節點中，是子節點的最大或最小元素。例如根節點的元素8，是子節點2,5,8的最大元素，也是葉子節點6,8的最大元素。根節點15是整個b+數的最大元素，無論插入删除多少元素，始終要保持最大在根節點中；父親元素都會包含在葉子節點中，所有葉子節點包含了全部元素資訊，并且每個葉子節點都帶有指向下一個節點的指針，形成連結清單這裡其實是雙向連結清單，圖中沒表現出來。
衛星資料：指的是索引元素所指向的資料記錄，比如資料庫中的某一行。
B樹中無論是中間結點還是葉子節點，都有衛星資料
而b+樹中，隻有葉子節點帶有衛星資料，其餘中間結點僅僅是索引。
如果需要單獨查找元素3，那麼先8,15節點，2,5,8節點，3,5節點，看起來與b樹沒有差別，實際上有兩點：b+樹沒有衛星資料，同樣大小磁盤頁，可以容納更多的元素，這樣B+樹會比b樹矮胖，另外，b+樹隻有在葉子節點有衛星資料，是以必須查找到葉子節點，而b樹隻要找到就可以傳回。
範圍查找:3-11
這種查找樹，隻要中序周遊，就是有序的
B樹範圍查找3-11
9->(2,6)->(3,5)查找到3之後進行中序周遊，
(3,5)->(2,6)->(8)->9->11
B+樹的查找範圍3-11
9->(2,6)->(3,5)查找到3之後進行連結清單周遊，(3,5)->(6,8)->(9,11)
是以b+樹的優勢在于；
1.單一節點存儲更多的元素，使得查詢的IO次數更少。
2.所有查詢都要查找到葉子節點，查詢性能穩定。
3.所有葉子節點形成有序連結清單，便于範圍查詢。
原文：https://blog.csdn.net/huangwei18351/article/details/82528523