B樹是為磁盤或其他輔助存儲設(shè)計的一種平衡搜索樹。

我理解B樹與紅黑樹等的主要區(qū)別是，紅黑樹假定對樹的操作都在內(nèi)存中，定義兩種操作：
1.關(guān)鍵字與結(jié)點的比較
2.在樹中沿樹的結(jié)構(gòu)爬升或下降
紅黑樹在內(nèi)存進行這兩種操作的時間在同一個數(shù)量級內(nèi)
而在磁盤等輔助存儲設(shè)備的狀況下，這兩種操作的時間相差多個數(shù)量級，爬升和下降操作耗時巨大，所以設(shè)計了B樹來增加操作1，減少操作2
B樹的主要特性就是分支因子很大，樹的高度很小，極大的減少了操作2

B樹的定義

B樹的嚴(yán)格定義有很多項，簡單的說，B樹是一顆分支因子很大的搜索樹，可以想象為 n 叉搜索樹（相對于二叉搜索樹）

可以證明，嚴(yán)格定義的B樹高度會很小，比二叉搜索樹小的多

B樹上的基本操作

基本操作包括搜索、創(chuàng)建、插入

搜索的過程較簡單，是一個從跟結(jié)點向下查找的過程，與二叉搜索樹類似，只是將與單個關(guān)鍵字的比較換為與多個關(guān)鍵字的比較。從某個結(jié)點的比較看，書中給出的方法是順序查找，如果 t 較大的話，二分查找會更有效率。

創(chuàng)建操作很簡單，只是創(chuàng)建一個空的跟結(jié)點。

插入操作不能簡單的插入新的葉結(jié)點，在遇到滿的結(jié)點時要將結(jié)點分裂為兩個結(jié)點，以保證插入新元素后仍然是合法的B樹。

從B樹中刪除關(guān)鍵字

從B樹中刪除關(guān)鍵字非常復(fù)雜，復(fù)雜到書里都不愿意給出代碼，只給了思路和分析。

B樹的刪除操作性能也很高，O(h) 次磁盤操作，O(th) 的 CPU 時間，同插入操作一樣高效。