Performance of B+ Tree Concurrency Algorithms.

@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

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

Online Paper

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

ACM SIGMOD Anthology

• 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/An4-1 or /cdrom

• 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/aDVD2 or /dvd

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) BibTeX

[Bayer & McCreight 1972]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[Bayer & Schkolnick 1977]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX

[Biliris 1985]

...

[Biliris 1987]

Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169 BibTeX

[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) BibTeX

[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 BibTeX

[Comer 1979]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[Franaszek & Robinson 1985]

Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) BibTeX

[Goodman & Shasha 1985]

Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19 BibTeX

[Gray 1979]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[Guibas & Sedgewick 1978]

Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 BibTeX

[Johnson & Shasha 1989]

Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246 BibTeX

[Johnson & Shasha 1990]

Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287 BibTeX

[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) BibTeX

[Kung & Lehman 1980]

H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX

[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) BibTeX

[Lanin & Shasha 1986]

Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 BibTeX

[Lausen 1984]

Georg Lausen: Integrated Concurrency Control in Shared B-Trees. Computing 33(1): 13-26(1984) BibTeX

[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) BibTeX

[Livny 1990]

...

[Lomet & Salzberg 1992]

David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 BibTeX

[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 BibTeX

[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 BibTeX

[Mond & Raz 1985]

Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 BibTeX

[Sagiv 1985]

Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX

[Samadi 1976]

Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX

[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) BibTeX

[Srinivasan 1992]

...

[Srinivasan & Carey 1991]

V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425 BibTeX

[Srinivasan & Carey 1992]

V. Srinivasan, Michael J. Carey: Compensation-Based On-Line Query Processing. SIGMOD Conference 1992: 331-340 BibTeX

[Tay 1984]

...

[Yao 1978]

Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

1. Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim: A Restructuring Method for the Concurrent B⁺-Tree Based on Semantic Consistency. DASFAA 1999: 229-236
2. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)