AbstractThe 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.
SubjectsHash tables, Scatter storage, Data base access, Sequential retrieval, Random access, Searching, Index structure, File organization, Distribution dependent hashing, Bucket size
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).