DBScholar

Back to papers

Concurrent Operations on B-Trees with Overtaking

Summary: Presents concurrent B-tree algorithms that reduce updater locking to a single node (vs. 2–3 in LY), lowering contention during searches/inserts. Also introduces a concurrent compression/merge triggered on underflow deletions, with each compression locking up to three nodes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
ha07801716bd3f68f
Venue
PODS
Year
1985
Pagerank
0.0001769727
Overall Rank
471 | 96.84%
DOI
10.1145/325405.325409

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sagiv_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{Concurrent Operations on B-Trees with Overtaking}},
        url = {https://dl.acm.org/doi/10.1145/325405.325409},
        doi = {10.1145/325405.325409},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sagiv, Yehoshua},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
221 ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes 1990 VLDB 0.00024274803
983 ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging 1992 SIGMOD 0.00012706526
1,692 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD 9.8570044e-05
1,717 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.8016891e-05
1,966 Sherman: A Write-Optimized Distributed B+Tree Index on Disaggregated Memory 2022 SIGMOD 9.3039057e-05
2,015 A Practical Scalable Distributed B-Tree 2008 VLDB 9.1820621e-05
2,263 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.7304715e-05
2,297 Concurrency Control of Nested Transactions Accessing B-Trees 1989 PODS 8.6774814e-05
2,658 Lazy Updates for Distributed Search Structure 1993 SIGMOD 8.1636113e-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
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
10,315 AB-tree: Index for Concurrent Random Sampling and Updates 2022 VLDB 5.0377739e-05
13,245 Highly Concurrent Cache Consistency for Indices in Client-Server Database Systems 1997 SIGMOD 4.9793485e-05
13,294 Index Concurrency Control in Firm Real-Time DBMS 1995 VLDB 4.9793485e-05
13,326 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB 4.9793485e-05
13,437 Concurrent Set Manipulation Without Locking 1988 PODS 4.9793485e-05
13,465 Concurrency Control in Database Structures with Relaxed Balance 1987 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank Cited Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,376 Compact B-Trees 1979 SIGMOD
2 3,025 On-line Reorganization of Sparsely-populated B+-trees 1996 SIGMOD
3 13,465 Concurrency Control in Database Structures with Relaxed Balance 1987 PODS
4 9,699 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD
5 4,904 Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms 1984 PODS
6 14,846 On B-Trees: Routing Schemes And Concurrency 1980 SIGMOD
7 7,164 Operation Specific Locking In B-Trees 1987 PODS
8 5,661 A Framework for the Performance Analysis of Concurrent B-tree Algorithms 1990 PODS
9 1,692 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD
10 13,326 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB