Indices

Why Indexing?

Indexing speeds up access to desired data. An index stores key value pairs of a search-key and a pointer. These are typically much smaller than the original file.

Note that indicing itself brings an overhead. When an element is added or removed, the index table has to be updated as well.

Kinds of Indices

• Ordered Index: Search keys are stored in an ordered fashion, and parsed as such.
• Hash Indices: Search keys are distributed uniformly between buckets via a hash cunction.

Index Evaluation Metrics

• Access Time
• Insertion Time
• Deletion Time
• Space Overhead