Which of the following file organizations is/are efficient for the scan operation in DBMS? A. Sorted B. Heap C. Unclustered tree index D. Unclustered hash index

GATE 2024 · Databases · Indexing · medium

Answer: A (Sorted) and B (Heap) are efficient for scan. C and D (unclustered indexes) are not.

1. Evaluate Sorted and Heap files: Sorted file: records are physically ordered, so a full scan reads each of the N_b data blocks exactly once in sequential order — efficient. Heap file: records are in insertion order, but a full scan still reads every data block exactly once — efficient. Both have scan cost = N_b (number of data blocks).
2. Evaluate Unclustered tree and hash indexes: Unclustered tree index: the B+ tree leaf entries point to records that may be on different pages in arbitrary order. Scanning all via the index can require one random block read per record — up to N_r block accesses where N_r >> N_b. Unclustered hash index: similarly, the hash chains point to records scattered across arbitrary data pages. A full-scan via hash index is even worse because hash does not preserve any order. Both are INEFFICIENT for full scan.