B-樹的詳解

文章目錄

• 一、B-樹的提出
• 二、B-樹的定義
• 三、B-樹的查找
• 四、B-樹的插入
• • 4.1 分裂
  • 4.2 再分裂
• 五、B-樹的删除
• • 5.1 旋轉
  • 5.2 合并
• 補充：B+樹

一、B-樹的提出

從嚴格意義上講，B-樹并不是二分查找樹。在實體上，B-樹的每一個結點都可能包含多個分支。然而，在邏輯上将，B-樹依然等效于傳統的二叉搜尋樹。B-樹的定義者，将其定義為一棵平衡的多路搜尋樹。

為什麼要提出B-樹呢？最初，B-樹的提出原因就是彌合不同存儲級别之間在通路速度上的巨大差異，也就是實作高效的I/O。

在現實生活中 系統存儲容量的增長速度 << 應用問題規模的增長速度。在當今的世界當中，典型的資料集（資料庫規模）都是以TB為機關，而我們的記憶體大小也大多都是8G、16G、32G、64G…。是以，相對而言，我們的記憶體容量非常小，并且呈現越來越小的趨勢。

那麼為什麼不直接把記憶體做大一點呢？實際上，當我們的存儲器容量越大/小，通路速度就會越慢/快。

事實1：不同容量的存儲器，通路速度的差異懸殊。以磁盤與記憶體為例： m s / n s ms / ns ms/ns > > > 1 0 5 10^5 105，如果一次記憶體通路需要一秒，那麼外存通路就相當于一天。是以，為了避免一次外存通路，我們甯願通路記憶體10次、100次、甚至千次、萬次。

大多數的存儲系統，都是分級組織的（Caching），最常用的資料盡可能放在更高層、更小的存儲器中，如果實在找不到，才向更低層、更大的存儲器索取。如果希望向更低的存儲級别寫入，或者向更高的存儲級别讀出資料，我們都稱之為I/O。更高層的存儲器，向更低層的存儲器通路都可以稱為外存通路。為了避免通路速度的差異懸殊，我們要盡量避免I/O操作。

事實2：從磁盤中讀寫1B的資料，與讀寫1KB的資料幾乎一樣快。

是以，無論是記憶體向外存寫入資料，還是外存向記憶體讀出資料，涉及的資料都是批量式地以頁或塊為基本機關。在大量資料的通路中，我們就要充分利用批量通路的特性：要麼就一次性通路1KB的資料，要麼就1B也不通路。

而基于上面兩個事實，我們的主角B-樹就扮演了一個非常重要的角色。下圖就是一個典型的B-樹。

我們可以看出，B-樹相對于二叉搜尋樹，每一個結點可以擁有更多的分支，表現的更寬、更矮。同時，所有的葉子結點都處于同一個深度。從這個意義上講，它不失為一種理想平衡的搜尋樹。

在多級存儲系統中使用B-樹，可針對外部查找，大大減少I/O次數。

難道，我們之前學習過的AVL樹還不夠嗎？比如，如果有 n = 1 G n=1G n=1G 個記錄，也就是說使用AVL樹每次查找有可能需要 l o g ( 2 , 1 0 9 ) = 30 log(2, 10^9)=30 log(2,109)=30 次I/O操作，也就是深入30層低級存儲層，并且每次隻能讀出一個關鍵字，得不償失。

那麼B-樹表現又如何呢？我們知道B-樹每一個結點可以包含多個關鍵字，它可以充分利用外存對批量通路的高效支援，将此特點轉換為B-樹的優點。每下降一層，都是以一個多關鍵字的結點為機關。

那麼B-樹具體應該多少個關鍵字為一個結點呢？這需要視磁盤的外存本身設定的資料緩沖頁的大小而定，假設一個頁的大小為1KB，每一個關鍵字的大小是4B，那麼一個結點就應該包含 n = 1 K B / 4 B = 250 n=1KB/4B=250 n=1KB/4B=250 個關鍵字。目前多數的資料庫系統采用 n = 200 n=200 n=200 ~ 300 300 300 個關鍵字。

回到我們之前舉的 1 G 1G 1G資料查詢的例子，若取 n = 256 n=256 n=256，則每次查找隻需要 l o g ( 256 , 1 0 9 ) ≤ 4 log(256, 10^9)≤4 log(256,109)≤4 次I/O，而4次相對于AVL樹的30次，是一個非常大的提高。

二、B-樹的定義

所謂 m m m 階B-樹，即 m m m 路平衡搜尋樹（ m ≥ 2 m≥2 m≥2），這裡的路，可以了解為分支。

