開宗明義，B樹是為磁盤或其他直接存取輔助設備而設計的一種平衡查找樹。一般設計的簡單數據結構都是面向主存而設計的，主存讀取速度快但容量小；而磁盤讀取速度慢而容量大，于是針對磁盤而設計的數據結構就不同于為主存而設計的。就樹結構上來說，紅黑樹的二叉性質和高深度適合主存，而B樹正是應磁盤特點而設計的高級樹結構，其高度比紅黑樹小很多，但廣度要大很多，其分支不只2個，分支因子越大，高度越小。

在考察算法性能時，需要考慮兩方面：磁盤存取次數和CPU運行時間。主存存儲量小，一旦要處理的數據量比較龐大，就需要以頁在磁盤和主存之間交換，選擇頁復制到主存中操作再將修改過的頁寫回磁盤，這來回就是磁盤存取消耗的性能，因此交換頁在操作系統磁盤模塊是一個很重要的算法。

B樹設計上，一個結點的大小相當于一個完整的磁盤頁，其子女數就由磁盤頁的大小來決定。這樣一個節點的讀取就交換一個頁，減少磁盤IO次數。下面定義B樹：

一棵B樹T是具有如下性質的有根樹（根為root[T]）：

1）每個結點x有以下域構成：

?? a)n[x]，當前存儲在結點x中的關鍵字數；

?? b)n[x]個關鍵字本身，以非降序存放，key₁[x]=<key₂[x]=<…=<key_n[x][x]

?? c)leaf[x]，布爾值，如果x是葉子該值為true，如果x是內結點則為false；

2）每個內結點x還包含n[x]+1個指向其子女的指針c₁[x]，c₁[x]，…，c_n[x]+1[x]，葉結點沒有子女，故而c_i域沒有定義；

3）各關鍵字key_i[x]對儲存在各子樹中的關鍵字范圍加以分割，如果k_i為存儲在以c_i[x]為根的子樹中的關鍵字，那么：

k₁=<key₁[x]=< k₂=< key₂[x]=<…=< k_n[x]=<key_n[x]+1[x]

子節點的值是被父結點的值區隔開。

4）每個葉結點具有相同深度，即樹的高度h；

5）每一個節點能包含的關鍵字數有一個上界和下界，界可用一個B樹的最小度數的固定整數t>=2來表示；

??? a)每個非根的結點必須至少有t-1個關鍵字，每個非根的內結點至少有t個子女，如果樹是非空的，則根節點至少包含一個關鍵字；

??? b)每個節點可包含至多2t-1個關鍵字，故一個內結點至多可有2t個子女，如果一個結點是滿的，那就有2t-1個關鍵字。

如果t=2，就是每個非根結點的關鍵字數為2，其每個內結點有2個、3個或4個子女，是一顆2-3-4樹。t其實就是限制了每個結點的關鍵字數，在t-1和2t-1范圍內，取閉區間。

B樹設計上一般考慮一個結點大小和一個磁盤頁相當，因此磁盤存取次數和B樹高度成正比。通過B樹最壞情況的高度來衡量性能。如果n>=1，對任意一顆包含n個關鍵字、高度為h、最小度數t>=2的B樹T，則：

定義了B樹和分析其性能，下面對B樹的基本操作進行描述。

B樹的基本操作和二叉樹類似，不同的是每個結點不只是二叉決定，而是根據B樹的度（結點關鍵字數）做決定。B樹的每個內結點x，都需要做n[x]+1路的分支決定。

1）B樹的搜索操作

從根結點出發搜索關鍵字k，在算法上只需依次從頂層定位關鍵字值序的空間就可以。關注下，B樹搜索操作的復雜度：搜索是從樹根一直下降的過程，需存取的磁盤頁面數為樹的高度就是：O(h)=O(log_tn)，t是節點的度，n是關鍵字數，h是樹高度；對于CPU運行時間消耗來說，每個節點的循環式為O(t)，總共進行h次循環，那總的時間就是O(th)=O(tlog_tn)。

2）B樹的插入操作

B樹插入操作比較復雜，必須對滿結點進行分裂操作，以維持B樹結點至多2t-1個關鍵字的性質。從根節點出發，尋找待插入關鍵字的序值位置，如果結點滿，則分裂，將中間值插入到父節點，如果父節點也因此滿，需要進一步分裂，遞歸如是。文中有一個思路很好，就是在尋找關鍵字要插入的結點過程中，在查找沿途過程中發現有滿節點（包含葉結點本身）就分類，而不是等最后插入時發現了才分裂。看看滿節點分裂算法的描述：

Fun_Btree_split_child(x,i,y){//x是父結點，y是子節點，i是x的分裂點

??? Allocat_node(z);//分配一個z結點

??? Leaf[z]=leaf[y];//把y中t個最大關鍵字（包含其t+1個子女）復制給z

??? n[z]=t-1;

??? for j=1 to t-1

??????? do key_j[z]=key_j+t[y];

??? if not leaf[y] //y有子女

??????? then for j=1 to t

??????????? do c_j[z]=c_j+t[y]

??? n[y]=t-1;

//到此已經將y節點，從中間分類成兩個節點，y和z，其中z是較大關鍵字的那部分

//下面就是將y的中間關鍵字提升到父結點x中，左右分別指向y和z

for j=n[x]+1downto i+1

??????? do c_j+1[x]=c_j[x];//x的子女向右移動一個位置

??? c_i+1[x]=z;

??? for j=n[x] downto i

??????? do key_j+1[x]=key_j[x];//x的關鍵字向右移動一個位置

??? key_i[x]=key_t[y]

??? n[x]=n[x+1]

??? Disk-Write(y);

??? Disk-Write(z);

Disk-Write(x);//回寫磁盤，一個結點一頁

}

有了分裂函數，插入算法就不描述了，在遇到滿結點時調用分裂函數即可。對高度為h的B樹，插入的磁盤存取次數是O(h)，cpu運行時間是O(th)=O(tlog_tn)。

3）B數的刪除操作

B樹刪除操作和插入一樣麻煩，需要確保刪除后結點數不小于t-1個關鍵字的性質。刪除的算法思路就是合并節點，復雜度和插入一樣。這里不具體描述。

B樹的應用是很廣泛的，對于算法復雜度來說，關注CPU時間是不夠的，因為多數情況，需要整體考慮設備性能，而磁盤IO能力是一個很關鍵但常常是制約性能的指標。 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的算法导论之B树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。