有一分支度(order)為256 之B-tree,將10 萬筆記錄存入此B-tree 中,其高度之最小值為下列何 者?

題目

有一分支度(order)為256 之B-tree,將10 萬筆記錄存入此B-tree 中,其高度之最小值為下列何 者?

1. (1) 3
2. (2) 4
3. (3) 5
4. (4) 2

官方答案

(1) 3

解析

B-tree 階數 m=256，每節點最多 255 個鍵值，最多 256 個子節點。高度 h 最小時樹最飽滿，最大節點數 ≈ (m^(h+1)-1)/(m-1)。h=2 時最大鍵值數 256^3-1 ≈ 1.67 億 > 10 萬，h=1 時最大 256^2-1=65535 < 10 萬，故最小高度為 2（層數為3，若題目定義高度為層數則為3）。依台灣考題慣例高度常指層數，答案為 3。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF