Index structure basics in file/DB systems: An index typically consists of which of the following elements?

Introduction / Context: Indexes speed up data retrieval by maintaining a compact, searchable structure separate from the base data. Understanding what an index stores helps clarify how lookups translate to locating the actual record in the master file or table.

Given Data / Assumptions:

• We consider classic index organization (e.g., B-tree-like structures).
• “Master list” represents the base file or table containing full records.
• Index entries must map search keys to record locations.

Concept / Approach: An index is a data structure that stores keys (values on which you search/sort) and pointers (references) to the corresponding records or to lower-level index pages. This allows logarithmic-time searches and ordered traversals, avoiding full scans of the master data.

Step-by-Step Solution: Identify index content: keys plus references to data/pages.Relate pointers to record identifiers (RIDs) or page numbers in DBMS terms.Conclude that both keys and pointers are essential components.Choose “both (a) and (b).”

Verification / Alternative check: B-tree/B+-tree descriptions show that each entry pairs a key with a pointer (to child node or to data), confirming the dual structure.

Why Other Options Are Wrong: Keys only: without pointers, keys cannot lead you to data.

Pointers only: without keys, you cannot search efficiently.

All of the above / None: do not add value beyond the correct combined option.

Common Pitfalls: Confusing clustered storage (where data pages are ordered by key) with the index itself; even clustered indexes still maintain key-pointer relationships.

Final Answer: both (a) and (b)