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

Step 1: Recall the definitions. An index is dense if it has one index entry for every distinct search-key value that occurs in the data file. An index is sparse if it has index entries for only some of the search-key values (typically one entry per data block), relying on the data being physically sorted on that key so the remaining records can be found by scanning forward from the pointed-to block.

Step 2: Examine S1 - 'A hash index must be a dense index'. A hash index works by applying a hash function \(h(K)\) to a search key \(K\) to directly compute the bucket address where the corresponding record pointer is stored. Because the data file is not maintained in any sorted order with respect to the key (records with 'nearby' hash values are not physically near each other), there is no way to infer the location of a record from the location of another record. Every single search-key value that exists in the file must therefore have its own explicit entry in the hash structure, or that record could never be retrieved by the index. This means a hash index is inherently dense. So S1 is true.

Step 3: Examine S2 - 'A B+ tree index can be a sparse index'. A B+ tree index can be built as a primary index on a data file that is sequentially ordered (sorted) on the indexing attribute. In that case it is common and efficient to store only one index entry per block (usually pointing to the first/smallest key in that block) rather than one entry per record. When a search is performed, the tree is used to locate the correct block, and then the block is scanned sequentially to find the exact record. This is a valid sparse organization for a B+ tree primary index, so a B+ tree index can indeed be sparse. So S2 is true.

Step 4: Combine the results. Since S1 is true and S2 is true, both statements hold.

\[ \boxed{\text{Answer: (A) Both S1 and S2 are true}} \]