The term hB-tree stands for “holey brick B tree.” A brick is a multidimensional rectangle, and a holey brick is a brick from which one or more smaller bricks may have been extracted. The hB-tree is used here as an index structure for data records where several attributes form the record index. Such a multidimensional clustering can considerably reduce the number of storage accesses when multi-attribute searches are the rule; inserting a new record requires updating a single index instead of multiple single-attribute indexes. The hB-tree is a skillful extension of B+ trees to several dimensions that essentially shares all their desirable properties.

Each node representing a holey brick has two direct subnodes, which usually partition it in a single dimension; sometimes several dimensions are utilized. Using subnodes in several dimensions leads to holes in the bricks; preferably a corner (rather than an interior part) is removed. The leaves of the tree are the data nodes, that is, the pages containing records. If inserting a new record forces a data node to split, it may happen that any one-dimensional subdivision results in heavily unbalanced new leaves, but holey bricks can guarantee that each leaf contains at least one-third of the records (if no multiple records with equal indexing attributes exist). Subtrees of the hB-tree are stored on the index pages, which the authors call index nodes because they form a tree with multiple descendants of an index page. If such an index page overflows, it must be split as well. Splitting at the root may result in unbalanced new index pages, but using holey bricks one can now ensure that each leaf contains at least one-third of the nodes contained in the old index page. Splitting a node is possible without adjusting the subtrees, in contrast to K-D-B-trees, which were the point of departure for developing hB-trees and which they resemble in other ways.

The authors give the construction of the hB-tree and the algorithms for splitting leaves or index pages in detail. They also analyze average as well as worst-case behavior for the addition of records and for the search. Thus it is guaranteed that the hB-tree has a good space utilization in the index and data pages, that the index is significantly smaller than the data collection, and that match queries have a good performance. This holds for exact match queries as well as for range queries and for arbitrary distributions of the keys. Other known methods for multi-attribute indexing, such as bit interleaving, grid files, and K-D-B-trees, have considerably inferior worst-case behavior in some respects, while even B+ trees in one dimension (where an even partition on both subnodes can always be achieved) behave only marginally better.