二叉搜索樹不適合應用到磁盤上，因為它的扇出數(shù)較低并且平衡時需要大量的節(jié)點重定位和指針更新。B樹通過增加每個節(jié)點存儲項的數(shù)量(高扇出)和減少頻繁的平衡操作來解決這些問題。下面我們將討論了B樹的內部結構，B樹的查找、插入和刪除操作算法概要，以及用于保持B樹平衡的拆分和合并操作。

B樹實際上是平衡二叉樹的擴展，不同之處在于B樹具有更大的扇出數(shù)(即更多的子節(jié)點)和更低的樹高。前文討論二叉樹時節(jié)點以圓形表示，而B樹節(jié)點通常以矩形表示，當然二叉樹也可以使用矩形來表示。圖2-7使用矩形的方式表示二叉樹，2-3樹和B樹，從中我們可以看出它們之間的相似性和差異性。

圖2-7

B樹的節(jié)點也是有序排列的，因此B樹可以像二叉搜索樹一樣進行節(jié)點查找。這也就是說B樹查找節(jié)點的時間復雜度是對數(shù)的，通過32次比較就能從包含40億個節(jié)點的B樹中找到某個鍵。

對于磁盤數(shù)據(jù)結構，如果每次比較都要經過磁盤扇區(qū)定位，這樣的性能顯然是不能接受的。但是每個B樹節(jié)點存儲幾十甚至上百個條目，這就避免了每次比較都需要定位新的磁盤扇區(qū)，僅僅在進入B樹下一層的時候才需要重定位加載新扇區(qū)。后面我們會更加詳細的討論查詢算法的細節(jié)。

B樹上可以非常高效的查詢單個數(shù)據(jù)或者是查詢某個范圍內的數(shù)據(jù)。在查詢語言里(如SQL)，查詢某個數(shù)據(jù)通常表示為等于(=)，而查詢某個范圍數(shù)據(jù)通常表示為比較(, ≤和≥)。

B樹的層次結構

B樹由多個節(jié)點構成，每個節(jié)點又包含N個鍵和N+1個指向子節(jié)點的指針。從邏輯上節(jié)點可以分成3類：

根節(jié)點(Root Node)： 根節(jié)點沒有父節(jié)點，位于樹的最頂部；

葉子節(jié)點(Leaf Nodes)： 樹的最底層節(jié)點，而且沒有任何子節(jié)點。

內部節(jié)點(Internal Nodes): 所有連接根節(jié)點和葉子節(jié)點的節(jié)點，通常樹包含多層內部節(jié)點。

圖2-9

由于B樹是一種磁盤頁面組織技術(即用于組織固定大小的頁面)，通常一個節(jié)點即是一個磁盤頁面，術語節(jié)點和頁面通常是同一概念。節(jié)點容量與它實際持有的鍵數(shù)之間的關系稱為占用率。

B樹的顯著特征是高扇出數(shù)(每個節(jié)點有較多的子節(jié)點)。高扇出數(shù)減少了為維持樹平衡而需要做的結構改動，也可以減少查詢時磁盤扇區(qū)定位的時間。B樹只有在節(jié)點空或滿的情況下才觸發(fā)平衡操作(即分裂和合并)。

分隔鍵(Separator Keys)

B樹節(jié)點上半部分存儲的鍵稱為分隔鍵。它們把樹劃分成子樹，每個子樹包含相應范圍內鍵的節(jié)點。分隔鍵以有序的方式保存在節(jié)點內，因此節(jié)點內能通過二分法進行鍵查找；找到鍵對應區(qū)間后，沿著對應的指針指向的子樹進入B樹的下一層。

B樹節(jié)點的下半部分保存了指向子樹的指針，第一個指針指向保存了所有小于第一個分隔鍵的子樹，最后一個指針指向了保存所有大于或等于最后一個分隔鍵的子樹，其它中間指針指向包含了所有大于等于其左側分隔鍵同時小于右側分隔鍵節(jié)點的子樹。 如圖2-10。

圖2-10

B樹的查復雜度

B樹查詢的復雜性需要從兩個方面考慮：磁盤頁傳輸?shù)臄?shù)量和查找時進行鍵比較的數(shù)量。

