Question

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

Answer 1

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

Order of leaf node is $\Rightarrow n^{\ast }(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$