一镐牺，b樹

b樹（balance tree）和b+樹應(yīng)用在數(shù)據(jù)庫(kù)索引蜓斧，可以認(rèn)為是m叉的多路平衡查找樹盲镶，但是從理論上講侥袜，二叉樹查找速度和比較次數(shù)都是最小的，為什么不用二叉樹呢溉贿？

因?yàn)槲覀円紤]磁盤IO的影響枫吧，它相對(duì)于內(nèi)存來說是很慢的。數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤上的宇色，當(dāng)數(shù)據(jù)量大時(shí)九杂，就不能把整個(gè)索引全部加載到內(nèi)存了，只能逐一加載每一個(gè)磁盤頁(yè)（對(duì)應(yīng)索引樹的節(jié)點(diǎn)）宣蠕。所以我們要減少IO次數(shù)例隆，對(duì)于樹來說，IO次數(shù)就是樹的高度抢蚀，而“矮胖”就是b樹的特征之一镀层，它的每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子，m稱為b樹的階皿曲，m的大小取決于磁盤頁(yè)的大小唱逢。

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

定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子，且M>2屋休；

根結(jié)點(diǎn)的兒子數(shù)為[2, M]坞古；

除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]，向上取整劫樟；

非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=兒子數(shù)-1痪枫；

所有葉子結(jié)點(diǎn)位于同一層；

k個(gè)關(guān)鍵字把節(jié)點(diǎn)拆成k+1段毅哗，分別指向k+1個(gè)兒子听怕，同時(shí)滿足查找樹的大小關(guān)系。

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

關(guān)鍵字集合分布在整顆樹中尿瞭；

任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；

搜索有可能在非葉子結(jié)點(diǎn)結(jié)束翅睛；

其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找声搁；

█如圖是一個(gè)3階b樹，順便講一下查詢?cè)?的過程：

1捕发，第一次磁盤IO疏旨，把9所在節(jié)點(diǎn)讀到內(nèi)存，把目標(biāo)數(shù)5和9比較扎酷，小檐涝，找小于9對(duì)應(yīng)的節(jié)點(diǎn)；

2，第二次磁盤IO谁榜，還是讀節(jié)點(diǎn)到內(nèi)存幅聘，在內(nèi)存中把5依次和2、6比較窃植，定位到2帝蒿、6中間區(qū)域?qū)?yīng)的節(jié)點(diǎn)；

3巷怜，第三次磁盤IO就不上圖了葛超，跟第二步一樣，然后就找到了目標(biāo)5延塑。

可以看到绣张，b樹在查詢時(shí)的比較次數(shù)并不比二叉樹少，尤其是節(jié)點(diǎn)中的數(shù)非常多時(shí)页畦，但是內(nèi)存的比較速度非撑痔妫快，耗時(shí)可以忽略豫缨，所以只要樹的高度低独令，IO少，就可以提高查詢性能好芭，這是b樹的優(yōu)勢(shì)之一燃箭。

█b樹的插入刪除元素操作：

比如我們要在下圖中插入元素4：

1，首先自頂向下查詢找到4應(yīng)該在的位置舍败，即3招狸、5之間；

2邻薯，但是3階b樹的節(jié)點(diǎn)最多只能有2個(gè)元素裙戏，所以把3、4厕诡、5里面的中間元素4上移（中間元素上移是插入操作的關(guān)鍵）累榜；

3，上一層節(jié)點(diǎn)加入4之后也超載了灵嫌，繼續(xù)中間元素上移的操作壹罚，現(xiàn)在根節(jié)點(diǎn)變成了4、9寿羞；

4猖凛，還要滿足查找樹的性質(zhì)，所以對(duì)元素進(jìn)行調(diào)整以滿足大小關(guān)系绪穆，始終維持多路平衡也是b樹的優(yōu)勢(shì)辨泳，最后變成這樣：

再比如我們要?jiǎng)h除元素11：

1虱岂，自頂向下查詢到11，刪掉它漠吻；

2量瓜，然后不滿足b樹的條件了，因?yàn)樵?2所在的節(jié)點(diǎn)只有一個(gè)孩子了途乃，所以我們要“左旋”，元素12下來扔傅，元素13上去：

這時(shí)如果再刪除15呢耍共？很簡(jiǎn)單，當(dāng)元素個(gè)數(shù)太少以至于不能再旋轉(zhuǎn)時(shí)猎塞，12直接上去就行了试读。

二，b+樹

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

1铝量、有n棵子樹的非葉子結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字（b樹是n-1個(gè)）倘屹，這些關(guān)鍵字不保存數(shù)據(jù)，只用來索引慢叨，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)（b樹是每個(gè)關(guān)鍵字都保存數(shù)據(jù)）纽匙。

2、所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息拍谐，及指向含這些關(guān)鍵字記錄的指針烛缔，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。

3轩拨、所有的非葉子結(jié)點(diǎn)可以看成是索引部分践瓷，結(jié)點(diǎn)中僅含其子樹中的最大（或最小）關(guān)鍵字亡蓉。

4晕翠、通常在b+樹上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)寸宵，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)崖面。

5、同一個(gè)數(shù)字會(huì)在不同節(jié)點(diǎn)中重復(fù)出現(xiàn)梯影，根節(jié)點(diǎn)的最大元素就是b+樹的最大元素巫员。

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

1、b+樹的中間節(jié)點(diǎn)不保存數(shù)據(jù)甲棍，所以磁盤頁(yè)能容納更多節(jié)點(diǎn)元素简识，更“矮胖”；

2、b+樹查詢必須查找到葉子節(jié)點(diǎn)七扰，b樹只要匹配到即可不用管元素位置奢赂，因此b+樹查找更穩(wěn)定（并不慢）；

3颈走、對(duì)于范圍查找來說膳灶，b+樹只需遍歷葉子節(jié)點(diǎn)鏈表即可，b樹卻需要重復(fù)地中序遍歷立由，如下兩圖：

原文參考：

---------------------

作者：login_sonata

來源：CSDN

原文：https://blog.csdn.net/login_sonata/article/details/75268075