GATE CSE 2024 | Set 2 | Question: 16

Question

​​​​​Which of the following file organizations is/are $\text{I/O}$ efficient for the scan operation in $\text{DBMS}$?

• A. Sorted
• B. Heap
• C. Unclustered tree index
• D. Unclustered hash index

Comments

@yashakacid Retrieving all pages/blocks of a File

---

Do we need to learn this table? For future exams? (Linked by Deepak sir)

---

Do we have to?

 

Answer 1

• A sorted file organization ensures that records are stored in a sequential order, which is optimal for scan operations since the data can be accessed sequentially with minimal I/O overhead.
• In a heap file organization, records are stored without any specific order. Although not as efficient as sorted files, a heap file still allows sequential scans across all records with moderate I/O efficiency.
• Options C (Unclustered tree index) and D (Unclustered hash index) are not I/O efficient for scans because they involve random access to data blocks, leading to higher I/O costs.
• Hence, the correct answer is A and B.

If you liked this answer, please consider upvoting it.

Comments

@nagarajupamanji43 How sorted file will be efficient for scan operation compared to heap file? In scan operationm, we need to retrieve all the blocks of a file. I/O cost will be same for both heap and sorted file.

Answer 2

A scan operation reads all records in a relation, and its I/O cost is minimized when data pages can be read sequentially from disk. Random I/O caused by non-contiguous record placement dramatically increases access time.

Consider the relation  
$$
\texttt{Employee}(\underline{\texttt{ID}}, \texttt{Name}, \texttt{Dept})
$$  
with the following instance:

$$
\begin{array}{|c|c|c|}
\hline
\texttt{ID} & \texttt{Name} & \texttt{Dept} \\
\hline
103 & \text{Alice} & \text{HR} \\
101 & \text{Bob} & \text{Engineering} \\
104 & \text{Charlie} & \text{HR} \\
102 & \text{Dana} & \text{Engineering} \\
\hline
\end{array}
$$

Assume each disk page holds two records.

Sorted File Organization (Option A):  
Records are stored physically in sorted order by a key (e.g., $\texttt{ID}$). The disk layout becomes:

• Page 1: $(101, \text{Bob}, \text{Engineering})$, $(102, \text{Dana}, \text{Engineering})$  
• Page 2: $(103, \text{Alice}, \text{HR})$, $(104, \text{Charlie}, \text{HR})$

A full scan reads Page 1 followed by Page 2 in sequential order, requiring no disk seeks between records. This yields optimal sequential I/O performance.

Heap File Organization (Option B):  
Records are stored in insertion order, with no sorting. The disk layout is:

• Page 1: $(103, \text{Alice}, \text{HR})$, $(101, \text{Bob}, \text{Engineering})$  
• Page 2: $(104, \text{Charlie}, \text{HR})$, $(102, \text{Dana}, \text{Engineering})$

Although unordered, all records reside in contiguous pages filled sequentially. A scan reads Page 1 then Page 2 without random seeks, making it highly I/O efficient for full scans.

Unclustered Tree Index (Option C):  
The index (e.g., a B⁺-tree on $\texttt{ID}$) is sorted, but data records remain in arbitrary physical locations. Leaf entries store pointers to record addresses. To retrieve all records via the index, the system must follow pointers in sorted key order, which typically results in non-sequential page accesses (e.g., accessing Page 1, then Page 2, then Page 1 again). This incurs costly random I/O and is inefficient for scans.

Unclustered Hash Index (Option D): 
A hash index on an attribute (e.g., $\texttt{Dept}$) maps values to buckets containing pointers to scattered records. A full scan requires visiting all buckets and dereferencing each pointer, leading to unpredictable, random disk accesses. This is the least efficient for scan operations.

In summary, only Sorted and Heap organizations store records in a manner that enables pure sequential I/O during a full scan.

$$
\boxed{\text{A. Sorted ,B. Heap}}
$$

Comments

Thank you. Any resourse to refer this topic?

---

DBMS Ramakrishnan chapter 8.
Few more Resources:
https://pages.cs.wisc.edu/~dbbook/openAccess/thirdEdition/slides/slides3ed-english/Ch8_Storage_Indexing_Overview.pdf

https://www.iitg.ac.in/awekar/teaching/cs344fall11/lecturenotes/october%2010.pdf

 

Answer 3

In sorted file organization, records are arranged in a sequential order. This arrangement is highly efficient for scan operations because it allows the data to be accessed in sequence, minimizing I/O overhead.

In contrast, heap file organization stores records in an unordered manner. While it’s less efficient than sorted files, it still allows for sequential scanning with moderate I/O efficiency.

On the other hand, unclustered tree indexes (Option C) and unclustered hash indexes (Option D) are not as I/O efficient for scans. This is because these structures require random access to data blocks, resulting in higher I/O costs due to more complex access patterns.

