B-tree（B樹）和B+tree（B+樹）是兩種高效的多叉樹數據結構，專為磁盤存儲系統優化設計，廣泛應用于數據庫和文件系統的索引。以下是兩者的核心特點及區別：

---

?? 一、B-tree（B樹）

1. 結構特性

   • 多路平衡：每個節點可包含多個子節點（通常稱為階數 m），非葉子節點存儲 鍵值（Key） 和 關聯數據（Data）。
   • 平衡規則：
     • 根節點至少有 2 個子節點（除非為葉子節點）；
     • 非根節點至少有 ?m/2? 個子節點；
     • 所有葉子節點位于同一層。

2. 數據存儲

   • 鍵值+數據共存：非葉子節點既存儲索引鍵，也存儲實際數據記錄。
   • 搜索靈活性：搜索可能在非葉子節點終止（若命中鍵值）。

3. 適用場景

   • 實時查詢系統：如 MongoDB 的默認索引，適合單點查詢。

---

🚀 二、B+tree（B+樹）

1. 結構優化

   • 數據分離：非葉子節點 僅存儲鍵值（不存實際數據），所有數據記錄存放在 葉子節點。
   • 葉子節點鏈表：葉子節點通過指針串聯為有序鏈表，支持高效范圍查詢。

2. 性能優勢

   • 更高扇出：非葉子節點僅存鍵值，可容納更多子節點，降低樹高，減少 I/O 次數。
   • 順序訪問優化：范圍查詢（如 WHERE id BETWEEN 10 AND 100）直接遍歷葉子鏈表，無需回溯樹。

3. 適用場景

   • 數據庫索引：如 MySQL InnoDB 引擎，尤其適合范圍掃描和排序操作。

---

🔍 三、核心區別總結

特性	B-tree	B+tree
非葉子節點數據	存儲鍵值+數據	僅存儲鍵值（無數據）
葉子節點結構	獨立無鏈接	通過指針形成有序鏈表
查詢終止位置	可能在任何非葉子節點命中	必須到達葉子節點
范圍查詢效率	低效（需回溯樹）	高效（直接遍歷葉子鏈表）

---

💡 四、典型應用

• B-tree：文件系統（NTFS/Ext4）、MongoDB 索引。
• B+tree：關系型數據庫（MySQL、Oracle）、大型數據倉庫索引。

兩種結構均通過 多路平衡 和 動態調整節點（分裂/合并）保持低樹高，顯著減少磁盤 I/O。B+tree 因數據分離和鏈表設計，在大數據量下綜合性能更優，成為數據庫索引的主流選擇。