Linear-density hashing with dynamic overflow sharing

摘要

A new method for handling overflow records in a linear hash file is introduced. This method, referred to as dynamic overflow sharing, requires that a small number of contiguous pages in the file be treated as a group for the initial sharing of an overflow page. An increase in the number of overflow records belonging to the group could result in the overflow page itself being split. The resulting two overflow pages are now associated with half the pages in the group. This process of overflow page splitting and reallocation can continue with further growth in the number of records hashing to the group. An important element in dynamic overflow sharing is that pointers to overflow are maintained in the home pages themselves in the form of a small extendible directory. A primary advantage of this method is that it is possible to retrieve any record with a maximum of two disk accesses. In addition, it enables file expansion to be performed at per record access costs which are superior to other recently reported schemes. Dynamic overflow sharing is described and analyzed for two situations: 1.(1) a linear, downward slope load distribution and2.(2) a uniform load distribution of records in the file. A comparison of the performance in the two cases reveals that, in general, the average retrieval, insertion and storage utilization performance of linear density hashing is superior to uniform density hashing and only slightly worse than conventional (non-dynamic) hashing.