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

Exhibit 21-5. Alternative sorted file organizations.

value for the search key or retrieving records within a specific range of val-
ues for the search key. This inefficiency occurs because files must be
scanned sequentially to locate any specific value or specific range of val-
ues. On the average, half of the records in a heap file must be accessed to
locate a specific record.

A sorted file maintains a list of records sorted by the values
of the primary search key. The two approaches for implementing the
Employee table with primary search key EmpName as a sorted file are pre-
sented in Exhibit 5. Again, for simplicity, only the value of the EmpName
search key is shown for each record. When using the doubly linked list of
data pages, a new record must be inserted into the appropriate data page so
the sorted order of records is maintained. Alternatively, an index may con-
tain pointers to every data page. Again, a new record is inserted into the
appropriate data page so the sorted order of records is maintained. If there
is no space for a new record in the existing data page, a new data page is cre-
ated and linked into the appropriate position within the doubly linked list.

Sorted Files.

Sorted files are efficient when:

1. Records need to be accessed in the sequence of the search key. For
example, if the Employee file is sorted by EmpName, then the sorted
file would be efficient for the representative Query 6.