Question:medium
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?
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?
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?
Show 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).
Updated On: Jul 22, 2026
- 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
Show Solution
The Correct Option is A
Solution and Explanation
Step 1: Pin down the two words first.
Dense means the index has a separate entry for every single key value in the file. Sparse means the index only has entries for some key values, usually one per block, and it only works when the data file itself is kept sorted on that key so a search can scan forward from the nearest entry.
Step 2: Think about how a hash index actually finds a record.
A hash index turns a key straight into a bucket address using a hash function. There is no nearby entry to fall back on, because hashed values are scattered with no order. So if the key you want has no entry, the hash index simply cannot find it. That forces every key to have its own entry, so hashing is always dense, statement S1 holds.
Step 3: Think about a $B^+$ tree used as the file's main (primary) index.
If the underlying data file is sorted by the search key, a $B^+$ tree does not need to record every key. It can record just the first key of each block, and once a search lands in the right block, a normal sequential scan inside that block finds the record. Fewer entries mean a smaller, faster index. This sparse setup only works for a primary index; a secondary $B^+$ tree index on an unsorted file would still need to be dense. So statement S2, which only claims a $B^+$ tree can be sparse, not that it always is, also holds.
Step 4: Put the two verdicts together.
S1 is true, S2 is true, so the correct choice is the one that marks both as true.
Step 5: Eliminate the rest quickly.
"Both false" ignores the reasoning entirely. "S1 true, S2 false" wrongly denies that a $B^+$ tree can ever be sparse. "S1 false, S2 true" wrongly claims hashing does not need to be dense, which breaks how hash lookups work.
\[ \boxed{\text{Both S1 and S2 are true}} \]
Dense means the index has a separate entry for every single key value in the file. Sparse means the index only has entries for some key values, usually one per block, and it only works when the data file itself is kept sorted on that key so a search can scan forward from the nearest entry.
Step 2: Think about how a hash index actually finds a record.
A hash index turns a key straight into a bucket address using a hash function. There is no nearby entry to fall back on, because hashed values are scattered with no order. So if the key you want has no entry, the hash index simply cannot find it. That forces every key to have its own entry, so hashing is always dense, statement S1 holds.
Step 3: Think about a $B^+$ tree used as the file's main (primary) index.
If the underlying data file is sorted by the search key, a $B^+$ tree does not need to record every key. It can record just the first key of each block, and once a search lands in the right block, a normal sequential scan inside that block finds the record. Fewer entries mean a smaller, faster index. This sparse setup only works for a primary index; a secondary $B^+$ tree index on an unsorted file would still need to be dense. So statement S2, which only claims a $B^+$ tree can be sparse, not that it always is, also holds.
Step 4: Put the two verdicts together.
S1 is true, S2 is true, so the correct choice is the one that marks both as true.
Step 5: Eliminate the rest quickly.
"Both false" ignores the reasoning entirely. "S1 true, S2 false" wrongly denies that a $B^+$ tree can ever be sparse. "S1 false, S2 true" wrongly claims hashing does not need to be dense, which breaks how hash lookups work.
\[ \boxed{\text{Both S1 and S2 are true}} \]
Was this answer helpful?
0
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems