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 \(B^{+}\) 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:

A hash index has no ordering to fall back on, so it must record every key (dense), while a B+ tree used as a primary index on sorted data can skip most keys (sparse).

Answer 1

The Correct Option is A

Step 1: Understanding the Question.
We need to judge two statements about indexing in a DBMS: whether a hash index must be dense, and whether a \(B^{+}\) tree index can be sparse. Recall the definitions given: a dense index has one index entry for every distinct search-key value in the file, while a sparse index has entries for only some of the search-key values, typically one per data block, relying on the data file being sorted on that key.

Step 2: Analyze S1, "A hash index must be a dense index".
A hash index works by applying a hash function directly to a search-key value to compute the location (bucket) of the matching record. This only works if there is an index entry stored for that exact key value, because there is no ordering among keys that would let a lookup skip ahead from a nearby entry the way a sparse index does on a sorted file. If some key values had no entry, the hash function would have no bucket to point to for them, and lookups for those keys would fail. So a hash index must have an entry for every search-key value, which is exactly the definition of dense. S1 is true.

Step 3: Analyze S2, "A \(B^{+}\) tree index can be a sparse index".
A \(B^{+}\) tree index can be built as either a primary (clustering) index or a secondary (non-clustering) index. When it is a primary index on a file that is physically sorted by the search key, the leaf level of the \(B^{+}\) tree does not need an entry for every record, it only needs one entry per data block, since the data file's own sort order lets a search jump to a block and then scan forward to the exact record. This is a sparse organization. So yes, a \(B^{+}\) tree index can be sparse, even though it is dense when used as a secondary index. S2 is true.

Step 4: Analyze the options.

(A) Both S1 and S2 are true: Matches our analysis of both statements. Correct.

(B) Both S1 and S2 are false: Contradicts both findings above. Incorrect.

(C) S1 is true and S2 is false: S1 is indeed true, but S2 is also true, not false, since a \(B^{+}\) tree primary index can be sparse. Incorrect.

(D) S1 is false and S2 is true: S2 is indeed true, but S1 is also true, not false, since hashing needs an entry for every key. Incorrect.

Step 5: Final conclusion.
Both statements hold, so
\[ \boxed{\text{Both S1 and S2 are true}} \]