The hB-tree: a multiattribute indexing method with good guaranteed performance
- 1 December 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 15 (4), 625-658
- https://doi.org/10.1145/99935.99949
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- A simple bounded disorder file organization with good performanceACM Transactions on Database Systems, 1988
- Partial expansions for file organizations with an indexACM Transactions on Database Systems, 1987
- A New Method for Fast Data Searches with KeysIEEE Software, 1987
- Grid file concurrencyInformation Systems, 1986
- The Grid FileACM Transactions on Database Systems, 1984
- Quintary treesACM Transactions on Database Systems, 1980
- Multidimensional Binary Search Trees in Database ApplicationsIEEE Transactions on Software Engineering, 1979
- Ubiquitous B-TreeACM Computing Surveys, 1979
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Organization and maintenance of large ordered indexesActa Informatica, 1972