在磁盤頁傳輸數(shù)量方面，每個節(jié)點的分隔鍵劃分當前搜索空間為原來的1/N。因此在從根節(jié)點到葉子節(jié)點的遍歷過程中，需要讀取磁盤頁的數(shù)量為B樹的層數(shù)，即B樹的高度。

在鍵比較次數(shù)方面，每個節(jié)點中以二分法進行搜索，每一次比較都將當前搜索空間減半，因此復雜度為log?M (M為節(jié)點的數(shù)目)。

B樹的查詢

為了從B樹上查詢某個鍵，我們需要從根節(jié)點到葉子節(jié)點遍歷B樹。首先在根節(jié)點保存的分隔鍵上執(zhí)行二分查找，找到第一個大于查詢鍵的分隔鍵，找到該分隔鍵對應的子樹；在子樹上重復二分查詢操作，直到到達目標葉子節(jié)點。這時我們要么找到了需要查詢的鍵，或者查詢的鍵不存在。

查詢時我們從最粗粒度的層次(樹根)開始查找，然后進入到粒度更細的下一層，其中每層分隔鍵表示更精確、更詳細的范圍。重復這個過程，直到最后到達葉節(jié)點，即數(shù)據(jù)記錄所在的位置。

單鍵查詢時，在找到查詢鍵時或確定沒有查詢鍵后搜索即告結束；而在范圍查詢時，在找到最接近范圍開始的鍵值對后繼續(xù)沿著它的兄弟節(jié)點查詢，直到到達查詢范圍的末尾。

B樹節(jié)點的拆分

當插入記錄到B樹時，首先需要找到插入目標位置，使用前一節(jié)中描述的查找算法即可找到目標位置；鍵值被附加到找到的葉子節(jié)點后面，鍵被添加到對應節(jié)點分隔鍵列表的適當位置。如果是B樹鍵值的更新，使用查找算法找到目標葉節(jié)點，并將新值與現(xiàn)有鍵關聯(lián)即可。

如果目標位置沒有足夠的空間存儲新鍵值，為了存儲更多鍵值我們必須要拆分該節(jié)點成兩個節(jié)點。拆分節(jié)點可能有下面兩種情況：

• 分隔葉子節(jié)點：如果葉子節(jié)點最多能夠保存N個鍵值對，新插入鍵值對前該葉子節(jié)點就已經保存有N個鍵值對；
• 分隔非葉子節(jié)點：如果節(jié)點可以保存N+1個指向子樹的指針，新插入一個子樹指針前該節(jié)點就已經保存了N+1個指針；

拆分節(jié)點時，通常我們需要創(chuàng)建一個新的節(jié)點，然后從被拆分節(jié)點上轉移一半的元素到新創(chuàng)建的節(jié)點上；添加新創(chuàng)建節(jié)點的第一個分隔鍵和指針都其父節(jié)點對應的位置上(通常稱這個鍵被晉級)。新創(chuàng)建的節(jié)點和原來的節(jié)點稱為兄弟節(jié)點。

拆分節(jié)點的父節(jié)點也有可能沒有更多的空間保存被晉級的鍵和新建節(jié)點的指針，這時其父節(jié)點也需要拆分。這樣的拆分操作有可能需要一直傳遞到根節(jié)點。當根節(jié)點也達到它的容量上限時，根節(jié)點也必須進行拆分。

這種情況下，首先會新創(chuàng)建一個新的根節(jié)點，其中保存了用于拆分舊根節(jié)點的鍵；其次為舊的根節(jié)點創(chuàng)建一個兄弟節(jié)點，以拆分鍵平分舊根節(jié)點的元素，并轉移到新創(chuàng)建的兄弟節(jié)點上；最后，添加舊根節(jié)點和其兄弟節(jié)點的指針到新根節(jié)點的子樹指針列表中。這個過程中，舊的根節(jié)點和新為其創(chuàng)建的兄弟節(jié)點一起被降級到第二層，樹的高度也增加了1。當根節(jié)點被拆分或兩個節(jié)點合并為新的根節(jié)點時，樹的高度會發(fā)生變，而在葉子和內部節(jié)點層，B樹只會水平擴展。

