About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM Transactions on Database Systems (TODS)
Paper
Bounded Index Exponential Hashing
Abstract
Bounded index exponential hashing, a new form of extendible hashing, is described. It has the important advantages over most of the other extendible hashing variants of both (i) providing random access to any record of a file in close to one disk access and (ii) having performance which does not vary with file size. It is straightforward to implement and demands only a fixed and specifiable amount of main storage to achieve this performance. Its underlying physical disk storage is readily managed and record overflow is handled so as to insure that unsuccessful searches never take more than two accesses. 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. © 1983, ACM. All rights reserved.