Linear spiral hashing for expansible files

The goal of dynamic hashing is to design a function and a file structure th at allow the address space allocated to the file to be increased and reduce d without reorganizing the whole file. In this paper, we propose a new sche me for dynamic hashing in which the growth of a file occurs at a rate of nk/n per full expansion, where n is the number of pages of the file and k is a given integer constant which is smaller than n, as compared to a rate of two in linear hashing. Like linear hashing, the proposed scheme (called li near spiral hashing) requires no index; however. the proposed scheme may or may not add one more physical page, instead of always adding one more page in linear hashing, when a split occurs. Therefore, linear spiral hashing c an maintain a more stable performance through the file expansions and have much better storage utilization than linear hashing. From our performance a nalysis, linear spiral hashing can achieve nearly 97 percent storage utiliz ation as compared to 78 percent storage utilization by using linear hashing , which is also verified by a simulation study.