Dynamic hashing with distributed overflow space: A file organization with good insertion performance

摘要

Retrieval, insertion and cycling performance in dynamic hash file organizations is influenced by a number of factors. These include the growth rate experienced by the file, the distribution of hashkeys over the address space, and the method used for handling overflow records. In this paper we propose a dynamic hashing scheme which uses a generalized exponential hash function and a directory-based overflow handling scheme. The hash function, which is designed to accommodate a variety of file growth rates, ensures that retrieval, insertion and file expansion performance is non-cyclic. We extend the concept of dynamic overflow sharing by distributing overflow space in the file. This is accomplished by combining contiguous sets of pages in the file into groups and assigning each group an additional page, referred to as a preallocated overflow page, for storing some or all of the records that overflow the pages in the group. Overflow records that cannot be stored in the preallocated page are directed to a separate overflow file. The resulting system is analyzed mathematically and results obtained have been confirmed using simulation. Based on these results we conclude that the proposed method, while providing good support for retrieval-intensive databases, is ideal for databases which experience a large proportion of insertion transactions. In addition, the characteristics of the scheme enable efficient implementation in a disk cache environment.