一、一棵空的階數為 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 分)

一、對於階數為 3 的 B-Tree（order 3，表示每個節點最多 2 個鍵值、最少度數 t=2），依序插入鍵值 10, 80, 2, 9, 45, 62 的過程如下：

- 插入10、80、2、9後，根節點因為滿了（2 個鍵值達上限），會分裂形成兩個子節點和一個新根節點，根節點中的鍵值為 9。
- 持續插入45、62後，根節點會再次分裂，但在此案例中根節點最後的鍵值為 （由小到大排序）。

故插入完畢後，根節點的鍵值為 **2, 9**。

關於樹節點變化，插入過程中會依序調整、分裂節點，使樹保持平衡，並確保每個非根節點的鍵值數在 t-1 到 2t-1 範圍內。

***

二、對於階數為 5 的 B-Tree（order 5，每個節點最多 4 個鍵值），高度為 3 的最大鍵值數量計算：

- 每層節點數分別為：
- 層 0（根節點）：1 個節點
- 層 1：5 個節點
- 層 2：25 個節點
- 層 3：125 個節點
- 總節點數 = 1 + 5 + 25 + 125 = 156 個
- 每個節點最大鍵值數為 4 個
- 最大鍵值數 = 156 × 4 = **624 個**

因此，該高度和階數的 B-Tree 最高可以儲存 624 個鍵值。

來源