Prev  Next  Up  Contents

A Typical Problem

Consider the problem of locating a particular book in a library containing thousands of books. Public libraries long ago developed the card catalog as a means to efficiently locate a particular book. Usually there were at least three card catalogs, one with cards arranged in order by the name of the author, another arranged by the title of the book, and a third arranged by subject heading. Each card contained information about the book, most importantly its location in the library. Therefore, by knowing the name of the author, the title of the book, or the appropriate subject heading, you could use the card catalogs to quickly determine the location of a particular book. The card catalogs can be thought of as indexes.

Consider the author index. There is a filing cabinet containing a card for each book in the library, filed in alphabetical order by the author's name. Each drawer in the cabinet is labeled, perhaps "A-E", "F-J", and so on. There are two broad kinds of searches that you might want to perform on the author index.

First, you might want to make a list containing the name of every book in the library. To do this you would start in the first drawer with the first card, and look at each card in order until you reached the last card in the last drawer. This is called a "sequential" search because you look at each card in the catalog in sequential order.

Second, you might want to know the names of the books in the library that were written by Thomas Jefferson. Instead of examining every card in the catalog, you are first guided by the labels on the drawers to the second drawer, the "F-J" drawer. You are then guided by the tabs inside the drawer to the names that start with the letter "J". This is called a "random" search. For any particular card, you can use the labels (or indexes) to go almost directly to the desired card.

Actually locating the Thomas Jefferson card(s) involves both a random and sequential search. We use random access to go directly to the correct drawer and correct tab inside the drawer. The labels (or indexes) allow us to very quickly get close to the card of interest. After locating the "J" tab inside the "F-J" drawer, we then use sequential access to locate the particular Thomas Jefferson card(s) of interest.

Next Page
C/Database Toolchest Description
Product List