民國106年 第2梯次 電腦軟體設計(JAVA)乙級 學科

第79題

下列有關分支度( O r d e r ) 為256 的B - t r e e 之描述,那些是正確的?

題目

下列有關分支度( O r d e r ) 為256 的B - t r e e 之描述,那些是正確的?

  1. (1) 當有1001000 筆紀錄存在一個分支度( O r d e r ) 為256 的B - t r e e 中,最壞之情形只須3 次存取( A c c e s s ) 就可拿到所要的一筆紀錄
  2. (2) 每個節點最多可放256 個鍵值( K e y )
  3. (3) 樹根節點至少存放128 個鍵值
  4. (4) B - t r e e 的高度只有在樹根( R o o t ) 分裂( S p l i t ) 時,才有可能增高

官方答案

(1) 當有1001000 筆紀錄存在一個分支度( O r d e r ) 為256 的B - t r e e 中,最壞之情形只須3 次存取( A c c e s s ) 就可拿到所要的一筆紀錄、(4) B - t r e e 的高度只有在樹根( R o o t ) 分裂( S p l i t ) 時,才有可能增高

解析

B-tree 階數 m=256，節點鍵值上限 255、下限 127（根節點除外），選項2「最多256個鍵值」與選項3「根節點至少128個鍵值」均錯誤。高度 h 滿足 N ≤ (m/2)^(h-1) * (m-1)；1,001,000 筆資料在 m=256 時高度最多 3，最壞存取 3 次（選項1正確）。B-tree 高度僅在根節點分裂時增加（選項4正確）。

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

官方資料