ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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 hBII-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 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 hBII-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 hBII-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

ACM SIGMOD Anthology

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David B. Lomet: Grow and Post Index Trees: Roles, Techniques and Future Potential. SSD 1991: 183-206 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Betty Salzberg: On Indexing Spatial and Temporal Data, Invited Project Review. Inf. Syst. 19(6): 447-465(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)