Indexing Flashcards
search key
attribute (or set of attributes) that are used to look up
records in a file
index entry
consists of the pair (search-key, pointer to data with the value stored in the search key)
index file
the file that consists of records of index entries
access types
the types of access that are supported efficiently
access time
the time it takes to find a particular data item
insertion time
the time it takes to insert a new data item
deletion time
the time it takes to delete a data item
ordered indices
based on a sorted ordering of the values
hash indices
based on a uniform distribution of values across a range
of buckets using a hash function
clustering index (primary index)
the index whose
search key also defines the sequential order of the file
non-clustering index (secondary index)
the index whose search key specifies an order different from the sequential order of the file (must be dense)
dense index
one index record appears for every search-
key value
- faster to locate a record
- takes more space
sparse index
an index entry appears for only some of the
search-key values (locate data by finding the index entry with the largest search-key value that is less than or equal to the
search-key value we are looking for and scanning from there)
- slower to locate a record
- takes less space
