🌳 什么是 B樹 和 B+樹？

它們都是多路平衡查找樹（M-Way Search Tree），用于提升磁盤讀寫效率，常用于數據庫（如 MySQL）、操作系統中的索引結構。

🔍 B樹 和 B+樹 的核心區別一覽

特性	B 樹	B+ 樹
數據存儲位置	所有節點都存數據（根、內、葉）	只有葉子節點存數據
內部節點內容	關鍵字 + 數據	只有關鍵字（不含實際數據）
葉子節點是否鏈表	? 否	? 是（葉子節點組成有序鏈表）
查詢效率	查詢速度不穩定，深度少但每層含數據	查詢穩定，需走到底但結構更簡單
范圍查詢	需遍歷整棵樹	? 非常高效，直接鏈表順序查
磁盤讀取次數	較少，但不規律	稍多，但更適合磁盤塊優化
典型應用	較少見，早期數據庫	? MySQL（InnoDB）、Linux 文件系統等

📌 形象理解

🟩 B樹結構：

        [ 10 | 20 ]/    |    \[5]  [15]  [25]/      |     \數據   數據   數據 （所有節點都存數據）

🟦 B+樹結構：

        [10 | 20]/    |    \[5]  [15]  [25]   <-- 只有關鍵字|     |     |[數據]→[數據]→[數據] （葉子節點鏈表）

🔥 為什么數據庫幾乎都用 B+ 樹？

1. 所有數據都在葉子節點，結構更統一，便于范圍查找
2. 葉子節點鏈表 → 范圍查詢效率極高
3. 磁盤讀取更高效：內部節點更“輕”，一頁能裝更多 key，樹更矮，訪問路徑更短
4. 支持順序遍歷：天然有序，分頁、between 查詢非常友好

? 一句話總結

B 樹適合內存查找結構，B+ 樹更適合磁盤和數據庫，因為它只在葉子節點存數據、結構更穩定、查詢更高效。