For secondary key processing which of the following file organizations is preferred? Give a one line justification. A. Indexed sequential file organization B. Two-way linked list C. Inverted file organization D. Sequential file organization

GATE 1989 · Databases · Indexing · medium

Answer: C. Inverted file organization — it directly maps secondary key values to record pointers, enabling efficient secondary key queries without full file scans.

1. Analyze indexed sequential file for secondary key: An indexed sequential file is organized by primary key and has an index on the primary key. For secondary key queries, there is no direct index — the entire file must be scanned. This is O(n) and inefficient for secondary key processing.
2. Analyze inverted file organization: An inverted file maintains a separate inverted index for each secondary attribute. Each entry in the inverted index contains a secondary key value and a list of pointers to all records with that value. A secondary key query (e.g., Dept=HR) directly looks up the inverted index to get all matching record addresses in O(log n + output_size) time — no full scan needed.
3. Compare remaining options: Sequential file: requires full scan O(n) for secondary key query — worst choice. Two-way linked list: allows forward/backward traversal but provides no faster access by secondary key value — still O(n) in the worst case. Inverted file: provides O(log n) lookup via the index + direct pointer-based access to matching records. This is clearly the best choice for secondary key processing.