B樹、B-tree與B+樹

在計算機科學，尤其是數據庫和文件系統的領域中，B樹、B-tree和B+樹是理解數據如何被高效存儲和檢索的關鍵。它們之間關系緊密，但功能和應用上又存在著決定性的差異。

一、 核心概念澄清：B樹就是B-tree

首先需要明確一個最基本的概念：B樹和B-tree是完全相同的概念。B-tree是其英文原名，在國內的翻譯過程中，有時被直譯為“B-樹”，有時被意譯為“B樹”。這兩種叫法指代的都是同一種自平衡的多路搜索樹結構，它能在對數時間內完成數據的查找、插入和刪除操作。

二、 主角登場：為什么數據庫索引偏愛B+樹？

當您聽到“數據庫索引”時，可以有九成的把握認為其底層實現是B+樹。是的，絕大多數現代關系型數據庫（如MySQL的InnoDB、PostgreSQL）都選擇B+樹作為其標準和默認的索引結構。

這并非偶然，而是因為B+樹的結構特性完美地解決了數據庫存儲的核心痛點：最大限度地減少昂貴的磁盤I/O操作。

B+樹之所以能成為主流，主要有以下幾點關鍵優勢：

1. 更低的樹高，更少的磁盤I/O：

   • B+樹：其內部節點（非葉子節點）只存儲鍵（key）和指向下一層節點的指針，不包含實際的數據記錄。這使得在同樣大小的節點空間內（通常為一個磁盤頁，如16KB），B+樹的內部節點可以容納成百上千個鍵，其“扇出”（fan-out）非常高。極高的扇出意味著樹的整體高度會非常低。對于一個存儲著數億條記錄的表，其B+樹索引的高度通常也只有3-4層，這意味著查找任何數據最多只需要3-4次磁盤I/O。
   • B樹：其內部節點既存儲鍵，也存儲數據。這限制了每個節點能容納的鍵的數量，導致在同等數據量下，B樹的高度可能比B+樹更高，從而需要更多的磁盤I/O。

2. 極其穩定的查詢效率：

   • B+樹：所有的數據記錄都只存在于葉子節點上。因此，任何一次查找都必須從根節點開始，完整地走到某個葉子節點才能獲取數據。這保證了每次查詢的I/O次數是穩定且可預測的。
   • B樹：數據分散在所有節點中。雖然運氣好的時候可能在根節點或中間節點就找到數據，路徑更短，但這也意味著查詢性能是不穩定的，路徑長度在1到樹高之間波動。

3. 對范圍查詢的完美支持：

   • B+樹：這是它的“殺手锏”。所有葉子節點通過一個雙向鏈表相互連接，并且葉子節點內部的數據本身是有序的。當執行范圍查詢（如 WHERE age > 25 AND age < 40）時，引擎只需定位到起始葉子節點（age=25），然后就可以沿著鏈表順序掃描，直到范圍結束。這個過程高效且連續，極大地提升了范圍查詢的性能。
   • B樹：要進行范圍查詢，必須對樹進行復雜的中序遍歷，這會涉及到更多節點的訪問和回溯，效率遠低于B+樹。

三、 核心差異速覽表

特性	B樹 (B-tree)	B+樹 (B±tree)
數據存儲位置	所有節點（內部節點和葉子節點）都存儲鍵和數據。	只有葉子節點存儲鍵和數據，內部節點僅作為索引。
葉子節點結構	葉子節點之間相互獨立，沒有鏈接。	所有葉子節點通過雙向鏈表連接，形成一個有序序列。
查詢效率	不穩定，最好的情況是O(1)（數據在根節點），最差是O(logN)。	非常穩定，任何查詢的路徑長度都相同，為O(logN)。
范圍查詢	效率低，需要進行中序遍歷。	效率極高，利用葉子節點的有序鏈表即可完成。
空間與I/O	內部節點存儲數據，導致扇出較小，樹高可能更高，I/O次數可能更多。	內部節點不存數據，扇出極大，樹高很低，I/O次數少。

四、 數據庫索引的“非主流”選擇

盡管B+樹是當之無愧的主角，但一個成熟的數據庫系統也會根據特定場景提供其他索引結構作為補充：

• 哈希索引 (Hash Index)：在進行精確的等值查詢時（如 WHERE email = '...'），其速度極快，理論上時間復雜度為O(1)。但它完全不支持范圍查詢。
• R樹 (R-Tree)：專門用于處理多維空間數據，如地理位置信息。能高效回答“查找我附近5公里內的所有餐館”這類空間查詢。
• 全文索引 (Full-Text Index)：專門用于在大量文本中快速搜索關鍵詞，其底層是倒排索引（Inverted Index），可以高效處理 LIKE '%keyword%' 這種B+樹無能為力的模糊查詢。

總結

B樹與B-tree是同一種數據結構。B+樹是B樹的優化變體，它通過將數據全部下沉到葉子節點并用鏈表將葉子節點串聯起來，實現了更低的樹高、更少的磁盤I/O、更穩定的查詢性能和極其高效的范圍查詢能力。

因此，B+樹成為了關系型數據庫索引技術當之無愧的基石。雖然在處理特定類型的數據和查詢（如空間數據或全文搜索）時會采用R樹或全文索引等專用結構，但在絕大多數通用場景下，B+樹都是性能和功能之間最佳的平衡點。