CLIMBING HASHING FOR EXPANSIBLE FILES

The goal of dynamic hashing is to design a function and a file structu re that allow the address space allocated to the file to be increased and reduced without reorganizing the whole file. In this paper, we pro pose a new dynamic hashing scheme called climbing hashing, which requi res 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 occ urs, the relative position of the new page (into which a data record m ay move), to the current page (where the data record is now), is propo rtional to the number of full expansions. Therefore, it seems like the data record is climbing in the files. (Note that a level is defined a s 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 simu lation 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 t he average number of disk accesses for data retrieval.