1 概述

B樹是為磁盤或其它直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜索樹。B樹類似于紅黑樹，但它在降低磁盤I/O操作方面要更好一些。許多數(shù)據(jù)庫系統(tǒng)使用B樹或者B樹的變種來存儲信息（比如MYSQL的B+tree）。

如圖，當B樹的一個內(nèi)部結(jié)點x包含x.n個關(guān)鍵字，那么結(jié)點x就有x.n+1個孩子。結(jié)點x中的關(guān)鍵字就是分隔點，它把節(jié)點x中所處理的關(guān)鍵字的屬性分隔為x.n+1個子域。當一課B樹中查找一個關(guān)鍵字時，基于對存儲在x中的x.n個關(guān)鍵字的比較，做出一個(x.n+1)路的選擇。葉結(jié)點的結(jié)構(gòu)和內(nèi)部結(jié)點的結(jié)構(gòu)不同，后面討論。

image.png

2 輔存上的數(shù)據(jù)結(jié)構(gòu)

磁盤結(jié)構(gòu)：

image.png

磁盤有兩個機械運動的部分：盤片旋轉(zhuǎn)和磁臂移動，這是一次I/O耗費時間的原因所在。磁盤每次存取多個數(shù)據(jù)項。由于大多數(shù)系統(tǒng)中，一個B樹算法的運行時間主要由它所執(zhí)行的DISK-READ和DISK-WRITE操作的次數(shù)決定，所以我們希望這些操作能夠讀或?qū)懕M可能的信息。因此，一個B樹結(jié)點通常和一個完整磁盤葉一樣大，并且一個磁盤頁的大小限制了一個B樹結(jié)點可以含有的孩子個數(shù)。

3 B樹的定義

任何和關(guān)鍵字相關(guān)聯(lián)的數(shù)據(jù)將于關(guān)鍵字一樣存放在同一個結(jié)點，實際上可能只是存放一個指針，這個指針存放該關(guān)鍵字對應的數(shù)據(jù)的磁盤頁。B+樹把所有的數(shù)據(jù)存在葉子結(jié)點，內(nèi)部結(jié)點只存放關(guān)鍵字和孩子指針，因此最大化了內(nèi)部節(jié)點的分支因子。

一棵B樹是具有以下性質(zhì)的有跟樹：

• 1.每個結(jié)點x有以下屬性：a. 有x.n個關(guān)鍵字；b. 關(guān)鍵字以非降序順序排列；c. x.leaf一個布爾值，true表示是葉結(jié)點；
• 2. 結(jié)點x包含x.n+1個孩子指針；
• 3. 關(guān)鍵字用于對子樹關(guān)鍵字范圍加以分割；
• 4. 每個葉結(jié)點具有相同的高度；
• 5. 每個結(jié)點所包含的關(guān)鍵字個數(shù)有上界和下界，用一個成為b樹的最小度數(shù)的固定整數(shù)t>=2 來表示這些界，t越大樹高度越小：
     a. 除根節(jié)點以外的每個結(jié)點x至少有t-1個關(guān)鍵字，至少t個孩子；
     b. 每個結(jié)點至多有2t-1個關(guān)鍵字，至多2t個孩子。

4 B樹的高度

h <= log(t) (n+1)/2 (t為對數(shù)的底)

5 B樹的基本操作

5.1 搜索

偽代碼如下

B-TREE-SEARCH(x, k)  //x為節(jié)點，k為插入關(guān)鍵字
i = 1  //
while i <= x.n and k > x.key(i) //搜索k所在的節(jié)點位置
    i = i + 1
 if i <= x.n and k == x.key(i)
    return (x, i)
elseif x.leaf  //當前是子節(jié)點，返回NIL
    return NIL
else  DISK-READ(x, c(i)) //查找子節(jié)點
    return B-TREE-SEARCH(x.c(i), k) 

5.2 插入

創(chuàng)建一棵空的B樹

為構(gòu)造一棵B樹T，先用B-TREE-CREATE來創(chuàng)建一個空的根結(jié)點，然后調(diào)用B-TREE-INSERT來添加新的關(guān)鍵字。這些過程都要用一個輔助過程ALLOCATE-NODE,它在O(1)時間內(nèi)為一個新節(jié)點分配一個磁盤頁，我們可以假定由ALLOCATE-NODE所創(chuàng)建的結(jié)點并不需要DISK-READ,因為磁盤上還沒有關(guān)于該結(jié)點的有用信息。

B-TREE-CREATE(T)
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x

分裂

由于不能將關(guān)鍵字插入一個滿的葉結(jié)點，故引入一個操作，將一個滿的結(jié)點y（有2t-1個關(guān)鍵字）按中間的關(guān)鍵字y.key(t)分裂為兩個各含t-1個關(guān)鍵字的結(jié)點。中間關(guān)鍵字被提升到y(tǒng)的父結(jié)點，以標識兩棵新樹的劃分點。但是如果y的父結(jié)點也是滿的，就必須在插入新的關(guān)鍵點之前將其分裂，最終滿結(jié)點的分裂會沿著樹向上傳播。

與一個二叉搜索樹一樣，可以在從樹根到葉子這個單程向下過程中將一個新的關(guān)鍵字插入B樹中，為了做到這一點，我們并不是等到找出插入過程中實際要分裂的滿結(jié)點時才做分裂。相反，當沿著樹往下查找新的關(guān)鍵字所屬位置時，就分裂沿途遇到的每個滿結(jié)點（包括葉結(jié)點本身）。因此，每當要分裂一個滿結(jié)點y時，就能確保它的父結(jié)點不是滿的。

