1,根節點至少有兩個子節點;
2.每個非根節點包含的關鍵詞個數j滿足:┌m/2┐-1≤?j≤?m-1;
3.除了根節點(不包括葉節點)以外的所有節點的度正好是關鍵字總數加上1,所以內部子樹的個數k滿足:┌m/2┐≤k≤m;
4.所有葉節點都位於同壹級別。
擴展數據
在B樹中查找給定關鍵字的方法是:首先取根節點,在根節點包含的關鍵字K1,…,Kn中查找給定關鍵字(使用順序搜索或二分搜索法法)。如果找到等於給定值的關鍵字,則搜索成功。
否則可以確定要搜索的關鍵字在Ki和Ki+1之間,Pi是指向子樹根節點的指針。此時取指針Pi指向的節點繼續搜索,直到找到為止,否則指針Pi為空時搜索失敗。
B+樹是B樹的變種,比B樹應用更廣泛。m階B+樹具有以下特征:
1.每個節點中關鍵字的數量等於子節點的數量。所有非最低內層節點的關鍵詞都是對應子樹中最大的關鍵詞,最低內層節點包含所有關鍵詞。
2.除了根節點,每個內部節點都有m/2到m個子節點。?
3.所有的葉節點都在樹結構的同壹層,它們不包含任何信息(它們可以被視為外部節點或未能找到的節點),因此樹結構在高度上總是平衡的。
百度百科-B+樹
百度百科-B樹