GATE CS 2026 Set 2 Q36 — File Organization and Indexing (B and B+ Trees)

Note: There is a minor typographical error in the question statement where the second statement is labeled as $\text{S1}$ instead of $\text{S2}$. We will treat the second statement as $\text{S2}$.

Let us analyze both statements based on database indexing principles:

Statement $\text{S1}$: A hash index must be a dense index

• A hash index uses a hash function to map a search-key value directly to a bucket address containing the record pointer(s).
• Because hashing does not preserve the physical or logical order of the keys, we cannot perform sequential scans to locate missing keys.
• To find any record using its search-key, the hash table must contain an entry for every single search-key value present in the database.
• Therefore, a hash index must be a dense index. Thus, $\text{S1}$ is true.

Statement $\text{S2}$: A $B^+$ tree index can be a sparse index

• A sparse index contains index entries for only some of the search-key values (typically one entry per data block/page). This requires the underlying data file to be physically sorted by the search-key.
• A $B^+$ tree can be designed as a sparse index (e.g., a sparse clustering index or primary index). In this setup, the leaf nodes of the $B^+$ tree store only the search-key of the first record of each data block.
• To find a record, we traverse the $B^+$ tree to find the largest index key less than or equal to the target key, and then scan that specific data block sequentially.
• Therefore, a $B^+$ tree index can be a sparse index. Thus, $\text{S2}$ is true.

Since both statements $\text{S1}$ and $\text{S2}$ are true, the correct option is A.