CLIMBING HASHING FOR EXPANSIBLE FILES

Abstract

The goal of dynamic hashing is to design a function and a file structure that allow the address space allocated to the file to be increased and reduced without reorganizing the whole file. In this paper, we propose a new dynamic hashing scheme called climbing hashing, which requires no index and has the growth of a file at a rate of n+1/n per full expansion, where n is the number of pages of the file, as compared to a rate of two in linear hashing. In climbing hashing, when a split occurs, the relative position of the new page (into which a data record may move), to the current page (where the data record is now), is proportional to the number of full expansions. Therefore, it seems like the data record is climbing in the files. (Note that a level is defined as the number of full expansions that have happened thus far.) From our performance analysis, given a fixed load control, the proposed scheme can achieve nearly 96% storage utilization as compared to 78% storage utilization by using linear hashing, which is also verified by a simulation study. Moreover, the proposed scheme can be generalize to have the growth of a file at a rate of n+t-1/n. per full expansion, where t is an integer larger than 1. As t is increased, the average number of overflow pages per home page is reduced, resulting in a decrease of the average number of disk accesses for data retrieval.