Framework for the performance analysis of concurrent B-tree algorithms

Theodore Johnson, Dennis Shasha

Research output: Contribution to conferencePaper

Abstract

Many concurrent B-tree algorithms have been proposed, but they have not yet been satisfactorily analyzed. 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 three algorithms: Naieve Lock-coupling, Optimistic Descent, and the Lehman-Yao algorithm. The analyses are validated by simulations of the algorithms on actual B-trees. 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.

Original languageEnglish (US)
Pages273-287
Number of pages15
StatePublished - Apr 1990
EventProceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - Nashville, TN, USA
Duration: Apr 2 1990Apr 4 1990

Other

OtherProceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
CityNashville, TN, USA
Period4/2/904/4/90

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Framework for the performance analysis of concurrent B-tree algorithms'. Together they form a unique fingerprint.

  • Cite this

    Johnson, T., & Shasha, D. (1990). Framework for the performance analysis of concurrent B-tree algorithms. 273-287. Paper presented at Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, TN, USA, .