© 1991 by British Computer Society
High Storage Utilisation for Single-Probe Retrieval Linear Hashing
Computer Science Department, North Carolina State University, Raleigh, North Carolina 27695-8206, USA
Many information systems require expandable files. Linear hashing is a well-known technique for growing a file without requiring a complete reinsertion of the data. With the advantage of expandability comes greater retrieval costs as compared to static file methods. A recent modification of linear hashing, Linear Hashing with Separators (LHS), requires only a single access of auxiliary memory. However, this method too has limitations. It introduces secondary clustering which increases insertion costs and it has lower storage utilisation than might be desirable.
After surveying linear hashing and LHS, this paper introduces an algorithm called High Storage Utilisation for Single-Probe Retrieval (HSUSPR is read SOO-SPRAH). HSUSPR linear hashing maintains the single probe retrieval of LHS but with lower insertion costs and greater auxiliary storage utilisation. To achieve these benefits HSUSPR does use more primary memory for storing index information.
Extensive experimental results are given comparing HSUSPR with LHS. Experimental results also are provided which indicate that the performance of HSUSPR is independent of the distribution of the key data. HSUSPR is particularly useful for information systems with many insertions and/or those systems involving real-time updates.
Received October 1990. revised May 1991.
* Please address all correspondence to this author.
Computer Science Department, North Carolina State University, Raleigh, North Carolina 27695-8206 USA