Extendible Hashing—A Fast Access Method For Dynamic Files

Authors

Ronald Fagin, IBM Research Lab
Jurg Nievergelt, Institut Informatik
Nicholas Pippenger, Harvey Mudd CollegeFollow
H. Raymond Strong, IBM Research Lab

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1979

Abstract

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 grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.

Rights Information

© 1979 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1145/320083.320092

Recommended Citation

Fagin, R., Nievergelt, J., Pippenger, N., and Strong, H.R. "Extendible Hashing|A Fast Technique for Files on Secondary Storage Devices", ACM Trans. on Database Sys., 4 (1979), 315-344. doi: 10.1145/320083.320092