Balanced multidimensional extendible hash tree
Ekow J. Otoo · 1985
We present a method for designing a multidimensional order preserving extendible hashing scheme that allows the directory to grow almost linearly with the number of insertions, irrespective of the key distribution.Such robustness in the design is achieved through the use of a hierarchical directory that grows in a manner similar to a multidimensional B-tree.For most practical directory sizes of at most 2s* entries, we guarantee no more than three diik accesses for an exact match search.Like the grid file, the directory corresponds to a rectilinearly partitioned attribute space which is represented as d-dimensional extendible &ray.Hence range and partial-range searches are efficiently executed in 0(n~), where no is the number of rectangular cells that cover the response region.