Thus, the correct answer is A (sorted file organization) and B (heap file organization), as they are more optimal for scan operations

 

If you liked this answer, please consider upvoting it.

Answer 4

Please refer "Database Management Systems by Raghu Ramakrishnan" - Chapter 8

Table with more clarity :

---

Scan column → Cost of reading entire file
Equality column → Cost of = selection
Range column → Cost of range selection
Insert column → Cost to insert one record
Delete column → Cost to locate + remove record

---

B = Number of data pages (blocks) required to store the file when records are packed with no wasted space

R = Number of records per data page (records per block)

D = Average disk I/O time to read or write one data page

C = Average CPU time to process one record (e.g., compare a field with a constant)

H = Time required to apply the hash function to one record

F = Fan-out of a tree index (number of pointers per index node, typically ≥ 100)

---

Heap Files

BD = Cost of scanning all B data pages (full file scan cost)

0.5BD = Average cost of equality search in an unsorted heap file (half the file scanned on average)

---

Sorted Files

log2(B) = Height of binary search over sorted data pages

D log2(B) = Disk I/O cost of binary search on sorted file

---

Clustered Files

logF(B) = Height of a B+ tree index with fan-out F and B data pages

D logF(B) = Disk I/O cost to traverse a B+ tree index

#matches = Number of records that satisfy the selection condition

1. In clustered files, data pages are not fully packed.

2. Empirical studies show average page occupancy is about 67%.

3. Because of this, more physical pages are needed to store the same data.

4. Effective number of data pages ≈ 1.5 × B (where B is the ideal number of pages).

5. This 1.5B assumption is used in cost analysis.

6. Full file scan must read all data pages.

7. Therefore, scan cost = 1.5B × (D + RC).

8. This scan cost is similar to sorted files, but higher due to extra pages.

---

Search = Cost to locate the record position (depends on file organization or index)

Search + D = Search cost plus one data page access

Search + BD = Search cost plus shifting/reorganization of B data pages

Search + 2D = Search cost plus two data page accesses

1.5BD = Scan cost for clustered index (due to partial page overlap and ordering)

0.15B = Approximate number of index pages (15% of data pages, rule of thumb)

BD(R + 0.15) = Full scan cost including data pages and index pages

---

Heap File with Unclustered Tree Index

D(1 + logF(0.15B)) = One data page access plus index traversal cost

D(3 + logF(0.15B)) = Insert cost including index traversal and multiple page updates

2D = Cost of equality search using unclustered hash index (hash bucket + data page)

4D = Insert cost in unclustered hash index (bucket + overflow + data page updates)

1. We consider a heap file with an unclustered B+ tree index.

2. Each index data entry is assumed to be about 1/10th the size of a data record (a typical assumption).

3. Index pages are assumed to be about 67% full.

4. Because of entry size and page occupancy, the number of index leaf pages is about 0.15 × B, where B is the number of data pages.

5. Each index leaf page contains about 6.7 × R data entries (R = records per data page).

6. To scan using an unclustered index, we first scan all index leaf pages to get record pointers.

7. This index scan costs roughly 0.15B I/Os.

8. Now comes the expensive part: for each index entry, we must fetch the actual data record.

9. Since the index is unclustered, each record may lie on a different data page.

10. Therefore, fetching data records costs about 1 I/O per record.

11. Total cost of fetching records becomes approximately B × R I/Os, which is extremely high.

12. Hence, using an unclustered index for a full scan is inefficient.

13. If sorted output is needed, it is better to ignore the index and scan the data file directly.

14. Sorting the data file can be done using a two-pass external sort.

15. Two-pass sorting requires reading and writing the entire file twice.

16. So, the I/O cost of sorting a file with B pages is about 4B.

17. This cost (4B) is much smaller than the cost of scanning using an unclustered index.

18. Rule of thumb: never use an unclustered index for full scan or sorted retrieval.

Answer 5

A. Sorted

• Full scan → read pages sequentially → I/O = N

• Range query → faster

•  For scan specifically → I/O same as heap

B. Heap

• Full scan → read pages sequentially → I/O = N

• No advantage beyond simplicity

•  For scan → same as sorted

So for a full scan, both are equally efficient.

C. Unclustered tree index

Index → page7  
Index → page22  
Index → page3  
Index → page40 

 

This causes random seeks → VERY expensive.

D. Unclustered hash index

Hash distributes records randomly into buckets → again RANDOM I/O.

Comments

So for a full scan, both are equally efficient.

What about the overhead of enumerating the heap itself ?
That should cause some extra seek making it less efficient than "Sorted" ?

Answer 6

a &b

Comments

damn best explanation on gateovf yet !!!