GATE CS 2024 Set 2 Q16 — File Organization and Indexing (B and B+ Trees)

A scan operation in a database retrieves all records from a relation. Let $B$ be the total number of data blocks (pages) containing these records, and $R$ be the total number of records ($R \gg B$).

Let's evaluate the efficiency of each file organization for a full scan:

• A. Sorted File: Records are packed densely and sequentially in physical blocks. Scanning the entire relation requires reading each of the $B$ blocks exactly once in sequential order. The total I/O cost is $B$, which is highly efficient.
• B. Heap File: Records are placed in no particular order but are packed densely into blocks. A scan requires reading each of the $B$ blocks exactly once. The total I/O cost is $B$, which is highly efficient.
• C. Unclustered Tree Index: In an unclustered index, the physical order of the data records does not match the order of the index search key. If we attempt to scan the relation by traversing the index leaf nodes and fetching the corresponding data records, consecutive index entries may point to different data blocks. In the worst case, this can require up to $R$ random disk I/Os (one for each record), which is extremely inefficient compared to $B$.
• D. Unclustered Hash Index: Similar to the unclustered tree index, scanning the relation using the hash index pointers is highly inefficient because it does not access data blocks sequentially, potentially resulting in up to $R$ random disk I/Os.

Thus, only Sorted and Heap file organizations are I/O efficient for the scan operation.