GATE CS 2017 Set 2 Q49 — File Organization and Indexing (B and B+ Trees)

In a $B^+$ tree, the order ($p$) is defined as the maximum number of pointers an internal node can contain. An internal node with order $p$ contains at most $p$ block pointers and $p-1$ search keys.

To fit within a single disk block, the total size of these pointers and keys must not exceed the block size ($B$):

$$\text{Size of } p \text{ pointers} + \text{Size of } (p - 1) \text{ keys} \le \text{Block size}$$

Given:

• Block size ($B$) = $512$ bytes
• Search-key size ($V$) = $8$ bytes
• Pointer size ($P$) = $2$ bytes

Substituting these values into the inequality:

$$p \cdot P + (p - 1) \cdot V \le B$$

$$p \cdot 2 + (p - 1) \cdot 8 \le 512$$

$$2p + 8p - 8 \le 512$$

$$10p \le 520$$

$$p \le 52$$

Thus, the maximum order of the $B^+$ tree is 52.