Extendible hashing—a fast access method for dynamic files

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.

REFERENCES

• 1: ADELSON-VELSKII, G.M., AND LANDIS, Y.M. An algorithm for the organization of information. Dokl. Akad. Nauk SSSR 146 (1962), 263-266 (Russian). English transl, in Soviet Math. Dokl. 3 (1962), 1259-1262.
• 2: ANDERSON, T.W., AND SAMUELS, S.M. Some inequalities among binomial and Poisson probabilities. Proc. 5th Berkeley Symp. Math. Statist. and Probability, 1965, pp. 1-12.
• 3: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Informatica I (1972), 173-189.
• 4: CARTER, J.L., AND WEGMAN, M. Universal classes of hash functions. Res. Rep. RC 6687, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., 1977. To appear in J. Comptr. Syst. Sci.
• 5: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 6: OS/VS2 ISAM Logic, IBM SY26-3833.
• 7: KHINCHINE, A.Y. Mathematical Methods in the Theory of Queueing. Griffin, London, 1969.
• 8: KNOTT, G.D. Expandable open addressing hash table storage and retrieval. Proc. ACM SIGFI- DET Workshop on Data Description, Access, and Control, 1971, pp. 186-206.
• 9: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 10: LARSON, P. Dynamic hashing. BIT 18 (1978), 184-201.
• 11: LITWIN, W. Virtual hashing: A dynamically changing hashing. Proc. Very Large Data Bases Conf., Berlin, 1978, pp. 517-523.
• 12: MARKOWSKY, G, CARTER, J.L., AND WEGMAN, M. Analysis of a universal class of hash functions. Lecture Notes in Computer Science 64, 1978, pp. 345-354.
• 13: MATTSON, R., GECSEI, J., SLUTZ, D., AND TRAIGER, i. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
• 14: MVNTZ, R, AND UZGALIS, R. Proc. Princeton Conf. on Inform. Sci. and Syst., 1970, pp. 345-349.
• 15: NEWELL, A., AND SIMON, H.A. The logic theory machine: A complex information processing system. IRE Trans. Inform. Theory 2, 3 (Sept. 1956), 61-79.
• 16: NIEVERGELT, J., AND REINGOLD, E.M. Binary search of trees of bounded balance. SIAM J. Comptng. 2 (1973), 33-43.
• 17: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 18: Wayne Allan Walker, Hybrid trees as a data structure., 1975
• 19: YAO, A. C.-C. Random 3-2 trees. Acta lnformatica 9 {1978), 159-170.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design

Keywords:
B-tree, access method, directory, extendible hashing, external hashing, file organization, hashing, index, radix search, searching, trie