GATE Overflow Test Series | Databases | Test 1 | Question: 29

Question

Consider a $B$-tree in which the search key is $20$ bytes long, block size is $1024$ bytes, data pointer is $10$ bytes and block pointer is $8$ Bytes. The maximum order of $B$-tree will be ________

Answer 1

In a $B$-tree of order $n$ every node will have $n-1$ <key, record pointer> pairs where the record pointers point to the corresponding records. In addition a node also has $n$ block pointers pointing to $n$ child blocks. The requirement of B-tree is that size of a node must not overflow the size of the disk block. Thus we have the equality

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

where, $n = $ Order of $B$-tree, $P_{b} = $ Block pointer size, $P_{r} = $ Record (or) Data pointer size, $k-$ search key size

$\implies n(8) + (n-1)(20 + 10) \leq 1024$

$\implies 8n + 30n - 30 \leq 1024$

$\implies 38n \leq 1054$

$\implies n \leq \dfrac{1054}{38}$

$\implies n \leq 27.73$

$\therefore$ The maximum order of $B$-tree $n = 27.$