GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 11

Question

Consider a $B^{+}$- tree in which the search key is $24\;\text{bytes}$ long, block size is $2048 \;\text{bytes}$, recorder pointer is $20\;\text{bytes}$ long and the block pointer is $16\;\text{bytes}$ long. If the maximum number of keys that can be accommodated in each leaf node is $’a’$ and that in each internal node (non-leaf) is $'b',$ the value of $b - a$ is ________

Answer 1

$\textbf{For Non-leaf node(Internal node):}$

$(n+1)(P_{b}) + n.k \leq \text{Block Size}$

Where, $n = $ maximum number of stored keys, $P_{b} = $ Block pointer size

$\implies (n+1)16 + n(24) \leq 2048$

$\implies 16n + 24n +16 \leq 2048$

$\implies 40n \leq 2032$

$\implies n \leq 50.8$

$\therefore$ Maximum number of keys in an internal node (non-leaf) $b = 50.$

$\textbf{For leaf node:}$

$m(k + P_{r}) + P_{b} \leq \text{Block Size}$

Where, $m = $ number of keys, $P_{b} = $ Block pointer size, $P_{r} = $ Record (or) Data pointer size (Unlike in a $B-$ tree, in a $B^+-$tree only the leaf nodes have record pointers).

$\implies m(24 + 20) + 16 \leq 2048$

$\implies 44m \leq 2032$

$\implies m \leq 46.18$

$\therefore$ Maximum number of keys in a leaf node, $a = 46.$

Now, the value of $ b-a = 50 - 46 = 4.$