分裂B樹中的結(jié)點

image.png

B-TREE-SPLIT-CHILD(x, i) //x是結(jié)點，i為x的滿子節(jié)點的下標
z = ALLOCATE-NODE()
y = x.c(i)
z.leaf = y.leaf
z.n = t - 1
for j = 1 to t - 1  // 復制關(guān)鍵字
    z.key(j) = y.key(j + 1)
if not y.leaf // 復制孩子指針
    for j = 1 to t
        z.c(j) y.c(j+t)
y.n = t - 1    
for j = x.n + 1 downto i + 1 //上層增加一個子節(jié)點，關(guān)鍵字和孩子結(jié)點要向前推進1
    x.c(j + 1) = x.c(j)
x.c(i + 1) = z
for j = x.n downto i 
    x.key(j + 1) = x.key(j)
x.key(i) = y.key(i)
x.n = x.n + 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)

沿樹單程下行方式向B樹插入關(guān)鍵字

在一顆高度為h的B樹T中，沿樹單程下行方式插入一個關(guān)鍵字k的操作需要O(h)次磁盤存取。所需要的CPU時間為O(th) = O(tlog(t)n)。過程B-TREE-INSERT利用B-TREE-SPLIT-CHILD來保證遞歸始終不會降至一個滿結(jié)點上。

//把關(guān)鍵字k插入T樹中
B-TREE-INSERT(T, k)
r = T.root
if r.n == 2t - 1  //如果根結(jié)點為滿，則分裂
    s = ALLOCATE-NODE()
    T.root = s
    s.leaf = FALSE
    s.n = 0
    s.c1= r
    B-TREE-SPLIT-CHILD(s, 1) 
    B-TREE-INSERT-NONFULL(s, k)
else 
    B-TREE-INSERT-NONFULL(s, k)

//插入未滿的結(jié)點
B-TREE-INSERT-NONFULL(x, k)
i = x.n
if x.leaf //如果是葉子結(jié)點，直接找到位置插進去
    while i >= 1 and k < x.key(i)
        x.key(i+1) = x.key(i)
        i = i - 1
    x.key(i + 1) = k
    x.n = x.n + 1
    DISK-WRITE(x)
else while  i >= 1 and k < x.key(i) //內(nèi)葉結(jié)點則找到位置，判斷所在的孩子結(jié)點是否已滿，滿則分裂，未滿則對孩子結(jié)點遞歸調(diào)用自己
              i = i  - 1
        i = i + 1
        DISK-READ(x, c(i))
        if x.c(i).n ==  2t - 1
            B-TREE-SPLIT-CHILD(x, i) 
            if k > x.key(i)
                i = i + 1
       B-TREE-INSERT-NONFULL(x.c(i), k)

image.png

5.3 刪除

必須防止刪除操作而導致樹的結(jié)構(gòu)違反B樹的性質(zhì)。下面簡要介紹刪除操作如何工作：

• 1 如果關(guān)鍵字k在結(jié)點x中，并且x是葉結(jié)點，則從x中刪除k；

• 2 如果關(guān)鍵字k在結(jié)點x中，并且x是內(nèi)部結(jié)點，則有下面的情況：

  • a 如果結(jié)點x中前于k的子結(jié)點y至少包含t個關(guān)鍵字，則找出k在以y為根的子樹中的前驅(qū)k'。遞歸地刪除k'，并且在x中用k'代替k。（找到k'并刪除它可在沿樹下降的單過程中完成）。
  • b 對稱地，如果y有少于t個關(guān)鍵字，則堅持結(jié)點x中后于k的子結(jié)點z。如果z至少有t個關(guān)鍵字，則找出k在以z為根的子樹中的后繼k'。遞歸地刪除k'，并在x中用k'代替k。
  • c 否則，如果y和z都只含有t-1個關(guān)鍵字，則將k和z的全部合并進y，這樣x就失去了k和指向z的指針，并且y現(xiàn)在包含2t-1關(guān)鍵字，然后釋放z并遞歸地從y中刪除k。

• 3 如果關(guān)鍵字k當前不在內(nèi)部結(jié)點x中，則確定比包含k的子樹的根x.c(i)（如果k確實在樹中）。如果x.c(i)只有t-1個關(guān)鍵字，必須指向步驟3a或3b來保證將至一個至少包含t個關(guān)鍵字的結(jié)點。然后，通過對x的某個合適的子結(jié)點進行遞歸而結(jié)束。

  • a 如果x.c(i)只含有t-1個關(guān)鍵字，但是它的一個相鄰的兄弟至少包含t個關(guān)鍵字，則將x中的某一個關(guān)鍵字降至x.c(i)中，將x。c(i)的相鄰左兄弟或右兄弟的一個關(guān)鍵字升至x，將該兄弟中相應的孩子指針移到x.c(i)中,這樣就使得x.c(i)增加了一個額外的關(guān)鍵字。

  • b 如果x.c(i)以及x.c(i)中的所有鄰兄弟都只包含t-1個關(guān)鍵字，則將x.c(i)與一個兄弟合并，即將x的一個關(guān)鍵字移至新合并的結(jié)點，使之成為該結(jié)點的中間關(guān)鍵字。

    
    
    a.png