外部結點的深度統一相等，所有葉結點的深度統一相等。

【解釋】葉結點：葉結點是内部結點最後一層的結點，外部結點：外部結點是葉結點的空孩子。

B-樹的樹高=外部結點的高度。

B-樹的每個内部結點各有：不超過 n = m − 1 n=m - 1 n=m−1 個關鍵字，不超過 m m m 個分支。

具體的， m m m 階B-樹的根結點的分支數在 [ 2 , m ] [2,m] [2,m]之間，其餘非根結點的内部結點的分支數在 [ ⌈ m 2 ⌉ , m ] [\lceil\frac{m}{2}\rceil,m] [⌈2m​⌉,m] ，是以B-樹又稱作 ( ⌈ m 2 ⌉ , m ) (\lceil\frac{m}{2}\rceil,m) (⌈2m​⌉,m)-樹

例如，當 m = 5 m=5 m=5 時，每個結點的分支數上限不能超過 5 5 5，非根結點的一般結點的分支數的下限也不能低于 ⌈ 5 2 ⌉ = 3 \lceil\frac{5}{2}\rceil=3 ⌈25​⌉=3，是以 5 5 5 階B樹又稱為 ( 3 , 5 ) (3,5) (3,5)-樹；當 m = 4 m=4 m=4， 4 4 4 階B樹又稱為 ( 2 , 4 ) (2,4) (2,4)-樹，而 ( 2 , 4 ) (2,4) (2,4)-樹與我們後面要講到的紅黑樹又有緊密的關系。

三、B-樹的查找

B-樹中所存儲的記錄非常多，是以不便于全部存儲在記憶體中，甚至根本不能由記憶體容納。是以我們通常将B-樹存放在相對于速度更慢的外存之中。

所謂B-樹的查找，其訣竅在于隻需要将必須的若幹個結點載入記憶體，通過這種政策可以盡可能的減少I/O的次數。

對于一棵處于活躍狀态的B-樹而言，我們可以假設其根結點已經載入到記憶體中。現在假設要查找關鍵字 k e y key key，我們先在根結點中順序查找是否存在該關鍵字，如果能在某個位置命中，查找結束。假設查找失敗于一個特殊的位置，這個位置會存放一個引用，這個引用将會指向B-樹中存儲在外存中的下一層的某個結點，是以我們通過一次I/O操作找到對應結點，并且将其載入到記憶體之中，然後我們繼續在該結點中進行順序查找…，依次執行上述操作。

在最壞情況下，這個過程可能反複執行到葉結點，到達葉結點後依然需要進行順序查找，如果繼續失敗，則指向葉結點之外的外部引用。

事實上，如果這個外部引用為空，則整個查找以失敗告終。但是更多情況下，這個外部引用會指向另一個存儲在更低存儲層次上的B-樹，這樣就可以将不同資料規模的B-樹串接起來。這也是為什麼将這個引用稱為“外部結點”。

有的同學可能會提出，能否用二分查找來優化查找結點内部有序關鍵字呢？事實上，相對于高耗時的I/O操作，這種優化是微乎其微的，甚至可能有害。我們知道一個結點内部的關鍵字數大概在 200 200 200 ~ 300 300 300，對于這種數量級的關鍵字，實驗表明使用二分查找的效率反而更低。

所謂的B-樹的通路，無非就是外存操作（垂直方向）和記憶體操作（水準方向）交替的過程，有多少次外存操作，就有多少次記憶體操作。

四、B-樹的插入

首先，與B-樹的查找的方法一緻，在6階B-樹中找到關鍵字37應該插入的位置，如下圖。

我們知道， 6 6 6 階B-樹的一個結點中最多隻可以容納 5 5 5 個關鍵字。此時，我們可以發現下層結點中關鍵字的多于 5 5 5 個，我們稱這個結點為上溢結點，需要通過B-樹特有的分裂方法調整。

4.1 分裂

1. 設上溢結點中的關鍵字依次為 [ k 0 , . . . , k m − 1 ] [k_0,...,k_{m-1}] [k0​,...,km−1​]
2. 取中位數 s = ⌊ m 2 ⌋ s=\lfloor \frac{m}{2} \rfloor s=⌊2m​⌋，以關鍵字 k s k_s ks​ 為界劃分為 [ k 0 , . . . , k s − 1 ] [k_0,...,k_{s-1}] [k0​,...,ks−1​]， [ k s ] [k_s] [ks​]， [ k s + 1 , . . . , k m − 1 ] [k_{s+1},...,k_{m-1}] [ks+1​,...,km−1​] 三個結點
3. 關鍵字 [ k s ] [k_s] [ks​] 結點上升一層，并進行分裂操作，将所得的左右另外兩個分别作為左、右孩子。

