ACM Transactions on Database Systems · 1990 · 279 citations · 16 references
ComputingComputer ScienceData StructuresDatabasesStorage SystemsData Structure AlgorithmsHash TablesQuery ProcessingSearching AlgorithmsSpatial PartitioningB-tree IndexingB-treesIndex StructuresIndexingIndexing StructuresK-d TreesStorage Space UtilizationStorage Utilization
A new multiattribute index structure called the hB-tree is introduced. It is derived from the K-D-B-tree of Robinson [15] but has additional desirable properties. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees [1]. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which no longer represent brick-like regions in k-space, but that can be characterized as holey bricks, bricks in which subregions have been extracted. We present results that guarantee hB-tree users decent storage utilization, reasonable size index terms, and good search and insert performance. These results guarantee that the hB-tree copes well with arbitrary distributions of keys.
16
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
J. Nievergelt, Hans Hinterberger, Kenneth C. Sevcik · ACM Transactions on Database Systems · 1984 · 1.1K citations · Full text
John T. Robinson · 1981 · 888 citations · Full text