[Previous] [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.4, pp.495-521 (December 1993)
An Incremental Approach to Dynamic Hashing
for Expansible Files*

Ye-In Chang and Chien-I Lee
Department of Applied Mathematics
National Sun Yat-Sen University
Kaohsiung, Taiwan, R.O.C.

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 with-out reorganizing the whole file. In this paper, we propose an incremental approach to a dynamic hashing scheme in which the growth of a file occurs 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. Like linear hashing, the proposed approach required no index; however, the proposed approach may or may not add one more page, instead of always adding one more page in linear hashing, when a split occurs. Therefore, the proposed approach can have much better storage utilization than can linear hashing. To reduce the number of disk accesses for overflow records, the proposed approach applies separators; therefore, the retrieval of any record is guaranteed to be in at most two disk accesses. From our performance analysis, the proposed approach can achieve nearly 95% storage utilization as compared to 78% storage utilization by using linear hashing, which is also verified by a simulation study. Moreover, the proposed approach can be generalized to have the growth of a file at a rate of ((n + k - 1) / n), where k is an integer larger than 1. As k 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.

Keywords: access methods, dynamic storage allocation, file organization, file system management, hashing

Received May 10, 1993; revised September 13, 1993.
Communicated by Wei-Pang Yang.
*This research was supported in part by the National Science Council of Republic of china under Grant No. NSC82-0408-E-100-135.