Implicit data structures for linear hashing schemes (Q1116689)

Two implicit data structures are defined which combine advantages of hashing and indexing methods. Both structures have the common property that their growth emulates the pattern of splittings in linear hashing. In Section 2 the linear binary trie is introduced and its relationship to the linear hashing scheme based on digital search is shown. Section 3 discusses linear binary search trees that are conceived as trees for interpolation hashing and order-preserving variant of linear hashing, respectively. The second application of trees organizes a set of records stored, without a priori knowledge of the bounds of the key values. The presented structurs lead to a sequential storage scheme which requires no pointers. They are maintained completely in implicit fashion. One can use them to support sequential access and range queries more effectively.