B 樹查找時間複雜度深度解析：O(log_m N) 的來龍去脈

標準答案

B 樹的查找時間複雜度為 O(log_m N)，其中：

• N：樹中關鍵字總數
• m：B 樹的階（每個節點最大子女數）

推導過程

1. B 樹高度分析

設 B 樹高度為 h（根節點高度為 0），階為 m。根據 B 樹定義：

• 根節點至少 2 個子女（除非是葉子）
• 非根內部節點至少 ⌈m/2⌉ 個子女
• 每個節點最多 m 個子女

因此，節點數最少時（最「瘦」的樹），高度最大：

N ≥ 1 + 2 * (⌈m/2⌉^0 + ⌈m/2⌉^1 + ... + ⌈m/2⌉^(h-1))
  ≈ 2 * (⌈m/2⌉^h - 1) / (⌈m/2⌉ - 1)

忽略常數項，得到：h = O(log_{⌈m/2⌉} N)

2. 查找過程

查找從根節點開始，每層進行一次節點內查找（二分查找或線性查找），然後下降到子節點。節點內查找複雜度為 O(log m) 或 O(m)，但 m 通常較小（如 100-1000），視為常數。

總複雜度 = 樹高 × 節點內查找 = O(log_m N) × O(1) = O(log_m N)

關鍵參數影響

B+ 樹與 B 樹的查找差異

• B 樹：關鍵字分佈在所有節點，查找可能在內部節點命中就結束。
• B+ 樹：所有關鍵字僅出現在葉子節點，非葉子節點僅作索引，**查找必須走到葉子層**，路徑長度固定為 h，性能更穩定，更適合範圍查詢。

工程實踐中的常見誤區

❌ 誤區：「B 樹查找是 O(log N)」（忽略了底數 m 的影響）
✅ 正確：「B 樹查找是 O(log_m N)，其中 m 是節點最大度數」

總結

B 樹通過增加節點度數（階數 m）來壓低樹高，將查找複雜度控制在 O(log_m N)，配合磁盤頁面大小設計節點，實現了極少的磁盤 I/O 次數，成為數據庫索引、文件系統的核心數據結構。