PHYSICAL DATABASE DESIGN - Fundamentals of Database Management Systems - page 207

FILE ORGANIZATIONS AND ACCESS METHODS
The Goal: Locating a Record
Depending on application requirements, we might want to retrieve the records of a
file on either a sequential or a direct-access basis. Disk devices can store records in
some logical sequence, if we wish, and can access records in the middle of a file.
But that's still not enough to accomplish direct access. Direct access requires the
combination of a direct access device and the proper accompanying software.
Say that a file consists of many thousands or even a few million records.
Further, say that there is a single record that you want to retrieve and you know the
value of its unique identifier, its key. The question is, how do you know where it
is on the disk? The disk device may be capable of going directly into the middle
of a file to pull out a record, but how does it know where that particular record is?
Remember, what we're trying to avoid is having it read through the file in sequence
until it finds the record being sought. It's not magic (nothing in a computer ever is)
and it is important to have a basic understanding of each of the steps in working with
simple files, including this step, before we talk about databases. This brings us to
the subject known as ''file organizations and access methods,'' which refers to how
we store the records of a file on the disk and how we retrieve them. We refer to the
way that we store the data for subsequent retrieval as the file organization .Theway
that we retrieve the data, based on it being stored in a particular file organization, is
called the access method . (Note in passing that the terms ''file organization'' and
''access method'' are often used synonymously, but this is technically incorrect.)
What we are primarily concerned with is how to achieve direct access to the
records of a file, since this is the predominant mode of file operation, today. In terms
of file organizations and access methods, there are basically two ways of achieving
direct access. One involves the use of a tool known as an '' index .'' The other is
based on a way of storing and retrieving records known as a '' hashing method .''
The idea is that if we know the value of a field of a record we want to retrieve, the
index or hashing method will pinpoint its location in the file and tell the hardware
mechanisms of the disk device where to find it.
The Index
The interesting thing about the concept of an index is that, while we are interested
in it as a tool for direct access to the records in files, the principle involved is exactly
the same as of the index in the back of a book. After all, a book is a storage medium
for information about some subject. And, in both books and files, we want to be able
to find some portion of the contents ''directly'' without having to scan sequentially
from the beginning of the topic or file until we find it. With a book, there are really
three choices for finding a particular portion of the contents. One is a sequential
scan of every page starting from the beginning of the book and continuing until the
desired content is found. The second is using the table of contents. The table of
contents in the front of the topic summarizes what is in the topic by major topics,
and it is written in the same order as the material in the topic. To use the table of
contents, you have to scan through it from the beginning and, because the items it
includes are summarized and written at a pretty high level, there is a good chance