看板Examination
請教
49.
某一DBMS使用B + tree結構存放其索引,該DBMS每一個硬碟頁佔4KByte,節點內的每個索
引值(欄位值)佔20 Byte,指向資料的記錄指標佔10 Byte,指向索引節點的節點指標佔8
Byte,每一節點(根節點除外)至少佔硬碟頁50%滿,請問這個B + tree中,每個葉節點最
多有幾個記錄指標?
1) 136 2) 68 3) 147 4)74
此題答案為 (20+10)X+ 8 <=4K X<=136 ; X>=68
Ans: 1)
50.承上題,若有50萬筆記錄,最多需要幾層B + tree即可完全存放?
1) 3 2) 5 3) 7 4) 9
節點: 8Y+20(Y-1) <=4K Y<=147; Y>=74
題目指最多需要幾層,所以用使用率(50%)最低的值去計算
=> 74^n*68 >=500000 ; n>=3
所以總共是3(中間節點)+1(葉節點)層,這答案是應該為4層嘛??
請問各位前輩,答案為1) 3層,該如何解釋,謝謝
--
◆ From: 124.8.228.92
※ 批踢踢實業坊(ptt.cc)※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1384097500.A.900.html
推 leo2:這題我也覺得很怪,硬要解釋的話 11/11 00:40
→ leo2:1: root算第0層 11/11 00:40
→ leo2:2: root用全滿狀態下去算 11/11 00:41
→ studentyien:74^n*68 >=500000 用小算盤按n>=1.869... 11/11 08:49
→ studentyien:抱歉,沒按完,算到log74了 11/11 08:54
→ studentyien:不過算完後n>=2.068...考場中若用估計值算可能會小於2 11/11 09:14