B-樹，B-樹是一種非二叉的查找樹。它除了要滿足查找樹的特性，還要滿足以下結(jié)構(gòu)特性：
一棵M階的B-樹，（1） 樹的根或者是一片葉子（一個節(jié)點(diǎn)的樹），或者其兒子數(shù)在2和M之間。（2） 除根外，所有的非葉子節(jié)點(diǎn)的孩子數(shù)在M/2和M之間。（3），所有的葉子節(jié)點(diǎn)都在相同的深度。
要注意的是，B-樹中，所有的數(shù)據(jù)都存放在葉子節(jié)點(diǎn)。而在葉子節(jié)點(diǎn)上存放的數(shù)據(jù)量是有限的。
B－樹的插入與刪除，唯一要考慮的問題是，讓插入或刪除以后的樹，依然滿足B－樹的特性。在某些情況下，這也是一個比較復(fù)雜的過程。說不清楚，看書中的例子。書中的方法其實(shí)也都是定式。因為計算機(jī)本身不會思考。所以當(dāng)我們思考計算機(jī)要做的工作時，我們要學(xué)會像計算機(jī)一樣機(jī)械的考慮問題。說白了就是if。。。then。。。else。
B－樹的平均深度為logm/2N。執(zhí)行查找的平均時間為O(logM)。
B－樹應(yīng)用在數(shù)據(jù)庫系統(tǒng)中。具體指的是應(yīng)該是索引。它加快了訪問數(shù)據(jù)的速度。
書中提到這一種流行的定義B－樹的方法。還有一種定義的方法是允許把數(shù)據(jù)存放在內(nèi)部節(jié)點(diǎn)中。而沒有提到B＋樹。而我在google上找出的B＋樹的定義和以上對B－樹的定義很像：“A B－Tree in which keys are stored in the leaves. ”。這讓我很困惑。究竟那個是B＋樹哪個是B－樹。