Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?
- (A)
Sorted
- (B)
Heap
- (C)
Unclustered tree index
- (D)
Unclustered hash index
Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?
Sorted
Heap
Unclustered tree index
Unclustered hash index
ANSWER
The correct options are (A) Sorted and (B) Heap.
Official answer: A, BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)
A full scan reads every record of the file, so its I/O cost is the number of pages that hold the data. An organization is efficient for a scan when it stores the records densely and lets the pages be read one after another.
Heap file: records are packed into pages with no gaps. A scan costs about page reads, where is the number of data pages, and the reads are sequential. This is efficient.
Sorted file: the records are also stored densely, in key order, so a full scan again costs about sequential page reads. The sort order does not hurt a scan. This is efficient.
Unclustered tree index: the leaf entries are in key order, but the data records are scattered across pages. Scanning in index order needs about one page read per record, so about random reads, where is the number of records. Since is much larger than , this is inefficient.
Unclustered hash index: the buckets are not in key order and each entry points to a record on an arbitrary page. A scan again costs about one page read per record, plus the index overhead. This is inefficient.
So only the sorted file (A) and the heap file (B) are I/O efficient for a scan.
KEY IDEA
A scan costs the number of data pages, so it is cheap only when the records are packed densely in the file itself (heap or sorted). An unclustered index leaves the records scattered, so a scan through it costs about one read per record.
WATCH OUT FOR
Thinking an index always helps. An unclustered index helps a search on one key, but it makes a full scan cost about one page read per record instead of sequential page reads.
From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes