Question

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?

• A. Both S1 and S2 are true
• B. Both S1 and S2 are false
• C. S1 is true and S2 is false
• D. S1 is false and S2 is true

Hint:

Ask whether the file has any usable physical order. Hash indexes scatter records randomly, so every key needs its own entry (dense). B+ tree indexes over sorted files can use one entry per block plus a sequential scan (sparse). Both facts hold, so option A is correct.

Answer 1

The Correct Option is A

Think of the difference between hash indexes and B+ tree indexes purely in terms of whether the underlying data has an exploitable order.

Checking S1: A hash index maps a key \(K\) to a bucket using \(h(K)\), scattering records across buckets with no notion of 'next' or 'previous' key. If even one key value were left out of the hash structure, that record would become permanently unreachable through the index, because you cannot infer its bucket from a neighboring entry the way you can with sorted data. This forces hash indexes to always list every key that exists in the file - that is exactly the definition of a dense index. Hence S1 holds.

Checking S2: A B+ tree, unlike a hash index, is built over data and is often paired with a file that is physically sorted on the search key (a primary index scenario). Because consecutive records are stored together in the same or adjacent blocks, you do not need an index entry for each record - one entry per block (pointing to the smallest key of that block) is enough. The search narrows down to a block via the tree, and then a short sequential scan within that block finds the target record. This block-level economy is precisely what makes a sparse index possible, and it is achievable with a B+ tree. Hence S2 also holds.

Since neither statement is refuted, the pair S1 and S2 are simultaneously valid, giving option (A) as correct: \(\text{Both S1 and S2 are true}\).