Q243.
下列有關分支度(Order) 為256 的B-tree 之描述，那些是正確的？
電腦軟體設計共同科目 · 乙級 · Q243
難易度分析
4 / 5
此題為多選題，要求對 B-tree 的多項結構定義與運作機制進行全面判別。題目設計了關於鍵值上限與下限的細微差異，以及高度增長的特定條件，需精準區分根節點與一般內部節點的差異才能正確作答。
正確答案 (複選)：①, ④
- ① 當有1001000 筆紀錄存在一個分支度(Order) 為256 的B-tree 中，最壞之情形只須3 次存取(Access)就可拿到所要的一筆紀錄:B-tree 的高度計算：分支度為 256 的 B-tree，每層最多可容納 256^h 個節點。256² = 65,536，256³ = 16,777,216，大於 1,001,000 筆紀錄，故最壞情形下只需 3 次存取即可找到目標資料。
- ④ B-tree 的高度只有在樹根(Root)分裂(Split) 時，才有可能增高:B-tree 高度增長機制：B-tree 的插入操作中，只有當樹根節點發生分裂(Split)時，才會產生新的根節點，使樹的高度增加 1。其他層級的節點分裂僅在該層重新分配鍵值，不會改變樹的整體高度。
錯誤選項解析
- ② 每個節點最多可放256 個鍵值(Key):分支度(Order) 為 m 的 B-tree，每個節點最多可有 m 個子節點(Child Pointer)，但最多只能存放 m-1 個鍵值(Key)，即 255 個鍵值而非 256 個。此選項混淆了子節點數與鍵值數的上限。
- ③ 樹根節點至少存放128 個鍵值:樹根節點的鍵值下限與其他內部節點不同。根節點至少需有 1 個鍵值（除非樹僅有根節點且為空），而 ceil(m/2)-1 = 127 個鍵值下限僅適用於非根的內部節點，不適用於根節點。
Learning Tip
"B-tree 核心考點：(1) 分支度 m 定義的是子節點上限，鍵值上限為 m-1；(2) 根節點的鍵值下限（至少 1 個）與非根內部節點的下限（ceil(m/2)-1）不同，此為常見混淆點；(3) B-tree 高度僅在根分裂時增加，此特性確保樹保持平衡，是資料庫索引設計的關鍵優勢。"
學員答題分佈
①當有1001000 筆紀錄存在一個分支度(Order) 為256 的B-tree 中，最壞之情形只須3 次存取(Access)就可拿到所要的一筆紀錄0%
②每個節點最多可放256 個鍵值(Key)0%
③樹根節點至少存放128 個鍵值0%
④B-tree 的高度只有在樹根(Root)分裂(Split) 時，才有可能增高0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！