Order-preserving dynamic hashing schemes for associative searching in data base systems
Mohamed Ouksel · 1983
Multidimensional storage mappings suitable for dynamic data bases are presented. The first scheme is a natural extension of Litwin's Linear Hashing, of which it inherits all the benefits: the storage space is allowed to gracefully expand or contract as desired, the storage utilization can be very high and is programmer controllable, no directory is needed to answer exact-match and partial-match queries, and retrieval and update operations are simple and efficient. Simulation results confirm the high performance: an average successful search cost very close to 1 access, and an average unsuccessful search cost close to 2 even while maintaining a storage utilization of 90%. The basic method is extended to handle range queries by using axial directories which preserve the order among the records on each of the d attributes and whose total space requirement is very small. These directories avoid the utilization of any kind of extraneous information like pointers. The basic scheme which is based on a predetermined cyclic order among the attributes (or the axes) is further improved by allowing a more flexible order, albeit still cyclic. In a second step, a generalization is obtained by totally relaxing the cyclic order constraint. As a result, further optimizations are possible. Finally, some bucket allocation methods which improve the queries performance by storing the file on several concurrently accessible disks are introduced.