The GATE Grind

GATE 2026 CS (CS2) – Question 46

Databases · File Organization and Indexing (B and B+ Trees) · 2 marks · Multiple choice

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 $B^{+}$-tree index can be a sparse index.

Which one of the following options is correct?

  1. Both $S1$ and $S2$ are true
  2. Both $S1$ and $S2$ are false
  3. $S1$ is true and $S2$ is false
  4. $S1$ is false and $S2$ is true

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Both $S1$ and $S2$ are true

Explanation

A hash index must be dense because a search-key value is located through a direct entry in the hash structure. A $B^{+}$-tree index can be sparse, for example when it is a clustered index with entries only for blocks or ranges. Therefore, both $S1$ and $S2$ are true, so option (A) is correct.