The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation.

Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561

@inproceedings{DBLP:conf/vldb/EvangelidisLS95,
  author    = {Georgios Evangelidis and
               David B. Lomet and
               Betty Salzberg},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery
               and Node Consolidation},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {551-561},
  ee        = {db/conf/vldb/EvangelidisLS95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We describe a new access method, the hB^II-tree, an adaptation of the hB-tree index to the constraints of the II-tree . The II-trees, a generalization of the B^link-trees, provide highconcurrency with recovery, because they break down structure modification into a series of short atomic actions. In addition, the II- 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 hB^II-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 hB^II-tree suitable for inclusion in ageneral purpose database management system supporting multi-attribute and spatial queries.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents

References

[1]: Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979)
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[3]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977)
[4]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[5]: ...
[6]: Georgios Evangelidis, Betty Salzberg: Using the Holy Brick Tree for Spatial Data in General Purpose DBMSs. IEEE Data Eng. Bull. 16(3): 34-39(1993)
[7]: Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605
[8]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[9]: David B. Lomet: Grow and Post Index Trees: Roles, Techniques and Future Potential. SSD 1991: 183-206
[10]: David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)
[11]: David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
[12]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
[13]: C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
[14]: Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113
[15]: Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
[16]: Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
[17]: Betty Salzberg: On Indexing Spatial and Temporal Data, Invited Project Review. Inf. Syst. 19(6): 447-465(1994)
[18]: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
[19]: Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
[20]: V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
[21]: Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11