interpolation-based index maintenance
A new interpolation-based order preserving hashing algorithm suitable for on-line maintenance of large dynamic external files under sequences of four kinds of operations insertion, update, deletion, and orthogonal range query is proposed. The scheme, an adaptation of linear hashing, requires no index or address directory structure and utilizes O(n) space for files containing n records, all of the benefits of linear hashing are inherited by this new scheme. File implementations yielding average successful search lengths much less than 2 and average unsuccessful search lengths much less than 4 for individual records are obtainable, the actual storage required is controllable by the implementor.
indexing maintenance order hashing algorithm dynamic sequence operability update scheme adapt addressing structure space records implementation search storage interpolation