GATE CS 2020 Q54 — File Organization and Indexing (B and B+ Trees)

To find the minimum number of disk accesses required to retrieve any record, we need to minimize the height of the $B^+$ tree by assuming all nodes are filled to their maximum capacity.

1. Calculate the order of non-leaf nodes ($p$):

A non-leaf node of order $p$ contains at most $p$ pointers and $p-1$ keys. Given:

• Block size ($B$) = $4\text{ KB} = 4096\text{ bytes}$
• Key size ($K$) = $12\text{ bytes}$
• Pointer size ($P$) = $8\text{ bytes}$

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

$$p \cdot 8 + (p-1) \cdot 12 \le 4096$$

$$20p - 12 \le 4096 \implies 20p \le 4108 \implies p \le 205.4$$

Thus, the maximum order of a non-leaf node is $p = 205$.

2. Calculate the maximum capacity of leaf nodes ($d$):

A leaf node contains record pointers, keys, and one next-leaf pointer:

$$d \cdot (K + P) + P \le B$$

$$d \cdot (12 + 8) + 8 \le 4096$$

$$20d \le 4088 \implies d \le 204.4$$

Thus, the maximum number of records indexed per leaf node is $d = 204$.

3. Determine the minimum height of the $B^+$ tree:

The database has $10^6$ records.

• Number of leaf nodes: $\lceil 10^6 / 204 \rceil = 4902$ nodes
• Level 2 (parents of leaves): $\lceil 4902 / 205 \rceil = 24$ nodes
• Level 3 (Root): $\lceil 24 / 205 \rceil = 1$ node

The minimum height of the $B^+$ tree is $3$ levels.

4. Total Disk Accesses:

To retrieve a record, we must access:

1. $3$ disk blocks to traverse the $B^+$ tree (Root $\rightarrow$ Intermediate $\rightarrow$ Leaf).
2. $1$ disk block to fetch the actual data record.

Total disk accesses = $3 + 1 = 4$.