Databases Reference
In-Depth Information
2
Basic Indexing Methods
If you don't find it in the index, look very carefully
through the entire catalogue.
—Sears, Roebuck, and Co.,
Consumer's Guide
, 1897
he concept of indexing for dictionaries, encyclopedias, book manuscripts, catalogs,
and address lists has been around for centuries. Methods like tabs in a topic volume
or lists of index terms at the back of the topic are used very effectively. When a com-
puter 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 sub-
set of the data quickly. In some cases the data is very small and can be accessed in a sin-
gle 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 files, and doubly chained trees to name a few.
Many options were allowed for programmers to choose from, and the choice of the best
T
15
