轉(zhuǎn)載自https://blog.csdn.net/login_sonata/article/details/75268075

一，b樹

b樹（balance tree）和b+樹應(yīng)用在數(shù)據(jù)庫索引，可以認為是m叉的多路平衡查找樹，但是從理論上講，二叉樹查找速度和比較次數(shù)都是最小的，為什么不用二叉樹呢？ 
因為我們要考慮磁盤IO的影響，它相對于內(nèi)存來說是很慢的。數(shù)據(jù)庫索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量大時，就不能把整個索引全部加載到內(nèi)存了，只能逐一加載每一個磁盤頁（對應(yīng)索引樹的節(jié)點）。所以我們要減少IO次數(shù)，對于樹來說，IO次數(shù)就是樹的高度，而“矮胖”就是b樹的特征之一，它的每個節(jié)點最多包含m個孩子，m稱為b樹的階，m的大小取決于磁盤頁的大小。

█一個M階的b樹具有如下幾個特征：

1. 定義任意非葉子結(jié)點最多只有M個兒子，且M>2；
2. 根結(jié)點的兒子數(shù)為[2, M]；
3. 除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]，向上取整；
4. 非葉子結(jié)點的關(guān)鍵字個數(shù)=兒子數(shù)-1；
5. 所有葉子結(jié)點位于同一層；
6. k個關(guān)鍵字把節(jié)點拆成k+1段，分別指向k+1個兒子，同時滿足查找樹的大小關(guān)系。

█有關(guān)b樹的一些特性，注意與后面的b+樹區(qū)分：

1. 關(guān)鍵字集合分布在整顆樹中；
2. 任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
3. 搜索有可能在非葉子結(jié)點結(jié)束；
4. 其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找；

█如圖是一個3階b樹，順便講一下查詢元素5的過程： 
 
1，第一次磁盤IO，把9所在節(jié)點讀到內(nèi)存，把目標(biāo)數(shù)5和9比較，小，找小于9對應(yīng)的節(jié)點；

 
2，第二次磁盤IO，還是讀節(jié)點到內(nèi)存，在內(nèi)存中把5依次和2、6比較，定位到2、6中間區(qū)域?qū)?yīng)的節(jié)點； 
3，第三次磁盤IO就不上圖了，跟第二步一樣，然后就找到了目標(biāo)5。

可以看到，b樹在查詢時的比較次數(shù)并不比二叉樹少，尤其是節(jié)點中的數(shù)非常多時，但是內(nèi)存的比較速度非?？欤臅r可以忽略，所以只要樹的高度低，IO少，就可以提高查詢性能，這是b樹的優(yōu)勢之一。

█b樹的插入刪除元素操作： 
比如我們要在下圖中插入元素4： 
 
1，首先自頂向下查詢找到4應(yīng)該在的位置，即3、5之間； 
2，但是3階b樹的節(jié)點最多只能有2個元素，所以把3、4、5里面的中間元素4上移（中間元素上移是插入操作的關(guān)鍵）； 
3，上一層節(jié)點加入4之后也超載了，繼續(xù)中間元素上移的操作，現(xiàn)在根節(jié)點變成了4、9； 
4，還要滿足查找樹的性質(zhì)，所以對元素進行調(diào)整以滿足大小關(guān)系，始終維持多路平衡也是b樹的優(yōu)勢，最后變成這樣： 
 
再比如我們要刪除元素11： 
1，自頂向下查詢到11，刪掉它； 
2，然后不滿足b樹的條件了，因為元素12所在的節(jié)點只有一個孩子了，所以我們要“左旋”，元素12下來，元素13上去： 
 
這時如果再刪除15呢？很簡單，當(dāng)元素個數(shù)太少以至于不能再旋轉(zhuǎn)時，12直接上去就行了。

二，b+樹

b+樹，是b樹的一種變體，查詢性能更好。m階的b+樹的特征：

1. 有n棵子樹的非葉子結(jié)點中含有n個關(guān)鍵字（b樹是n-1個），這些關(guān)鍵字不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點（b樹是每個關(guān)鍵字都保存數(shù)據(jù)）。
2. 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。
3. 所有的非葉子結(jié)點可以看成是索引部分，結(jié)點中僅含其子樹中的最大（或最?。╆P(guān)鍵字。
4. 通常在b+樹上有兩個頭指針，一個指向根結(jié)點，一個指向關(guān)鍵字最小的葉子結(jié)點。
5. 同一個數(shù)字會在不同節(jié)點中重復(fù)出現(xiàn)，根節(jié)點的最大元素就是b+樹的最大元素。

█b+樹相比于b樹的查詢優(yōu)勢：

1. b+樹的中間節(jié)點不保存數(shù)據(jù)，所以磁盤頁能容納更多節(jié)點元素，更“矮胖”；
2. b+樹查詢必須查找到葉子節(jié)點，b樹只要匹配到即可不用管元素位置，因此b+樹查找更穩(wěn)定（并不慢）；
3. 對于范圍查找來說，b+樹只需遍歷葉子節(jié)點鏈表即可，b樹卻需要重復(fù)地中序遍歷，如下兩圖：