Overview

The concept of indexing for dictionaries, encyclopedias, book manuscripts, catalogs, and address lists has been around for centuries. Methods like tabs in a book volume or lists of index terms at the back of the book are used very effectively. When a computer needs to find data within a relational database it has exactly the same need. How can a small amout of data be found from within a very large set without looking very carefully through the entire thing catalog. For example, consider how inefficient life would be if every time you walked over to an ATM machine to withdraw money the bank s computer performed a linear search through possibly millions of customer records until it found the entry matching your bank account number. Large electronic files and databases have accelerated the need for indexing methods that can access a subset of the data quickly. In some cases the data is very small and can be accessed in a single input/output (I/O) operation.

In other cases data needs to be accessed in bulk and looked over by an analyst to determine which data is relevant to the current need. In the late 1970s, indexing for the earliest relational, hierarchical (like IMS), and CODASYL databases was done in a wide variety of ways: sequential, indexed sequential, hashing, binary search trees, B-trees, TRIE structures, multilist files, inverted...