Indexing Flashcards
What is an index?
A data structure that allows for fast lookup for records in a file
Can an index allow records to be retrieved in sorted order?
Yes it can allow that
Describe a data file and and index file
Data File: the file that actually contains the records
Index File: The file that stores the index information
What is a Search Key
The set of attributes stored by the index to the find records in the data file
does the search key have to be unique?
NO it doesn’t, more than one record may have the same search key value
What is an index entry?
One index record that contains a search key value and pointer to the location of the record with that value
What is the difference between ordered and unordered files?
Ordered files are sorted on the search key, unordered files are not
Dense vs Sparse indexes
A dense index has an index entry for every record in the data file
A sparse index has index entries for only some of the data file records
Primary (clustering) indexes vs Secondary indexes
A primary index sorts the data file by its search key. The search key doesn’t have to be the same as the primary key
A 2NDary index doesn’t determine the organization of the data file
Single-Level vs Multi-Level indexes
Single-level indexes have only one index level
multi-level indexes have several levels of indexes on the SAME FILE
Formula for sparse index based on key?
log2(N)
