IAE Academy

GATE 2026 CS2 Q.46: solution and answer

GATE 2026 · CS2Q.46 · 2 marks · MCQ

An index in a DBMS is said to be dense if an index entry appears for every search-key value in the indexed file. Otherwise it is called a sparse index. Consider the following two statements.

S1: A hash index must be a dense index

S2: A tree index can be a sparse index

Which one of the following options is correct?

  1. (A)

    Both S1 and S2 are true

  2. (B)

    Both S1 and S2 are false

  3. (C)

    S1 is true and S2 is false

  4. (D)

    S1 is false and S2 is true

See the question in the paper

Answer and solution

ANSWER

Option (A): both S1 and S2 are true.

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. A sparse index keeps entries for only some search-key values, usually one per data block of a file stored in search-key order. To search, find the largest index entry not exceeding the key, then scan forward in the sorted file from there.

  2. S1: A hash index maps a key to a bucket through the hash function. Hashing keeps no order, so a key value with no entry of its own cannot be reached by scanning forward from a neighbouring entry. Every search-key value therefore needs its own entry, so a hash index must be dense. S1 is true.

  3. S2: A tree index can be built as a sparse (clustering) index over a file stored in search-key order. Its leaf level then holds one entry per data block instead of one per key value. A search follows the tree to the right block and scans within it. Such an index is sparse, so S2 is true.

  4. Both statements are true, so the answer is option (A).

KEY IDEA

A sparse index needs the data file sorted on the search key, so that it can scan forward from the nearest smaller entry. A hash index has no such order, so it must be dense. A B+ tree index over a sorted file can be sparse, with one leaf entry per block.

WATCH OUT FOR

Taking "B+ tree index" to mean "always dense", which forgets that a clustering B+ tree over a sorted file can be sparse. The opposite slip is believing a hash index can be sparse.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes

More Indexing questions