The hb -tree: A multi-attribute index supporting concurrency, recovery and node consolidation

Abstract. We propose a new multi-attribute index. Our ap-proach combines the hB-tree, a multi-attribute index, and the Π-tree, an abstract index which offers efficient concur-rency and recovery methods. We call the resulting method the hB -tree. We describe several versions of the hB -tree, each using a different node-splitting and index-term-posting algorithm. We also describe a new node deletion algorithm. We have implemented all the versions of the hB -tree. Our performance results show that even the version that offers no performance guarantees, actually performs very well in terms of storage utilization, index size (fan-out), exact-match and range searching, under various data types and distri-butions. We have also shown that our index is fairly in-sensitive to increases in dimension. Thus, it is suitable for indexing high-dimensional applications. This property and the fact that all our versions of the hB -tree can use the Π-tree concurrency and recovery algorithms make the hB -tree a promising candidate for inclusion in a general-purpose DBMS