B-tree 資料結構

前言：在學習 PostgreSQL 關於索引的章節時，我開始好奇資料庫在執行查詢時，背後是如何提升搜尋效率的。這讓我接觸到了 B-tree 這種常用的資料結構，也因此產生了濃厚的興趣。以下是我針對 B-tree 所整理的學習筆記，並輔以 JavaScript 的實作來說明。

B-tree 基本概念

1. 鍵值排序：每個節點中的鍵值都按照遞增順序儲存。
2. 葉節點標記：每個節點都有一個布林值 leaf，當該節點是葉節點時，此值為 true。
3. 節點容量：如果 n 是樹的階數（order），每個內部節點最多可以包含 n-1 個鍵值，並且有指向每個子節點的指標。
4. 子節點數量限制：除了根節點外，每個內部節點最多可以有 n 個子節點，最少要有 ⌈n/2⌉ 個子節點（向上取整）。對於葉節點，最多有 n-1 個鍵值，最少有 ⌈n/2⌉-1 個鍵值。
5. 葉節點深度一致：所有葉節點都位於相同的深度（即樹的高度 h）。
6. 根節點特性：如果根節點不是葉節點，則至少有 2 個子節點；如果是葉節點，則至少包含 1 個鍵值。根節點不受最小鍵值數量限制。
7. 高度公式：如果 n ≥ 1，對於任何包含 n 個鍵值的 B-tree，其高度 h 和最小度數 t ≥ 2，滿足：h ≥ log_t((n+1)/2)。

重點說明

• 階數（Order）：決定了節點可以擁有的最大子節點數量
• 最小度數（Minimum Degree）：通常記為 t，階數 n 與最小度數 t 的關係為 n = 2t，或 t = ⌈n/2⌉
• 平衡性：B-tree 透過分裂和合併操作保持所有葉節點在同一層，確保查詢效率

B-tree 常見應用場景

1. 資料庫索引

像 PostgreSQL 這類資料庫會用 B-tree 來加快查詢速度，比如快速找到某位使用者或某筆訂單。

2. 檔案系統

電腦的檔案系統（像是 Windows 或 Mac）會用 B-tree 來幫忙快速找到檔案或資料夾。

3. 關聯式資料庫的的資料查詢 (ex: PostgreSQL)

如果我們查詢一段資料範圍（例如「價格在 100 到 200 之間」），PostgreSQL 的 B-tree 索引可以幫我們快速抓出結果。

4. 作業系統管理記憶體

作業系統會用類似 B-tree 的方法，來記住哪些記憶體有被用到、哪些還空著。

為什麼 B-tree 搜尋速度快？

B-tree 的設計重點是 每層節點都儲存多個 key，這讓整棵樹可以「長得比較矮」，大幅減少從根節點走到葉節點所需的層數（也就是搜尋步驟）。

以下是範例圖示：

高度為 3 的 B-tree（每個節點最多有 3 個子節點）

假設我們要找的是數字 25：

1. 從 root 節點 [28, 45] 開始，25 < 28 → 走左邊的路徑。
2. 進入左子節點 [15]，25 > 15 → 走右邊的路徑。
3. 到達葉節點 [20, 25]，找到 25！

即使資料筆數變多，只要維持樹的平衡與分裂規則，層數也不會爆增，因此搜尋時間通常維持在 O(log N) 的效率，非常適合大量資料的快速查詢。

B-tree 基本概念與插入示意（階數 =3, bottom-up 分裂）

插入順序: [10, 20, 5, 6, 12, 30, 7, 17]

Insert 10

Insert 20

Insert 5

[5, 10, 20] 滿了，分裂並將 10 上提：

Insert 6 → 插入左子節點

Insert 12 → 插入右子節點

Insert 30 → 插入右子節點，觸發分裂

30 插入到 [12, 20]，導致該節點滿，分裂並將 20 上提：

Insert 7 → 插入左節點，觸發分裂

[5, 6, 7] 滿了，因此將 6 上提，並入 [10, 20] 內

[6, 10, 20] 滿了，因此將 10 上提

Insert 17 → 插入 [12] 成為 [12, 17]

最終 B-tree 結構

這是一個以 bottom-up 分裂實現的 B-tree，插入順序 [10, 20, 5, 6, 12, 30, 7, 17]，結構對齊圖解預期。

程式碼實作（由 AI 協助撰寫與整理）

TL;DR

🔗 參考資源與延伸閱讀

1. Understanding B-Trees: The Data Structure Behind Modern Databases - 這部影片提供了清晰的視覺化流程，幫助我建立 B-tree 的基本認知與操作方式。
2. PostgreSQL 官方文件：索引與 B-tree - 深入了解 B-tree 在實際資料庫系統（如 PostgreSQL）中的應用與最佳化策略。
3. Rogramiz
4. 本篇 JavaScript 實作部分，為了幫助理解整體邏輯與插入／刪除操作，我透過 AI（ChatGPT）輔助生成與優化程式碼，並根據實際學習需求進行調整。