A Framework for the Performance Analysis of Concurrent B-tree Algorithms

Summary: Framework to analytically model concurrent B-tree algorithms' response time and throughput, validated by simulations on real B-trees. Evaluates Naive lock‑coupling, Optimistic Descent, Lehman–Yao; gives practical rules‑of‑thumb and quantifies recovery's concurrency cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 907
Venue: PODS
Year: 1990
Pagerank: 6.1856695e-05
Overall Rank: 5,530 | 62.07%
DOI: 10.1145/298514.298580

Incoming Non-self Citations Over Time

Authors

1. Theodore Johnson (New York University)
2. Dennis Shasha (New York University)

BibTeX Citation

@inproceedings{johnson_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{A Framework for the Performance Analysis of Concurrent B-tree Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/298514.298580},
        doi = {10.1145/298514.298580},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Johnson, Theodore and Shasha, Dennis},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00010073735
2,605	Lazy Updates for Distributed Search Structure	1993	SIGMOD	8.3494816e-05
7,804	Online B-Tree Merging	2005	SIGMOD	5.5415082e-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 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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,738	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.1875737e-05

Semantically Similar Papers

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