The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation
Georgios D. Evangelidis, David Lomet, Betty Joan Salzberg · Very Large Data Bases · 1995
We describe a new access method, the hB”-tree, an adaptation of the hB-tree index to the constraints of the II-tree . The II-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 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”-tree corrects the splitting/posting algorithm and adapts the concurrency, recovery and node consolidation of the II-tree to the hB-tree. The combination makes the hBn-tree suitable for inclusion in a general purpose database management system.supporting multi-attribute and spatial queries. keywords: indexing, B-trees, multi-attribute access methods, spatial access methods, concurrency, recovery