GATE CS 2026 Set 2 Q.46: File Organization, B-Trees and B+ Trees Indexing

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?

Both S1 and S2 are true

Both S1 and S2 are false

S1 is true and S2 is false

S1 is false and S2 is true

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Analyze why a hash index requires an entry for every search key (dense) while a primary clustering B+ tree index can store one entry per disk block (sparse).

S1 is true: A sparse index relies on finding the largest key $\le K$ in sorted order and scanning sequentially within the data block. Because a hash function scatters search keys across buckets without preserving range order, a hash index cannot locate an unindexed key via range lookup and therefore must store an entry for every search-key value (dense).
S2 is true: When a data file is sorted on the search key (clustering/primary index), a $B^+$ tree can be built as a sparse index with one key-pointer entry per data block.

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 46 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source