??這一小節將介紹B樹和B+樹的內容，
一：B樹
1.介紹
??B樹又稱多路平衡查找樹，所有結點的平衡因子均等于0，所有孩子結點的最大值成為B樹的階，用m表示，一顆m階B樹或為空樹，或者滿足：
??(1)樹中每個結點至多有m棵子樹，至多有m-1個關鍵字，
??(2)若根結點不是終端結點，則至少有兩棵子樹，
??(3)除根結點外的所有非葉結點至少有m/2棵子樹(取整數最大值)至少有m/2-1個關鍵字(取整數最大值).
??(4)所有葉結點不帶資訊，實際上這些結點并不存在，指向這些結點的指標為空，
2.B樹的結構
??B樹的結構舉例如下：
3.B樹的性質
??(1)結點的孩子個數=改結點的關鍵字個數+1，
??(2)如果根節點有關鍵字，則其子樹不然大于等于兩棵，
??(3)除根結點外所有非葉結點至少有m/2(取整數最大值)子樹，至少有m/2-1(取整數最大值)關鍵字；至多有m棵子樹，至多有m-1個關鍵字， 這里m/2等同于Math.ceil(m/2)，即取上線的整數值，
??(4)結點的下層結點關鍵字落在上層結點關鍵字所劃分的區間內，
??(5)所有葉結點均在最后一層，代表查找失敗的位置，
4.B樹的高度
??要明確的是B樹的高度不包括最后的不帶任何資訊的葉結點所處的那一層，
??對于任意一顆包括n個關鍵字，高度為h，階數為m的B樹：
??(1)因為B樹中每個結點最多有m棵子樹，m-1個關鍵字，所以在一顆高度為h的m階B樹中關鍵字的個數滿足n <= (m-1)(1+m+m^2+...+m^(h-1))，
??(2)若讓每個結點的關鍵字個數達到最小，則容納同樣多關鍵字的B樹的高度達到最大，由B樹的定義，第一層至少有1個結點，第二層至少有2個結點，除根結點外的每個非終端結點至少有m/2(取最大值)棵子樹，則第h+層至少有2*(m/2)^(h-1)個結點，
對于關鍵字個數為n的B樹，查找不成功的結點個數為n+，因此有n+1>=2(m/2)^(h-1)，
??綜上計算出B樹的高度范圍為：
?? logm(n+1)<= h <=log(ceil(m/2)) (n+1)/2 + 1
5.B樹的查找
??在B樹上進行查找與二叉查找樹很相似，只是不同的是每個結點都是多個關鍵字的有序表，在每個結點上都有多個子樹的多路分支，
??B樹的查找包含兩個基本操作：在B樹上找結點；在結點內找關鍵字，前一個操作是在磁盤上進行的，后一個操作是在記憶體中進行的，
??查找時現在有序表中進行查找，查找不成功時到所指的子樹中去查找，查找到葉結點時(對應指標為空指標)，則說明樹中沒有對應的關鍵字，查找失敗，
6.B樹的插入
??B樹的插入比二叉查找樹復雜，在二叉查找樹中，僅需查找到需要插入的終端結點的位置，但是，在B樹中找到插入位置的時候，直接插入可能會導致整個樹不再滿足B樹定義的要求，將關鍵字key插入B樹的程序如下：
??定位：先利用B樹查找演算法，找到插入該關鍵字的最低層的某個非葉結點，插入位置一定是最低層中的某個非葉結點，
??插入：如果插入后的結點關鍵字個數少于m個，可以直接插入，當插入后的結點關鍵字個數大于m-1，即大于子樹個數+1的話，就不符合規定了，必須對結點進行分裂，
??分裂的方法是：取一個新結點，在插入關鍵字的原結點，以結點中間的key為中心分裂成左右兩部分，然后將這個中間的key插入到父結點中，這個key的左子樹指向分裂后的左半部分，這個key的右子支指向分裂后的右半部分，然后將當前結點指向父結點，若此時導致其父結點的關鍵字個數也超過了上線，則繼續，
7.B樹的洗掉
??B樹的洗掉操作要復雜一些，要使得洗掉后的關鍵字個數大于等于(m/2)-1，這里(m/2)-1等同于Math.ceil(m/2)-1，需要進行合并，
??因為B樹的洗掉操作和插入操作比較復雜，下一篇講具體來講B樹的插入和洗掉和他們演算法實作的細節，
二：B+樹
??B+樹是針對資料庫需求而出現的一種B樹的變形樹，
??B+樹最重要的特點是 關鍵字個數和孩子結點個數相同，如果關鍵字個數比孩子結點個數小1，就會變成一棵B樹，
??B+樹還滿足下列條件：
??(1)每個分支結點最多有m棵子樹，
??(2)非葉根節點至少有兩棵子樹，其他分支結點至少有Math.ceil(m/2)-1棵子樹(和B樹一樣)，
?? (3)所有葉結點包含全部的關鍵字及指向相應記錄的指標，并將關鍵字按大小順序排列，相鄰葉結點按大小順序鏈接起來，非葉結點的關鍵字也會出現在葉結點中，
??(4)所有分支中僅包含它的各個子結點中關鍵字的最大值及指向其子結點的指標，
??(5)B+樹子樹和關鍵字大小范圍都和B樹子樹范圍一樣，為[Math.ceil(m/2)-1,Math.ceil(m/2)]，
?? B+樹與B樹最大的不同是非葉結點不保存資料，只用于索引，不含有關鍵字對應記錄的存盤地址，所有資料（或者說記錄）都保存在葉子結點中 ，
?? 指向B樹的指標有兩個，一個指向根結點，另一個指向關鍵字最小的葉結點，因此對B樹有兩種查找運算，一種是從關鍵字開始的順序查找，另一種是從根結點開始的多路查找，當找到非葉節點的關鍵字等于給定值時并不終止，繼續向下查找，直到找到葉結點上的該關鍵字為止，
??所以無論查找成功與否，每次查找都是一條從根結點到葉結點的路徑，
??B+樹的結構例子如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145112.html
標籤：其他