高考申論題
109年
[資訊處理] 資料結構
第 一 題
📝 此題為申論題，共 2 小題
小題 (一)
請描述 order 為 m 的 B-tree 之特性。（6分）
思路引導 VIP
看到 B-tree 特性題，應立即聯想其為「平衡的多路搜尋樹（Balanced Multi-way Search Tree）」。解題關鍵在於精確列出定義的五大要素：節點最大分支度、內部節點最小分支度（⌈m/2⌉）、根節點限制、鍵值與指標數量的關係，以及葉節點齊平（同層）的絕對平衡特性。
小題 (二)
請問 order 為 m 高度為 h 的 B-tree：⑴最多有幾個節點？最多有幾個Key？（6分）⑵最少有幾個節點？最少有幾個 Key？（8分）
思路引導 VIP
遇到 B-tree 最大/最小節點與鍵值推導題，先確認 B-tree 的定義：Order m 代表每個節點最多 m 個子節點、m-1 個鍵值；除根節點外，內部節點最少有 ⌈m/2⌉ 個子節點、⌈m/2⌉-1 個鍵值。接著確立高度 h 的定義（通常假設根節點為第 1 層，樹葉為第 h 層），利用等比級數公式逐層累加，即可嚴謹求得答案。
B-tree 核心特性與結構
💡 透過限制分支度與強制葉節點齊平，確保搜尋效率的平衡多路搜尋樹。
- 分支度限制：根節點至少 2 個子節點，其餘內部節點至少 ⌈m/2⌉ 個。
- 鍵值數量規律：節點若有 k 個子節點，則包含 k-1 個遞增排序的鍵值。
- 完美平衡特性：所有葉節點必須位於同一階層，確保樹高維持在 O(log_m N)。
- 外部存取優化：設計目的為減少磁碟 I/O 次數，分支度越大，樹高越低。
