# Extendible hashing—a fast access method for dynamic files

@article{Fagin1979ExtendibleHF, title={Extendible hashing—a fast access method for dynamic files}, author={Ronald Fagin and J{\"u}rg Nievergelt and Nicholas Pippenger and H. Raymond Strong}, journal={ACM Transactions on Database Systems (TODS)}, year={1979}, volume={4}, pages={315 - 344} }

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… Expand

#### Figures and Topics from this paper

#### 718 Citations

Extendible Hashing

- Computer Science
- Encyclopedia of Database Systems
- 2009

Extendible Hashing is a dynamically updateable disk-based index structure which implements a hashing scheme utilizing a directory which logically doubles the number of buckets. Expand

Analysis of Extendible Hashing

- Computer Science
- IEEE Transactions on Software Engineering
- 1982

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. Expand

Multilevel Extendible Hashing: A File Structure for Very Large Databases

- Computer Science
- IEEE Trans. Knowl. Data Eng.
- 1991

A dynamic hashing scheme based on extendible hashing is proposed whose directory can grow into a multilevel directory and the simulation results reveal that the proposed scheme is superior than the other two with respect to directory space utilization. Expand

Linear hashing with separators—a dynamic hashing scheme achieving one-access

- Computer Science
- TODS
- 1988

The new method is the first practical method offering one-access retrieval for large dynamic files, and its most outstanding feature is that any record can be retrieved in exactly one disk access. Expand

Concurrency in Extendible Hashing

- Computer Science
- Inf. Syst.
- 1988

This paper presents a solution to allow for concurrency in one of these dynamic hashing data structures, namely extendible hashfiles, based on locking protocols and minor modifications in the data structure. Expand

Bounded index exponential hashing

- Computer Science
- TODS
- 1983

The method's ability to access data in close to a single disk access makes it possible to organize a database, in which files have a primary key and multiple secondary keys, such that the result is a significant performance advantage over existing organizations. Expand

A Mapping Function for the Directory of a Multidimensional Extendible Hashing

- Computer Science
- VLDB
- 1984

A generalization of the Extendible Hashing scheme of Fagin and others is presented for structuring files of records with d-attribute fields and algorithms for searching, inserting and processing partial-match queries are presented. Expand

Multidimensional extendible hashing for partial-match queries

- Computer Science
- International Journal of Computer & Information Sciences
- 2005

It is shown thatn-dimensional hashing is a special case of one- dimensional hashing, thus the storage utilization of the buckets is independent ofn, and the advantages of multidimensional hashing are presented. Expand

Dynamic signature hashing

- Computer Science
- [1989] Proceedings of the Thirteenth Annual International Computer Software & Applications Conference
- 1989

A dynamic hashing scheme that guarantees single access retrieval from the disk is proposed, based on the external hashing scheme proposed by G.H. Gonnet and P.A. Larson, and the performance is studied using simulations with real-life files. Expand

Extendible hashing for concurrent operations and distributed data

- Computer Science
- PODS '83
- 1983

This paper presents solutions to allow for concurrency that are based on locking protocols and minor modifications in the data structure for extendible hash files for distributed data. Expand

#### References

SHOWING 1-10 OF 24 REFERENCES

Virtual Hashing: A Dynamically Changing Hashing

- Computer Science
- VLDB
- 1978

This work defines virtual hashings which practically independently of the number of such records find in one disk access almost each record of the file, such that several accesses would be needed if the function initially chosen for the file was used. Expand

Dynamic hashing

- Computer Science
- BIT
- 1978

A new file organisation called dynamic hashing is presented. The organisation is based on normal hashing, but the allocated storage space can easily be increased and decreased without reorganising… Expand

Universal classes of hash functions (Extended Abstract)

- Mathematics, Computer Science
- STOC '77
- 1977

An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions. Expand

Universal Classes of Hash Functions

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1979

An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions. Expand

Analysis of a Universal Class of Hash Functions

- Mathematics, Computer Science
- MFCS
- 1978

This paper uses linear algebraic methods to analyze the performance of several classes of hash functions, including the class H2 presented by Carter and Wegman, and shows that the probability of choosing a function from H which maps x to the same value as more than t other elements of S is no greater than min. Expand

Evaluation Techniques for Storage Hierarchies

- Computer Science
- IBM Syst. J.
- 1970

A new and efficient method of determining, in one pass of an address trace, performance measures for a large class of demand-paged, multilevel storage systems utilizing a variety of mapping schemes and replacement algorithms. Expand

Binary search trees of bounded balance

- Mathematics, Computer Science
- STOC
- 1972

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is… Expand

Binary Search Trees of Bounded Balance

- Mathematics, Computer Science
- SIAM J. Comput.
- 1973

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is… Expand

Trie memory

- Computer Science
- CACM
- 1960

In this paper several paradigms of trie memory are described and compared with other memory paradigm, their advantages and disadvantages are examined in detail, and applications are discussed. Expand

Some inequalities among binomial and Poisson probabilities

- Mathematics
- 1967

k (1.4) P(k; X) = E p(j; X), k = 0, 1, i-o for X = np. In this paper it is shown that the error of approximation of the binomial cumulative distribution function P(k; np) B(k; n, p) is positive if k… Expand