GATE CS 2007 Q63 — File Organization and Indexing (B and B+ Trees)

To find the order of the leaf node in the $B^+$-tree, we first understand its structure.

According to the definition given in the question, the order $p$ of a leaf node is the maximum number of (value, data record pointer) pairs it can hold. In addition to these pairs, a leaf node in a $B^+$-tree also contains a block pointer to point to the next leaf node (for sequential access).

Let:

• $p$ = Order of the leaf node (number of key-pointer pairs)
• $V$ = Size of the value (key) field = $9\text{ bytes}$
• $R$ = Size of the data record pointer = $7\text{ bytes}$
• $P$ = Size of the block pointer (next-leaf pointer) = $6\text{ bytes}$
• $B$ = Block size = $1\text{ KB} = 1024\text{ bytes}$

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

Substitute the given values into the inequality:

Since the order $p$ must be an integer, the maximum possible value of $p$ is $\lfloor 63.625 \rfloor = 63$.

Therefore, the order of the leaf node is 63.