The hBPi/-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation
- Georgio Evangelidis ,
- David Lomet ,
- Betty Salzberg
Published by Morgan Kaufmann Publishers
We describe a new access method, the hBPi-tree, an adaptation of the hB-tree index to the constraints of the Pi-tree. The Pi-trees, a generalization of the Blink-trees, provide high concurrency with recovery, because they break down structure modification into a series of short atomic actions. In addition, the Pi-trees 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 hBPi-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 hBPi-tree suitable for inclusion in a general-purpose database management system supporting multi-attribute and spatial queries.