Java Reference
In-Depth Information
In−memory
Table of
Cylinder Keys
Cylinder 1
Cylinder 2
Cylinder
Index
Cylinder
Index
Records
Records
Cylinder
Cylinder
Overflow
Overflow
System
Overflow
Figure10.6
Illustration of the ISAM indexing system.
among a number of cylinders on disk.
1
Each cylinder holds a section of the list in
sorted order. Initially, each cylinder is not filled to capacity, and the extra space is
set aside in the cylinder overflow. In memory is a table listing the lowest key value
stored in each cylinder of the file. Each cylinder contains a table listing the lowest
key value for each block in that cylinder, called the cylinder index. When new
records are inserted, they are placed in the correct cylinder's overflow area (in ef-
fect, a cylinder acts as a bucket). If a cylinder's overflow area fills completely, then
a system-wide overflow area is used. Search proceeds by determining the proper
cylinder from the system-wide table kept in main memory. The cylinder's block
table is brought in from disk and consulted to determine the correct block. If the
record is found in that block, then the search is complete. Otherwise, the cylin-
der's overflow area is searched. If that is full, and the record is not found, then the
system-wide overflow is searched.
After initial construction of the database, so long as no new records are inserted
or deleted, access is efficient because it requires only two disk fetches. The first
disk fetch recovers the block table for the desired cylinder. The second disk fetch
recovers the block that, under good conditions, contains the record. After many
inserts, the overflow list becomes too long, resulting in significant search time as
the cylinder overflow area fills up. Under extreme conditions, many searches might
eventually lead to the system overflow area. The “solution” to this problem is to
periodically reorganize the entire database. This means re-balancing the records
1
Recall from Section 8.2.1 that a cylinder is all of the tracks readable from a particular placement
of the heads on the multiple platters of a disk drive.
