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.8555388e-05
Overall Rank: 1,691 | 88.64%
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,857	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.4935317e-05
2,065	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0904572e-05
2,265	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.7267108e-05
3,113	High-Concurrency Locking in R-Trees	1995	VLDB	7.633977e-05
3,170	Access Method Concurrency with Recovery	1992	SIGMOD	7.5681486e-05
4,364	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.6349342e-05
7,458	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5203926e-05
7,498	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.5078165e-05
7,590	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4877983e-05
7,978	Concurrent Log-Structured Memory for Many-Core Key-Value Stores	2018	VLDB	5.412355e-05
10,317	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0363234e-05
13,300	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB	4.9769913e-05
13,376	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS	4.9769913e-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.00022664149
472	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.0001769063
2,473	Concurrency Control in B+-Trees Databases Using Preparatory Operations	1985	VLDB	8.4097527e-05
2,575	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.2725628e-05
2,791	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.0061967e-05
5,662	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0448437e-05
7,166	Operation Specific Locking In B-Trees	1987	PODS	5.5929625e-05

Semantically Similar Papers

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