KEY ACCESS TYPE FILE APPARATUS

摘要

A key-accessed (indexed) file is organized such that the file structure consists only of two levels, an index level and a data level. Both levels are permanently stored on a page-organized secondary storage medium that supports random accessing of the pages. The index level is designed to have a fixed and specifiable number of pages and is stored entirely in the computer's memory when the file is in use. The fixed size of the index is made possible by having each index entry reference a data node with a growing (or shrinking) number of data pages as the file changes in size. Avoiding the accessing of more than one of the data pages referenced by an index entry is accomplished by means of an address computation that utilizes bits of the search argument.