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

An Incremental Approach to Dynamic Hashing

for Expansible Files

**Ye-In Chang and Chien-I Lee**

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.