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.8232497e-05
Overall Rank: 1,698 | 88.62%
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,865	PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors	2011	VLDB	9.4644494e-05
2,076	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0622765e-05
2,279	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6989205e-05
3,121	High-Concurrency Locking in R-Trees	1995	VLDB	7.6094637e-05
3,180	Access Method Concurrency with Recovery	1992	SIGMOD	7.5432668e-05
4,387	Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?	2017	CIDR	6.6129973e-05
7,477	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5022037e-05
7,516	B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	5.4896042e-05
7,607	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4696523e-05
7,993	Concurrent Log-Structured Memory for Many-Core Key-Value Stores	2018	VLDB	5.3946213e-05
10,345	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0197268e-05
13,341	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB	4.9605343e-05
13,417	Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking	1992	PODS	4.9605343e-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
270	Models for Studying Concurrency Control Performance: Alternatives and Implications	1985	SIGMOD	0.00022604714
475	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00017634372
2,484	Concurrency Control in B+-Trees Databases Using Preparatory Operations	1985	VLDB	8.381967e-05
2,582	Semantically-based Concurrency Control for Search Structures	1985	PODS	8.2453579e-05
2,798	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	7.9830986e-05
5,675	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0248757e-05
7,187	Operation Specific Locking In B-Trees	1987	PODS	5.5744874e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,929	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
2	3,121	High-Concurrency Locking in R-Trees	1995	VLDB
3	475	Concurrent Operations on B-Trees with Overtaking	1985	PODS
4	2,311	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,187	Operation Specific Locking In B-Trees	1987	PODS
6	2,983	The Performance of Concurrency Control Algorithms for Database Management Systems	1984	VLDB
7	13,512	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,341	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB
9	13,373	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
10	5,675	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS