Skip to content
GATETECH
Official PYQ · 2015Set 3 · Q46File Organization and Indexing (B and B+ Trees)NAT1 mark

GATE CS 2015 Set 3 Q46 — File Organization and Indexing (B and B+ Trees)

Explain with AI
Consider a B+B^+ tree in which the search key is 1212 bytes\text{bytes} long, block size is 10241024 bytes\text{bytes}, record pointer is 1010 bytes\text{bytes} long and the block pointer is 88 bytes\text{bytes} long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is ______.
View worked solution

Answer: 50

In a B+B^+ tree, a non-leaf (internal) node of order pp contains at most pp block pointers and p−1p - 1 search keys.

Let:

  • BB = Block size = 10241024 bytes
  • KK = Search key size = 1212 bytes
  • PP = Block pointer size = 88 bytes
  • pp = Maximum number of block pointers (order of the non-leaf node)

The total space occupied by a non-leaf node must not exceed the block size:

Size of non-leaf node=(p×P)+((p−1)×K)≤B\text{Size of non-leaf node} = (p \times P) + ((p - 1) \times K) \le B

Substitute the given values into the inequality:

(p×8)+((p−1)×12)≤1024(p \times 8) + ((p - 1) \times 12) \le 1024 8p+12p−12≤10248p + 12p - 12 \le 1024 20p≤103620p \le 1036 p≤⌊51.8⌋=51p \le \lfloor 51.8 \rfloor = 51

Thus, the maximum number of block pointers pp is 5151.

The maximum number of keys that can be accommodated in a non-leaf node is:

Maximum keys=p−1=51−1=50\text{Maximum keys} = p - 1 = 51 - 1 = 50

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore File Organization and Indexing (B and B+ Trees) questions