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: 2612
Venue: SIGMOD
Year: 1991
Pagerank: 0.00010073735
Overall Rank: 1,663 | 88.60%
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,822	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.6765747e-05
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,227	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.9111106e-05
3,057	High-Concurrency Locking in R-Trees	1995	VLDB	7.807389e-05
3,114	Access Method Concurrency with Recovery	1992	SIGMOD	7.7405805e-05
4,296	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.7773228e-05
7,310	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.6494751e-05
7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.6111155e-05
7,821	Concurrent Log-Structured Memory for Many-Core Key-Value Stores	2018	VLDB	5.5373067e-05
8,255	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4574671e-05
10,093	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.1530576e-05
13,004	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB	5.093636e-05
13,080	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS	5.093636e-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
260	Models for Studying Concurrency Control Performance: Alternatives and Implications	1985	SIGMOD	0.00023103999
464	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00018055592
2,418	Concurrency Control in B+-Trees Databases Using Preparatory Operations	1985	VLDB	8.6059055e-05
2,526	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.463742e-05
2,738	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.1875737e-05
5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.1856695e-05
7,026	Operation Specific Locking In B-Trees	1987	PODS	5.7232444e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
2	3,057	High-Concurrency Locking in R-Trees	1995	VLDB
3	464	Concurrent Operations on B-Trees with Overtaking	1985	PODS
4	2,257	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,026	Operation Specific Locking In B-Trees	1987	PODS
6	2,911	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,004	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB
9	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
10	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS