Dynamic key-ordered file structures for the random and sequential access to very large data/knowledge bases
Nabil I. Hachem · 1988
This research is concerned with the design of efficient access methods for very large dynamic files. This class of file structures is based on order preserving hashing and is referred to as the dynamic random-sequential access method (DRSAM). The main characteristic of this method is the sequential allocation property which results in the clustering of data in key order in consecutive physical space on secondary storage. This leads to the development and adaptation of new techniques for directoriless dynamic hashing methods. An analytical model together with trace driven simulations of DRSAM show performance improvements over previous methods for both direct access and range queries. The DRSAM file structure is extended to deal with non-uniform distributions which are typical of key-ordered hashed files. The resulting structure is referred to as extended DRSAM (EDRSAM) and is proposed as an alternative to indexed-sequential files. EDRSAM is efficient for the processing of very large dynamic files; specifically for secondary key retrieval. This makes it suitable to be used as an access method in a multi-user environment. Surrogate (or signature) files are used to generate compressed images of very large databases. EDRSAM is proposed to index surrogate files and the resulting physical model is called inverted dynamic surrogate files (IDSF). With IDSF, the reduced storage overhead of surrogate files is combined with the high performance of EDRSAM to provide a flexible and efficient physical model for very large data/knowledge bases.