Issue No.06 - November (1982 vol.8)
H. Mendelson , Graduate School of Management, University of Rochester
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 considers their implecations on the physical database design. A complete characterization of the probability distribution of the directory size and depth is derived, and its implications on the design of the directory are studied. The expected input/output costs of various operations are derived, and the effects of varying physical design parameters on the expected average operating cost and on the expected volume are studied.
performance analysis, Database, extendible hashing, hashing
H. Mendelson, "Analysis of Extendible Hashing", IEEE Transactions on Software Engineering, vol.8, no. 6, pp. 611-619, November 1982, doi:10.1109/TSE.1982.236022