ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Performance of B+ Tree Concurrency Algorithms.

V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
@article{DBLP:journals/vldb/SrinivasanC93,
  author    = {V. Srinivasan and
               Michael J. Carey},
  title     = {Performance of B+ Tree Concurrency Algorithms},
  journal   = {VLDB J.},
  volume    = {2},
  number    = {4},
  year      = {1993},
  pages     = {361-406},
  ee        = {db/journals/vldb/SrinivasanC93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A number of algorithms have been proposed to access B+-trees concurrently, but they are not well understood. In this article, we study the performance of various B+-tree concurrency control algorithms using a detailed simulation model of B+-tree operations in a centralized DBMS. Our study covers a wide range of data contention situations and resource conditions. In addition, based on the performance of the set of B+-tree concurrency control algorithms, which includes one new algorithm, we make projections regarding the performance of other algorithms in the literature. Our results indicate that algorithms with updaters that lock-couple using exclusive locks perform poorly as compared to those that permit more optimistic index descents. In particular, the B-link algorithms are seen to provide the most concurrency and best overall performance. Finally, we demonstrate the need for a highly concurrent long-term lock holding strategy to obtain the full benefits of a highly concurrent algorithm for index operations.

Copyright © 1993 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.

Key Words

Performance, simulation models, B+-tree structures, resource conditions, workload parameters, lock modes, data contentions.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[Agrawal et al. 1987]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bayer & McCreight 1972]
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
[Bayer & Schkolnick 1977]
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
[Biliris 1985]
...
[Biliris 1987]
Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Carey & Thompson 1984]
Michael J. Carey, Clark D. Thompson: An Efficient Implementation of Search Trees on (lg N + 1) Processors. IEEE Trans. Computers 33(11): 1038-1041(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chan et al. 1982]
Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Franaszek & Robinson 1985]
Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Goodman & Shasha 1985]
Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gray 1979]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Guibas & Sedgewick 1978]
Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Johnson & Shasha 1989]
Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Johnson & Shasha 1990]
Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Johnson 1990]
...
[Kersten & Tebra 1984]
Martin L. Kersten, Hans Tebra: Application of an Optimistic Concurrency Control Method. Softw., Pract. Exper. 14(2): 153-168(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kung & Lehman 1980]
H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kwong & Wood 1982]
Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lanin & Shasha 1986]
Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lausen 1984]
Georg Lausen: Integrated Concurrency Control in Shared B-Trees. Computing 33(1): 13-26(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lehman & Yao 1981]
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
[Livny 1990]
...
[Lomet & Salzberg 1992]
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
[Miller & Snyder 1978]
...
[Mohan 1990]
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mohan & Levine 1989]
...
[Mohan & Levine 1992]
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
[Mond & Raz 1985]
Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sagiv 1985]
Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Samadi 1976]
Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shasha 1984]
...
[Shasha 1985]
Dennis Shasha: What Good are Concurrent Search Structure Algorithms for databases Anyway? IEEE Database Eng. Bull. 8(2): 84-90(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Srinivasan 1992]
...
[Srinivasan & Carey 1991]
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
[Srinivasan & Carey 1992]
V. Srinivasan, Michael J. Carey: Compensation-Based On-Line Query Processing. SIGMOD Conference 1992: 331-340 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tay 1984]
...
[Yao 1978]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:34:24 2010 by Michael Ley (ley@uni-trier.de)