1. An index for a file works like a catalogue in a library. Cards in alphabetic order tell us where to find books by a particular author.
2. In real-world databases, indices like this might be too large to be effcient. We'll look at more sophisticated indexing techniques.
3. There are two kinds of indices.

• Ordered indices: indices are based on a sorted ordering of the values.
• Hash indices: indices are based on the values being distributed uniformly across a range of buckets. The buckets to which a value is assigned is determined by a function, called a hash function.

4. We will consider several indexing techniques. No one technique is the best. Each technique is best suited for a particular database application.

5. Methods will be evaluated on:

(a) Access Types - types of access that are supported effciently, e.g., value-based search or range search.
(b) Access Time - time to nd a particular data item or set of items.
(c) Insertion Time-time taken to insert a new data item (includes time to nd the right place to insert).
(d) Deletion Time - time to delete an item (includes time taken to nd item, as well as to update the index structure).
(e) Space Overhead - additional space occupied by an index structure.

6. We may have more than one index or hash function for a le. (The library may have card catalogues by author, subject or title.)
7. The attribute or set of attributes used to look up records in a le is called the search key (not to be confused with primary key, etc.).