The hBP-tree - A Modified hB-tree Supporting Concurrency, Recoveryand Node Consolidation

Abstract

We describe a new access method, the hB\Pi-tree, an adaptation of the hB-tree index to the constraints of the Pi-tree. The Pi-trees, a generalization of the B link-trees, provide high concurrency with recovery, because they break down structure modification into a series of short atomic actions. In addition, the IItrees include a node consolidation algorithm. The hB-tree is, a multi-attribute index which is highly insensitive to dimensionality, but which has no node consolidation algorithm and has a flaw in its split/post algorithm in certain special cases. The hB\Pi-tree corrects the splitting/posting algorithm and adapts the concurrency, recovery and node consolidation of the Pi-tree to the hB-tree. The combination makes the hB\Pi-tree suitable for inclusion in a general purpose database management system.supporting multi-attribute and spatial queries.