地特三等申論題
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 核心特性
💡 B-tree 是平衡多路搜尋樹，藉由嚴格分支度與葉節點齊平優化外部存取。
- 分支度限制：節點上限 m 個子節點，內部節點下限為向上取整的 m/2。
- 根節點規範：若非葉節點則至少 2 個子節點，不受內部節點下限限制。
- 鍵值與排序：節點含 k-1 個鍵值並依序排列，用以區隔 k 個子樹範圍。
- 完美平衡性：所有葉節點必須位於同一階層，確保搜尋路徑長度一致。
