GATE CS 1993 Q14 — File Organization and Indexing (B and B+ Trees)

To find the size of the data and index areas and the number of index levels, we perform the calculations step-by-step:

1. Data Area Calculation

• Record size ($R$): $64$ bytes
• Block size ($B$): $512$ bytes
• Number of records ($N$): $16\text{K} = 16 \times 1024 = 16,384$

The blocking factor for data blocks ($Bfr_d$) is:

The number of data blocks ($D$) required is:

2. Index Area Calculation

In an ISAM (indexed sequential) file, a sparse index is used where each entry points to a data block.

• Key size ($K$): $14$ bytes
• Block pointer size ($P$): $2$ bytes
• Index entry size ($R_i$): $K + P = 14 + 2 = 16$ bytes

The blocking factor for index blocks ($Bfr_i$) is:

3. Multi-level Index Construction

We construct the index levels bottom-up until we reach a single root block:

• Level 1: Points to the $2048$ data blocks. $$\text{Number of blocks at Level 1 } (I_1) = \left\lceil \frac{2048}{32} \right\rceil = 64 \text{ blocks}$$
• Level 2: Points to the $64$ blocks of Level 1. $$\text{Number of blocks at Level 2 } (I_2) = \left\lceil \frac{64}{32} \right\rceil = 2 \text{ blocks}$$
• Level 3 (Root): Points to the $2$ blocks of Level 2. $$\text{Number of blocks at Level 3 } (I_3) = \left\lceil \frac{2}{32} \right\rceil = 1 \text{ block}$$

Since Level 3 contains exactly $1$ block, it represents the root of the index tree.

Summary of Results

• Data Area: $2048$ blocks
• Index Area: $64 + 2 + 1 = 67$ blocks
• Number of index levels: $3$