上例中關鍵字37上升、分裂之後的效果如下圖所示。

4.2 再分裂

如果上溢結點的父親結點原本也處于分裂的邊緣， [ k s ] [k_s] [ks​] 上升之後如果使父親結點也成為上溢結點，則需要對父結點再次使用分裂操作，成為再分裂。

上溢可能持續發生，并且逐層向上傳播；縱然發生了最壞的情況，也不過上溢到根結點。但是，根結點的上溢處理略有不同。如果根結點發生了上溢，則上升的結點 k s k_s ks​ 将作為整棵B-樹的新的根，原先的根節點分裂為2個孩子挂在根結點 [ k s ] [k_s] [ks​] 的兩側，如下圖。

這也是B-樹高度增加的唯一情況。

五、B-樹的删除

首先，與B-樹的查找的方法一緻，在m階B-樹中找到關鍵字應該删除的位置直接删除即可，但是如果删除之後結點内部的關鍵字數量過少，即通過删除一個關鍵字隻剩下 ⌈ m 2 ⌉ − 2 \lceil \frac{m}{2} \rceil - 2 ⌈2m​⌉−2個結點 ⌈ m 2 ⌉ − 1 \lceil \frac{m}{2} \rceil - 1 ⌈2m​⌉−1 個分支。則必須通過旋轉和合并操作調整結點。

注意：旋轉操作的優先級大于合并操作，隻有當旋轉操作的條件無法滿足時，才進行合并操作。

5.1 旋轉

如果發生了下溢，下溢結點首先會左顧右盼看其左右子樹是否有盈餘（必須是相鄰的左右子樹，其他兄弟結點不能進行旋轉）。這裡舉例左子樹有盈餘，則優先朝左子樹最後一個結點借。

為什麼是一定是朝左子樹最後一個結點借？因為B-樹依然要保證中序周遊的有序性，讓 x x x 上升到 y y y 的位置，再讓 y y y 下降到下溢結點的第一個位置。這樣做則中序周遊依然能夠保持有序性。

相反的，如果左子樹不夠借，再看看右子樹是否有盈餘。如果有，則将右子樹第一個結點替換到其父結點的位置，将父結點所對應的元素補充給下溢結點的最後一個位置，這樣就能保證中序周遊依然是有序的。

旋轉的優先級是高于合并操作的，但是旋轉的條件不一定能夠滿足（左右兄弟不一定有盈餘），則需要合并操作。

5.2 合并

發生下溢的結點在經過左顧右盼後，都沒有找到可以幫忙的左右結點，旋轉操作無法執行。則需要進行合并操作。

此時，左兄弟 和 右兄弟或者不存在，或者所含的關鍵字均不足 ⌈ m 2 ⌉ \lceil \frac{m}{2} \rceil ⌈2m​⌉ 個。

注意：此時還不算糟糕透頂，畢竟左兄弟和右兄弟至少存在一個（因為即使是根結點都有兩個子樹），且恰巧包含 ⌈ m 2 ⌉ − 1 \lceil \frac{m}{2} \rceil - 1 ⌈2m​⌉−1 個關鍵字，這裡不妨以存在左兄弟為例。

此時，無論是結點 L L L 還是下溢結點 V V V，關鍵字的個數都非常的少，并且 [ L ] [L] [L]、 [ y ] [y] [y]、 [ V ] [V] [V] 三個結點的總和關鍵字的個數都不會超過結點的關鍵字上界 m − 1 m - 1 m−1，是以直接将其三者合并（原先 [ y ] [y] [y] 左右兩個分支也合并為一個指針指向合并結點），來解決結點 V V V 的下溢問題。

通過合并之後，依然能夠保持中序周遊的有序性。

但是問題還沒有結束，通過合并以後，上層的父結點失去了一個關鍵字，父結點有可能是以發生了下溢。是以再嘗試對父結點進行旋轉，如果無法旋轉，則繼續合并，如法炮制。跟旋轉操作一樣，最壞情況下，也隻是達到了樹根。

補充：B+樹

因為B+樹不是本章的重點，但是既然講到了B-樹，那麼也理應帶上一點B+樹的影子。在這裡我就直接引用另外一個作者的文章，供大家參考：【B+樹和B樹的差別】