A Model for Optimizing Indexed File Structures

Multilevel indexes have long been used for accessing records in sorted files. Given the access cost at each level, the total cost of retrieving a record from the file can be substantially reduced by selecting the proper size of the index at each level. Organizations involving a variable number of levels are covered and binary searching is compared to sequential searching. The literature on the organization of file structures is largely qualitative, rather than quantitative, in nature. A number of books and survey articles give thorough discussions of possible indexed file organization strategies (e.g., Refs. 1-4). However, the development of techniques for comparin