A relation is stored as a data file sorted on attribute ; the file is not sorted on . A sparse index has entries for only some search-key values (for example, one entry per data block), and a lookup for a key that has no entry uses the entry with the largest indexed key not greater than it.
Which one of the following indexes on this file can be sparse?
Show solution
Solution MCQ · 1 mark · −⅓ if wrong
Answer: (A) A B+ tree index on A
Method. A sparse index works only if, after jumping to the nearest smaller indexed key, the target record is guaranteed to be close by. That needs two things: the data file is physically ordered on the search key, and the index itself is ordered so "the largest key not greater than " can be found.
- B+ tree on : the file is sorted on and a B+ tree is ordered. Sparse works.
- B+ tree on : the file is not sorted on , so records with nearby values are scattered. Dense needed.
- Hash index on or : hashing scatters keys, so there is no "nearest smaller key" to fall back on. Dense needed.
The trap. It is easy to think "the file is sorted on , so any index on can be sparse" and pick the hash index on . Sparse needs order in both the file and the index structure.
What was tested. Dense versus sparse indexes and why sparseness requires a clustering (primary) ordered index.
Copied. Paste it into the new chat.Too long to send. Copy the question and solution by hand.