The hBPi/-tree: A Concurrent and Recoverable Multi-attribute Index

We propose a new multi-attribute index. Our approach combines the hB-tree, a multi-attribute index, and the Pi-tree, an abstract index which offers efficient concurrency and recovery methods. We call the resulting method the hBPi-tree. We describe several versions of the hBPi-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 hBPi-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 distributions. We have also shown that our index is fairly insensitive to increases in dimension. Thus, it is suitable for indexing high-dimensional applications. This property and the fact that all our versions of the hBPi-tree can use the Pi-tree concurrency and recovery algorithms make the hBPi- tree a promising candidate for inclusion in a general-purpose DBMS.