B-tree vs B+tree

   B-Tree和B+Tree

目前大部分資料庫系統及檔案系統都采用B-Tree或其變種B+Tree作為索引結構，在本文的下一節會結合存儲器原理及計算機存取原理讨論為什麼B-Tree和B+Tree在被如此廣泛用于索引，這一節先單純從資料結構角度描述它們。

B-Tree

為了描述B-Tree，首先定義一條資料記錄為一個二進制組[key, data]，key為記錄的鍵值，對于不同資料記錄，key是互不相同的；data為資料記錄除key外的資料。那麼B-Tree是滿足下列條件的資料結構：

d為大于1的一個正整數，稱為B-Tree的度。

h為一個正整數，稱為B-Tree的高度。

每個非葉子節點由n-1個key和n個指針組成，其中d<=n<=2d。

每個葉子節點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節點的指針均為null 。

所有葉節點具有相同的深度，等于樹高h。

key和指針互相間隔，節點兩端是指針。

一個節點中的key從左到右非遞減排列。

所有節點組成樹結構。

每個指針要麼為null，要麼指向另外一個節點。

如果某個指針在節點node最左邊且不為null，則其指向節點的所有key小于v(key1)，其中v(key1)為node的第一個key的值。

如果某個指針在節點node最右邊且不為null，則其指向節點的所有key大于v(keym)，其中v(keym)為node的最後一個key的值。

如果某個指針在節點node的左右相鄰key分别是keyi和keyi+1且不為null，則其指向節點的所有key小于v(keyi+1)且大于v(keyi)。

圖2是一個d=2的B-Tree示意圖。

由于B-Tree的特性，在B-Tree中按key檢索資料的算法非常直覺：首先從根節點進行二分查找，如果找到則傳回對應節點的data，否則對 相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，後者查找失敗。B-Tree上查找算法的僞代碼如下：

BTree_Search(node, key) {

   if(node == null) return null;

   foreach(node.key)

   {

       if(node.key[i] == key) return node.data[i];

           if(node.key[i] > key) return BTree_Search(point[i]->node);

   }

   return BTree_Search(point[i+1]->node);

}

data = BTree_Search(root, my_key);

關于B-Tree有一系列有趣的性質，例如一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為logd((N+1)/2)，檢索一個key，其查找節點個數的漸進複雜度為O(logdN)。從這點可以看出，B-Tree是一個非常有效率的索引資料結構。

另外，由于插入删除新的資料記錄會破壞B-Tree的性質，是以在插入删除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質，本 文不打算完整讨論B-Tree這些内容，因為已經有許多資料詳細說明了B-Tree的數學性質及插入删除算法，有興趣的朋友可以在本文末的參考文獻一欄找 到相應的資料進行閱讀。

B+Tree

B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實作其索引結構。

與B-Tree相比，B+Tree有以下不同點：

每個節點的指針上限為2d而不是2d+1。

内節點不存儲data，隻存儲key；葉子節點不存儲指針。

圖3是一個簡單的B+Tree示意。

圖3

由于并不是所有節點都具有相同的域，是以B+Tree中葉節點和内節點一般大小不同。這點與B-Tree不同，雖然B-Tree中不同節點存放的key和指針可能數量不一緻，但是每個節點的域和上限是一緻的，是以在實作中B-Tree往往對每個節點申請同等大小的空間。

一般來說，B+Tree比B-Tree更适合實作外存儲索引結構，具體原因與外存儲器原理及計算機存取原理有關，将在下面讨論。

帶有順序通路指針的B+Tree

一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序通路指針。

圖4

如圖4所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的B+Tree。做這個優化的目的是為了提高 區間通路的性能，例如圖4中如果要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點， 極大提到了區間查詢效率。

這一節對B-Tree和B+Tree進行了一個簡單的介紹，下一節結合存儲器存取原理介紹為什麼目前B+Tree是資料庫系統實作索引的首選資料結構。

本文轉自 位鵬飛 51CTO部落格，原文連結：http://blog.51cto.com/weipengfei/1256155，如需轉載請自行聯系原作者