Physical Database Design - High-Performance Web Databases: Design, Development, and Deployment - page 337

Exhibit 21-4. Alternative heap file organizations.

keys. The most important search key is called the primary search key. The
remaining search keys of a table are called secondary search keys.

It is important that the DBA understands the basic mechanisms of the
three widely used file structures, as well as their strengths and weak-
nesses, so the database being designed will fit the needs of the users.

A heap file maintains an unsorted list of records in a file. Two
popular approaches for implementing the Employee table as a heap file are
illustrated in Exhibit 4. Heap files are implemented using a doubly linked
list of data pages, each containing one or more records. For simplicity pur-
poses, only the value of the EmpName search key is shown for each record.
A new record can be inserted into any data page that has room to store the
record, or a new data page can be inserted into the doubly linked list with
the new record stored in the data page.

Heap Files.

Alternatively, a directory contains pointers to every data page. A new
record is inserted into any data page that has room to store the record, or
a pointer to a new data page can be inserted into the directory with the new
record stored in the new data page.

Heap files are efficient when every record in a file must be accessed.
However, they are not efficient when retrieving a record with a specific