Richland CollegeSCHOOL OF COSC 243611 Indexing Structures

Document Content and Description Below

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 spars... e 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]

Last updated: 1 year ago

Preview 1 out of 6 pages