數據結構: B+Tree及其應用

02-15

在前面的文章中我們已經介紹了B-Tree的一些特性，以及B-Tree的插入及刪除操作。今天我們介紹一下B-Tree的一個變種 --> B+Tree。B+Tree是一種非常重要的數據結構，它廣泛應用於文件系統，及資料庫索引中。既然它是B-Tree的一個變種，自然他有很多特性和B-Tree就是一樣的，但它們也有以下兩點不同：

第一：在 B-Tree中一個含有n個子樹的節點有n-1個關鍵字(key)。而在 B+Tree中一個含有n個子樹的節點有n個關鍵字(key)。為什麼在擁有同樣子樹的情況下B+Tree的節點多需要一個key呢？那是因為 B+Tree的節點會存儲該節點的子樹中最小的key。

第二：B-Tree的每個節點都包含了關鍵字(key)以及指向包含這些關鍵字記錄的指針。而 B+Tree在葉子節點中存儲了所有的關鍵字信息，以及指向包含這些關鍵字記錄的指針。而且這些葉子節點構成一個有序鏈表，即每個葉子節點會有一個指針指向其兄弟節點。在非葉子節點中只存儲了關鍵字信息。下面這張圖畫的非常好，是我從百度圖片搜索而來。相信我們對照這張圖看就非常清楚了。

了解了B-Tree和B+Tree的結構後，我們來看看為什麼文件系統和資料庫索引大量採用這種數據結構。就拿資料庫的索引來說，需要創建索引一般數據量都較大，那麼創建出來的索引文件也會很大，所以索引一般不可能直接存儲在內存中，而是存儲在硬碟上（這裡我們考慮的是機械硬碟）。我們都知道硬碟的讀寫速度是遠遠趕不上內存的，一般都差了幾個數量級（機械硬碟讀寫速度慢主要就是因為它需要通過機械臂將磁頭移動到數據所在的磁軌上，要詳細了解磁碟的原理可以閱讀這篇文章Code-lovers Learning Notes）。而我們根據索引來查詢就會產生硬碟 I/O，所以要提高查詢的性能就必須降低 I/O 的次數（就是要減少磁頭移動的次數）。那麼B樹相對於其它的數據結構如AVL樹，紅黑樹，在降低 I/O 的次數方面有什麼優勢呢？很明顯由於B樹的每一個節點能存儲多個關鍵字信息（實際應用中每個節點都能存儲幾百個關鍵字信息，當然這個數字也不會非常大，因為它需要保證每個節點的所有關鍵字能在一次 I/O中就全部讀取到內存中，如果需要多次 I/O 的話，那就反而會降低性能。一次 I/O 讀取的數據一般為1頁，而在大多數操作系統中1也=頁的大小為 4 K，所以每個節點存儲的關鍵字信息的總大小不能超過 4K）而二叉樹每個節點只能存儲一個關鍵字信息，所以在數據量很大的情況下，二叉樹的高度會很大。例如根據我們前面推導的B樹的一個公式，N = 1 + s * ((m/2) - 1) = 2 * ( $(m/2)^{h-1}$ ) - 1，一個200階的高度為4的B樹最少能存儲2百萬個關鍵字信息。而同樣存儲2百萬個關鍵字信息則需要一顆高度為21的二叉樹。所以在這個200階的包含2百萬個關鍵字信息的B樹中查詢 I/O 的次數不會超過3次（因為根節點是常駐內存的），而同樣存儲2百萬個關鍵字信息的二叉樹則可能需要好幾倍次數的 I/O 性能就會差很多。

在資料庫索引的實現中，大部分採用的是B+Tree而不是B-Tree，這又是為什麼呢？

原因有二，其一是由於B+Tree 在非葉子節點中只存儲了關鍵字信息，而沒有存儲指向包含這些關鍵字記錄的指針，所以在樹的高度相同時，B+Tree往往能比B-Tree存儲更多的關鍵字信息。更最要的原因是因為 B+Tree在葉子節點中存儲了所有的關鍵字信息，以及指向包含這些關鍵字記錄的指針。而且這些葉子節點構成一個有序鏈表，這樣B+Tree在實現範圍查詢的時候就比較容易，只需要遍歷這個有序鏈表就行。而B-tree要實現範圍查詢則比較困難，但範圍查詢又是資料庫中比較常用的功能，所以資料庫中大部分採用的是B+Tree而不是B-Tree。當然B-Tree也有強於B+tree的地方，例如在隨機查詢中，由於B-Tree的每個節點都包含了關鍵字(key)以及指向包含這些關鍵字記錄的指針，所以B-Tree可能中途就查詢到需要的數據，不需要遍歷到葉子節點。而B+Tree由於只在葉子節點中存儲了所有的關鍵字信息，以及指向包含這些關鍵字記錄的指針。在非葉子節點中只存儲了關鍵字信息，沒有存儲指向包含這些關鍵字記錄的指針，所以B+Tree一定要遍歷到葉子節點才能獲取到包含這些關鍵字記錄的指針。所以B-Tree的隨機查詢性能會高於B+Tree。

在B+樹的基礎上又演變出B*樹，B*Tree在非葉子結點中也增加了指向兄弟節點的指針，並且它將非葉子節點上存儲的關鍵字個數的最小值提高到 (2/3) * m，這樣的話就提高了空間利用率。