B 樹作為數據庫索引核心結構，其性質判斷是考研、面試高頻考點。本文逐條分析四個陳述的正誤，釐清易混淆概念。
陳述逐條解析
A. m 階 B 樹中任何一個結點的左右子樹的高度都相等
判斷：錯誤
- B 樹是多路平衡查找樹，「平衡」指所有葉子結點在同一層（即從根到任意葉子的路徑長度相等）
- 非葉子結點有
m 個子樹（m 路），而非二元「左右子樹」
- 正確表述：所有葉子結點深度相同，或 根到任意葉子路徑長度相等
B. 含 10 個葉結點的 3 階 B 樹中至多有 8 個非葉結點
判斷：錯誤
- 3 階 B 樹（即 2-3 樹）非葉結點關鍵字數：1 或 2，孩子數：2 或 3
- 非葉結點最少 2 個孩子 → 非葉結點數 最少 時，樹最高
- 非葉結點最多 3 個孩子 → 非葉結點數 最多 時，樹最矮
- 計算最多非葉結點（樹最高）：每非葉結點僅 2 個孩子
- 第 1 層 (根)：1 個
- 第 2 層：2 個
- 第 3 層：4 個
- 第 4 層：8 個葉子 → 非葉結點 = 1+2+4 = 7 個
- 實際 10 葉子需更多層，但非葉結點數 ≤ 7，絕不可能達到 8
- 正確答案：至多 7 個非葉結點（對應 2-3 樹最高情況）
C. B 樹是一種動態索引結構，既適用於隨機查找，也適用於順序查找
判斷：錯誤
- B 樹適合隨機查找（O(log n) 定位單條記錄）
- 不適合順序查找（範圍查詢/全表掃描）：
- 需中序遍歷，頻繁在父子結點間跳轉，磁盤 I/O 開銷大
- 葉子結點無鏈表連接，無法順序訪問下一葉子
- B+ 樹才適合順序查找：葉子結點雙向鏈表連接，範圍查詢只需遍歷葉子鏈表
- 此陳述混淆了 B 樹與 B+ 樹特性
D. 對於 B 樹中任何一個非葉結點中的關鍵碼 K，比 K 大的最小關鍵碼和比 K 小的最大關鍵碼一定都在葉結點中
判斷：正確
- B 樹性質：所有關鍵字分佈在整棵樹中（非葉、葉均含關鍵字）
- 但關鍵字的前驅/後繼（即比 K 小的最大值、比 K 大的最小值）必定在葉子結點
- 原因：中序遍歷序列中，K 的前驅是左子樹最右葉子的最大關鍵字，後繼是右子樹最左葉子的最小關鍵字
- 此性質是 B 樹區別於 B+ 樹的關鍵之一（B+ 樹關鍵字僅在葉子）
總結表
| 選項 | 正誤 | 核心知識點 |
|---|
| A | ❌ | B樹平衡性指葉子同層，非左右子樹 |
| B | ❌ | 3階B樹10葉子最多7非葉節點 |
| C | ❌ | B樹不適合順序查找，B+樹才適合 |
| D | ✅ | 非葉節點關鍵字的前驅後繼在葉子 |
記憶口訣
- B樹：多路、平衡(葉同層)、關鍵字分佈全樹、隨機查找強、順序查找弱
- B+樹：關鍵字僅葉子、葉子雙向鏈表、隨機+順序雙強、數據庫索引首選
精準掌握 B 樹與 B+ 樹的差異，是攻克數據庫索引原理的關鍵一步。
