Performance of B-Tree Concurrency Control Algorithms

Summary: Simulation-based study of B-tree concurrency control in a centralized DBMS. B-link algorithms yield highest concurrency and best throughput; updater-lock-coupled exclusive locks underperform vs. optimistic index descent under varied contention. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfb42f912f13d5471
Venue: SIGMOD
Year: 1991
Pagerank: 9.8570044e-05
Overall Rank: 1,692 | 88.63%
DOI: 10.1145/115790.115860

Incoming Non-self Citations Over Time

Authors

1. V. Srinivasan (University of Wisconsin)
2. Michael J. Carey (University of Wisconsin)

BibTeX Citation

@inproceedings{srinivasan_sigmod91,
        title = {{Performance of B-Tree Concurrency Control Algorithms}},
        author = {Srinivasan, V. and Carey, Michael J.},
        series = {{SIGMOD} '91},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/115790.115860},
        url = {https://dl.acm.org/doi/10.1145/115790.115860},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,855	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.4973014e-05
2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0942902e-05
2,263	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.7304715e-05
3,111	High-Concurrency Locking in R-Trees	1995	VLDB	7.6374094e-05
3,170	Access Method Concurrency with Recovery	1992	SIGMOD	7.5691807e-05
4,362	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.6380763e-05
7,454	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5230036e-05
7,584	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4903974e-05
7,816	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4481832e-05
7,974	Concurrent Log-Structured Memory for Many-Core Key-Value Stores	2018	VLDB	5.41489e-05
10,315	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0377739e-05
13,294	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB	4.9793485e-05
13,370	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
268	Models for Studying Concurrency Control Performance: Alternatives and Implications	1985	SIGMOD	0.00022673125
471	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.0001769727
2,471	Concurrency Control in B+-Trees Databases Using Preparatory Operations	1985	VLDB	8.4135005e-05
2,575	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.2761608e-05
2,791	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.009544e-05
5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0475065e-05
7,164	Operation Specific Locking In B-Trees	1987	PODS	5.5954112e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,904	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
2	3,111	High-Concurrency Locking in R-Trees	1995	VLDB
3	471	Concurrent Operations on B-Trees with Overtaking	1985	PODS
4	2,297	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,164	Operation Specific Locking In B-Trees	1987	PODS
6	2,973	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	13,465	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,294	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB
9	13,326	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
10	5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS