Retrieval of records in key sequence from direct access hash files

The desirable random access characteristics of hash tables until now have been considered incompatible with the ability to retrieve the record next in key sequence. In this paper, algorithms are developed for such Get Next retrieval from a specific category of hash tables. It is shown that the random access performance is unchanged, and that the overhead for the Get Next operations can be quite satisfactory. These characteristics can be particularly advantageous for file and data base system access. Implications for choice of blocking factors on secondary storage devices are assessed. Extensions of the basic technique serve to expand the scope of applications, allow for distribution dependent hashing schemes, and describe a spectrum of schemes in which tradeoffs can be made between the efficiencies of random access and Get Next retrievals.Technical report DCS-TR-8