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.