B+樹(shù)和B樹(shù)相比的主要區(qū)別：1，就是B+樹(shù)所有關(guān)鍵碼都在葉子節(jié)點(diǎn);2，B+樹(shù)的葉子節(jié)點(diǎn)是帶有指針的，且葉節(jié)點(diǎn)本身按關(guān)鍵碼從小到大順序連接;3，在搜索過(guò)程中，如果查詢(xún)和內(nèi)部節(jié)點(diǎn)的關(guān)鍵字一致，那么搜索過(guò)程不停止，而是繼續(xù)向下搜索這個(gè)分支。

B樹(shù)就是B-樹(shù)嗎

B樹(shù)就是B-樹(shù)，等價(jià)的，一般都說(shuō)是B樹(shù)，B+樹(shù)是B樹(shù)的一種變形，B+樹(shù)和B樹(shù)他們之間有區(qū)別。

通常表示B-樹(shù)B*-樹(shù)B+-樹(shù)中的“-”是英文中的連詞符號(hào)，沒(méi)有實(shí)在的意義。所以B樹(shù)就是B-樹(shù)。

B樹(shù)的基本概念

B-樹(shù)中所有結(jié)點(diǎn)中孩子結(jié)點(diǎn)個(gè)數(shù)的最大值成為B-樹(shù)的階，通常用m表示，從查找效率考慮，一般要求m>=3。一棵m階B-樹(shù)或者是一棵空樹(shù)，或者是滿(mǎn)足以下條件的m叉樹(shù)。

1)每個(gè)結(jié)點(diǎn)最多有m個(gè)分支(子樹(shù));而最少分支數(shù)要看是否為根結(jié)點(diǎn)，如果是根結(jié)點(diǎn)且不是葉子結(jié)點(diǎn)，則至少要有兩個(gè)分支，非根非葉結(jié)點(diǎn)至少有ceil(m/2)個(gè)分支，這里ceil代表向上取整。

2)如果一個(gè)結(jié)點(diǎn)有n-1個(gè)關(guān)鍵字，那么該結(jié)點(diǎn)有n個(gè)分支。這n-1個(gè)關(guān)鍵字按照遞增順序排列。

3)每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：

其中，n為該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù);ki為該結(jié)點(diǎn)的關(guān)鍵字且滿(mǎn)足ki<ki+1;pi為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針且滿(mǎn)足pi所指結(jié)點(diǎn)上的關(guān)鍵字大于ki且小于ki+1，p0所指結(jié)點(diǎn)上的關(guān)鍵字小于k1，pn所指結(jié)點(diǎn)上的關(guān)鍵字大于kn。< p="">

4)結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且按從小到大排列。

5)葉子結(jié)點(diǎn)處于同一層;可以用空指針表示，是查找失敗到達(dá)的位置。

注：平衡m叉查找樹(shù)是指每個(gè)關(guān)鍵字的左側(cè)子樹(shù)與右側(cè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1的查找樹(shù)，其結(jié)點(diǎn)結(jié)構(gòu)與上面提到的B-樹(shù)結(jié)點(diǎn)結(jié)構(gòu)相同，由此可見(jiàn)，B-樹(shù)是平衡m叉查找樹(shù)，但限制更強(qiáng)，要求所有葉結(jié)點(diǎn)都在同一層。