Per-Åke Larson
Abstract
Linear hashing with partial expansions is a new file organization primarily intended for files which grow and shrink dynamically. This paper presents a mathematical analysis of the expected performance of the new scheme. The following measures are considered: length of successful and unsuccessful searches, accesses required to insert or delete a record, and the size of the overflow area. The performance is cyclical. For all performance measures, the necessary formulas are derived for computing the expected performance at any point of a cycle and the average over a cycle. Furthermore, the expected worst case in connection with searching is analyzed. The overall performance depends on several file parameters. The numerical results show that for many realistic parameter combinations the performance is expected to be extremely good. Even the longest search is expected to be of quite reasonable length.
- 1 FAGIN, R., NIEVERGELT, J., PIPPENGER, N., AND STRONG, H.R. Extendible hashing--A fast access method for dynamic i'ties. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 315-344. Google Scholar
Digital Library
- 2 GONNET, G.H. Expected length of the longest probe sequence in hash code searching. J. ACM 28, 2 (April 1981), 289-304. Google ScholarDigital Library
- 3 LARSON, P.-/k. Dynamic hashing. BIT 18, 2 (1978), 184-201.Google ScholarDigital Library
- 4 LARSON, P.-A. Linear hashing with partial expansions. In Proc. 6th Conf. Very Large Data Bases (Montreal, Canada, Oct. 1-3), ACM, New York, 1980, pp. 224-232.Google Scholar
- 5 LITWIN, W. Virtual hashing: A dynamically changing hashing. In Proc. 4th Conf. Very Large Data Bases (Berlin, 1978), 517-523.Google Scholar
- 6 LITWIN, W. Hachage virtuel: Une nouvelle technique d'adressage de memoires. These de Doctorat d'Etat, Univ. Paris VI, 1979.Google Scholar
- 7 LITWlN, W. Linear hashing: A new tool for fries and tables addressing. In Proc. 6th Conf Very Large Data Bases (Montreal, Canada, Oct. 1-3), ACM, New York, pp. 212-223. Google ScholarDigital Library
- 8 MARTIN, G.N.N. Spiral storage: Incrementally augmentable hash addressed storage. Theory of Computation Rep. 27, Univ. of Warwick, England, 1979. Google ScholarDigital Library
Index Terms
- Performance analysis of linear hashing with partial expansions
Recommendations
Linear hashing with partial expansions
VLDB '80: Proceedings of the sixth international conference on Very Large Data Bases - Volume 6A new method for organising dynamic files is presented and its performance is analysed. The scheme is a generalization of W. Litwin's linear (virtual) hashing. The amount of storage space allocated to the file grows and shrinks in a simple fashion ...
Extendible hashing—a fast access method for dynamic files
Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that ...
Analysis of Extendible Hashing
Extendible hashing is an attractive direct-access technique which has been introduced recently. It is characterized by a combination of database-size flexibility and fast direct access. This paper derives performance measures for extendible hashing, and ...
Comments