dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Performance of B-Tree Concurrency Algorithms.

V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
@inproceedings{DBLP:conf/sigmod/SrinivasanC91,
  author    = {V. Srinivasan and
               Michael J. Carey},
  editor    = {James Clifford and
               Roger King},
  title     = {Performance of B-Tree Concurrency Algorithms},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {416-425},
  ee        = {http://doi.acm.org/10.1145/115790.115860},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A number of algorithms have been proposed for accessing B-trees concurrently, but the performance of these algorithms is not yet well understood. In this paper, we study the performance of various concurrency control algorithms using a detailed simulation model of B-tree operations in a centralized DBMS. Our study considers a wide range of data contention situations and resource conditions. Results from our experiments indicate that algorithms in which updaters lock-couple using exclusive locks perform poorly as compared to those that permit more optimistic index descents. In particular, the B-link algorithms provide the most concurrency and the best overall performance.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1060 KB]

References

[Agra87]
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
[Baye77]
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
[Bili85]
...
[Bili87]
Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Care84]
...
[Come79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Good85]
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
[Gary79]
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
[Guib78]
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
[John89]
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
[John90]
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
[John91]
...
[Kell88]
Arthur M. Keller, Gio Wiederhold: Concurrent Use of B-trees with Variable-Length Entries. SIGMOD Record 17(2): 89-90(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kwon82]
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
[Lani86]
Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lehm81]
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
[Livn90]
...
[Mill78]
...
[Moha89]
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
[Mond85]
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
[Sagi85]
Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sama76]
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
[Shas85]
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
[Srin91]
...
[Weih90]
...
[Yao78]
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

Last update Tue Sep 18 00:25:06 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page