Question

Consider a block size 512 bytes, search key field 9 bytes long, block pointer size is 6 byte and record pointer is 7 byte long. if a level 3 B+ tree is constructed considering root as level 0, find the maximum number of entries in the B+ tree ?

• A. $(34{)}^3\ast (31{)}^2$ entries
• B. $(34{)}^2\ast 31$ entries
• C. $(34{)}^3\ast 31$ entries
• D. $(31{)}^3\ast 34$ entries

Answer 1

The correct option is C $(34{)}^3\ast 31$ entries

option (a)

Order of internal node is
$\Rightarrow$ n*6 + (n-1) * 9$\le$512
$\Rightarrow$ 6n+9n - 9 $\le$ 512
$\Rightarrow$ 15n $\le$ 521
n $\le$ 34

Order of leaf node is
$\Rightarrow$n* (9+7) +6$\le$512
$\Rightarrow$ 16n $\le$ 506
$\Rightarrow$ n $\le$ 31

maximum number of entries in level 3 B + tree is

= $(34{)}^3\ast 31$