申論題

四、一個大型資料庫系統資料庫有 N 筆紀錄（data records），B⁺ - tree 是一個常用的索引 結構，而整個 B⁺ - tree 也存放在磁碟機中。B⁺ - tree 的一個節點（node）占一個區塊 （disk block）大小 b bytes，資料鍵值（key value）需 k bytes，區塊位址指標（block address pointer）p bytes，每筆紀錄位址指標（data record pointer）r bytes。

⑴試算內部節點的量級 m（branches 數 or order in internal node）、葉節點的量級 n （branches 數 or order in leaf node）及 B⁺ - tree 的高度 H。m，n 以 b，k，p，r 等符 號表示，H 以 N，m，n 等符號表示。（12 分）