ACM SIGMOD Anthology TODS dblp.uni-trier.de

The Performance of Current B-Tree Algorithms.

Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
@article{DBLP:journals/tods/JohnsonS93,
  author    = {Theodore Johnson and
               Dennis Shasha},
  title     = {The Performance of Current B-Tree Algorithms},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {1},
  year      = {1993},
  pages     = {51-101},
  ee        = {http://doi.acm.org/10.1145/151284.151286, db/journals/tods/JohnsonS93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Many concurrent B-tree algorithms have been proposed, but their performances have not yet been analyzed satisfactorily. When transaction processing systems require high levels of concurrency, a restrictive serialization technique on the B-tree index can cause a bottleneck. In this paper we present a framework for constructing analytical performance models of concurrent B-tree algorithms. The models can predict the response time and maximum throughput. We analyze a variety of locking algorithms including naive lock-coupling, optimistic descent, two-phase locking, and the Lehman-Yao algorithm. The analyses are validated by simulations of the algorithms on actual B-trees, as well as by simulations done by other researchers. We find that the Lehman-Yao algorithm has the best performance by far, that the performance of two-phase locking is limited, and that the response time of two-phase locking has a high variance. Simple and instructive rules of thumb for predicting performance are also derived. We apply the analyses to determine the effect of database recovery on B-tree concurrency. We find that holding nonleaf locks for recovery purposes significantly reduces performance.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Index Terms and Review]
[Full Text in PDF Format, 2802 KB]

References

[1]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[2]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[3]
...
[4]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[5]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[6]
...
[7]
...
[8]
Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169 BibTeX
[9]
Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX
[10]
...
[11]
Ronald Fagin: Asymptotic Miss Ratios over Independent References. J. Comput. Syst. Sci. 14(2): 222-250(1977) BibTeX
[12]
...
[13]
...
[14]
Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19 BibTeX
[15]
Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 BibTeX
[16]
Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX
[17]
Theodore Johnson: Approximate Analysis of Reader and Writer Access to a Shared Resource. SIGMETRICS 1990: 106-114 BibTeX
[18]
...
[19]
...
[20]
Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246 BibTeX
[21]
Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287 BibTeX
[22]
Theodore Johnson, Dennis Shasha: B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half. J. Comput. Syst. Sci. 47(1): 45-76(1993) BibTeX
[23]
Martin L. Kersten, Hans Tebra: Application of an Optimistic Concurrency Control Method. Softw., Pract. Exper. 14(2): 153-168(1984) BibTeX
[24]
...
[25]
...
[26]
...
[27]
...
[28]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[29]
Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX
[30]
Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 BibTeX
[31]
Georg Lausen: Integrated Concurrency Control in Shared B-Trees. Computing 33(1): 13-26(1984) BibTeX
[32]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[33]
...
[34]
...
[35]
...
[36]
C. Mohan, Frank Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 BibTeX
[37]
Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 BibTeX
[38]
In Kyung Ryu, Alexander Thomasian: Performance Analysis of Centralized Databases with Optimistic Concurrency Control. Perform. Eval. 7(3): 195-211(1987) BibTeX
[39]
Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX
[40]
Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX
[41]
Dennis Shasha: What Good are Concurrent Search Structure Algorithms for databases Anyway? IEEE Database Eng. Bull. 8(2): 84-90(1985) BibTeX
[42]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
[43]
...
[44]
Jeffrey R. Spirn, Shalom Tsur: Memory Management for B-Trees. Perform. Eval. 4: 159-174(1985) BibTeX
[45]
V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425 BibTeX
[46]
...
[47]
Y. C. Tay, Nathan Goodman, Rajan Suri: Locking Performance in Centralized Databases. ACM Trans. Database Syst. 10(4): 415-462(1985) BibTeX
[48]
...
[49]
...

Referenced by

  1. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  2. Vigyan Singhal, Alan Jay Smith: Analysis of Locking Behavior in Three Real Database Systems. VLDB J. 6(1): 40-52(1997)
  3. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
  4. Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:14 2008