Publication
Journal of the ACM
Paper

File Organization: On the Selection of Random Access Index Points for Sequential Files

Download paper

Abstract

The construction of a hierarchy of indexes (the indexed sequential access method) is one means of providing rapid random access to sequential files. An examination is made of the consequences of partially or completely replacing one or more index levels by linear interpolation procedures. For all possible configurations of the several types of key distributions investigated, linear interpolation on the average provides significant performance improvements. Typically, the two accesses required to obtain track index and data are reduced to 1.1 to 1.7 accesses per record. Extremely unusual key distribution will, however, raise the number of accesses required above 2. © 1969, ACM. All rights reserved.

Date

01 Oct 1969

Publication

Journal of the ACM

Authors

Topics

Resources

Share