目前大部分數據庫系統及文件系統都采用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示意圖。  圖2 由于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是數據庫系統實現索引的首選數據結構。