Basic Concepts

1. An index for a file works like a catalogue in a library.
2. Cards in alphabetic order tell us where to find books by a particular author.
3. In real-world databases, indices like this might be too large to be efficient.
4. We'll look at more sophisticated indexing techniques, and at hashing techniques as an alternative.
5. Methods will be evaluated on:
   1. Access Time - time to find a particular data item.
   2. Insertion Time - time taken to insert a new data item (includes time to find the right place to insert).
   3. Deletion Time - time to delete an item (includes time taken to find item, as well as to update the index structure).
   4. Space Overhead - additional space occupied by an index structure.
6. We may have more than one index or hash function for a file. (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 file is called the search key (not to be confused with primary key, etc.).