New file organization based on dynamic hashing

Abstract

New file organizations based on hashing and suitable for data whose volume may vary rapidly recently appeared in the literature. In the three schemes which have been independently proposed, rehashing is avoided, storage space is dynamically adjusted to the number of records actually stored, and there are no overflow records. Two of these techniques employ an index to the data file. Retrieval is fast and storage utilization is low. In order to increase storage utilization, we introduce two schemes based on a similar idea and analyze the performance of the second scheme. Both techniques use an index of much smaller size. In both schemes, overflow records are accepted. The price which has to be paid for the improvement in storage utilization is a slight access cost degradation.