高考申論題
114年
[資訊處理] 資料結構
第 一 題
一、一棵空的階數為 3 的 B-Tree（B-Tree of order 3）。由左而右依序插入下列鍵值（key value）：10, 80, 2, 9, 45, 62。請問插入完畢後，根節點中的鍵值有那些？請依序由小到大列出，用逗號分隔，並請說明樹節點的變化。（10 分）有一棵階數為 5 的 B-Tree（B-Tree of order 5），其高度（height）為 3，請問這棵樹中最多可以儲存多少個鍵值？(10 分)
📝 此題為申論題
思路引導 VIP
階數為 m 的 B-Tree，每個節點最多容納 m-1 個鍵值，超過時會以中間值向上提拔（Promote）並分裂（Split）節點。計算 B-Tree 的最大鍵值數量時，應考慮每個節點均達到最大鍵值數 m-1 且擁有最多子節點 m 的完美滿樹（Full Tree）狀態進行累加運算。
🤖
AI 詳解
AI 專屬家教
【解題思路】第一小題利用 2-3 樹（Order 3）的節點分裂規則逐步模擬插入；第二小題以完美滿樹的狀態逐層計算或代入公式求取最大鍵值數。 【詳解】 一、 階數為 3 的 B-Tree 插入推導與根節點鍵值
▼ 還有更多解析內容
B-Tree 插入與運算
💡 掌握 B-Tree 節點分裂機制及滿樹鍵值總數之計算公式。
🔗 B-Tree 節點分裂處理流程
- 1 插入鍵值 — 依序找到葉節點插入，若節點鍵值數達到 m 則觸發溢位
- 2 找出中位 — 將該節點內所有鍵值排序，取出中間位置的鍵值
- 3 向上提拔 — 將中位鍵值推入父節點；若無父節點則該值成為新根
- 4 完成分裂 — 原節點剩餘鍵值以中位值為界，拆分為左右兩個子節點
↓
↓
↓
🔄 延伸學習：延伸學習：若父節點也因提拔而溢位，則重複上述步驟進行連鎖分裂。