圖2-11展示了將一個新元素11加入到一個已經完全占用的葉節(jié)點的過程。其中一半的元素留在老的節(jié)點，另一半元素被轉移到新創(chuàng)建的節(jié)點上。而拆分點的鍵(13)被作為分隔鍵保存到父節(jié)點對應的位置。

圖2-11

圖2-12展示了插入元素11前非葉子節(jié)點被完全占用的情況。首先一個新的節(jié)點被創(chuàng)建, 待分割節(jié)點中從N/2+1開始的元素被移入新創(chuàng)建的節(jié)點；其次拆分鍵被晉級到其父節(jié)點；最后新建的節(jié)點的指針被加入到其父節(jié)點的適當位置。

圖2-12

因為非葉節(jié)點拆分總是從下往上的，所以父節(jié)點需要一個額外的指針位置(指向下一層新創(chuàng)建的節(jié)點)。如果父節(jié)點沒有足夠的空間，那么它也必須被拆分。

拆分完成后，原來的一個節(jié)點變成兩個節(jié)點，我們必須選擇正確的節(jié)點來完成插入操作。如果插入的鍵小于新晉升的分隔鍵，則插入新元素到被拆分節(jié)點；否則，插入新元素到新創(chuàng)建的節(jié)點。

總而言之，節(jié)點拆分大致分為四步:

創(chuàng)建一個新的節(jié)點；

從待分割節(jié)點上轉移一半元素到新創(chuàng)建的節(jié)點上；

把新元素插入到相應的節(jié)點上；

把新分隔鍵和新建節(jié)點的指針加入到被拆分節(jié)點的父節(jié)點中；

B樹節(jié)點的合并

在進行刪除操作時，首先找到目標葉子節(jié)點，然后刪除鍵和與之關聯(lián)的值。刪除后，如果該葉子節(jié)點和它相鄰兄弟節(jié)點保存的鍵值對過少(低于某個閥值)，這時候就需要合并節(jié)點。

準確的說，如果以下條件成立，則需要合并兩個節(jié)點:

• 合并葉子節(jié)點：如果節(jié)點能夠保存N個鍵值對，相鄰兩個兄弟節(jié)點保存的鍵值對數(shù)量之和少于或等于N。
• 合并非葉子節(jié)點： 如果節(jié)點能夠保存N+1個子樹指針，相鄰兩個兄弟節(jié)點保存的指針數(shù)量之和少于或等于N+1。

圖2-13展示了刪除元素16后，B樹合并兩個葉子節(jié)點后結構的變化。通常，我們把右邊兄弟節(jié)點的元素移入左邊節(jié)點。但是也可以把左邊的元素移入右邊節(jié)點，只要保證鍵是有序的即可。

圖2-13

圖2-14展示了刪除元素10后，B樹合并兩個相鄰非葉子節(jié)點后結構的變化。我們合并兩個節(jié)點包含的元素到一個節(jié)點中，刪除另一個多余的節(jié)點。在合并非葉節(jié)點的過程中，我們還必須從父節(jié)點中轉移相應的分隔鍵到合并后子節(jié)點的適當位置(即分隔鍵的降級)。由于合并導致父節(jié)點的指針也減少了一個，由此有可能觸發(fā)父節(jié)點的合并操作。和節(jié)點拆分一樣，節(jié)點的合并也可能需要一直傳遞到根節(jié)點。

圖2-14

總而言之，節(jié)點合并大概也分為三步:

轉移所有右節(jié)點的元素到左邊節(jié)點；

從父節(jié)點中移除右節(jié)點的指針(如果是非葉節(jié)點則降級分隔符)；

移除右節(jié)點；

在B樹中，為了減少節(jié)點拆分和合并操作的數(shù)量，經常會使用一種稱為重新平衡的技術(Rebalancing)，我們會在后面的文章中再具體討論這個問題。

---

深入理解數(shù)據(jù)庫系統(tǒng)(儲存引擎概述1)

深入理解數(shù)據(jù)庫系統(tǒng)之存儲存引擎2(數(shù)據(jù)和索引)

深入理解數(shù)據(jù)庫系統(tǒng)之存儲存引擎(二叉搜索樹)

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的b树删除节点每次只能删一个吗_深入理解数据库系统之存储存引擎（B树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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