Section 11: Indexing Structures
Question 1
1. Describe the primary difference between a dense and sparse index.
2. What is the advantage of the sparse over the dense index?
3. Can we apply a sparse index to an unorde
...
Section 11: Indexing Structures
Question 1
1. Describe the primary difference between a dense and sparse index.
2. What is the advantage of the sparse over the dense index?
3. Can we apply a sparse index to an unordered data file? Explain your answer.
Answer
1. A dense index maintains an index entry for every record in the data file.
A sparse entry maintains an index entry for only the anchor record (i.e. the
first record of every block) and not every record in the data file.
2. The sparse index indexes only the anchor records, it requires fewer index
entries to cover every record in the data file and so fewer disk block are
needed to use and maintain a sparse index. That is, during a search, fewer
disk read operations are needed to identify the data file block containing the
target record resulting in faster searches.
3. A sparse index cannot be utilized for an unordered data file. A sparse index
relies on the fact that the indexed attribute value is ascending across data file
blocks. That is, that the indexed attribute values on data file block i is less
than the records on block i+1 (assuming ascending order).
An unordered data file places records randomly across its blocks, and so
each unique index value (data record) requires a pointer to the record’s block
i.e. a dense index.
Question 2
Each of these questions refer to ordered data files.
1. Provide a short description of a data block’s “Anchor Record”.
2. What is the relationship between the anchor record and the other records on
same block?
3. What is the relationship between the anchor records on block i and block i+1?
4. In terms of anchor record values, what block might the record containing a
searched-for field value X be found?
Answer
1. The anchor record is the first record of a data file block. The record contains
the first indexing field value of the sequence of records stored on the data file
block.
2. The anchor record’s index field value should be ≤ the ordering attribute field
values of the other records on the same data block (assuming ascending
order).
[Show More]