Indexing mechanisms are used to speed up access to desired data (e.g., an author catalog in a library).

• Search Key: an attribute (or set of attributes) used to look up records in a file.
• An index file consists of records called index entries of the form (search-key, pointer), and is typically much smaller than the original file.

Two basic kinds of indices:

• Ordered indices: search keys are stored in sorted order.
• Hash indices: search keys are distributed uniformly across buckets using a hash function.