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
716
Venue
PODS
Year
1985
Pagerank
0.00018055592
Overall Rank
464 | 96.82%
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
214 ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes 1990 VLDB 0.00024680756
958 ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging 1992 SIGMOD 0.00012956148
1,663 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD 0.00010073735
1,710 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.9537123e-05
2,001 A Practical Scalable Distributed B-Tree 2008 VLDB 9.3326014e-05
2,212 Sherman: A Write-Optimized Distributed B+Tree Index on Disaggregated Memory 2022 SIGMOD 8.9411432e-05
2,227 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.9111106e-05
2,257 Concurrency Control of Nested Transactions Accessing B-Trees 1989 PODS 8.8573263e-05
2,605 Lazy Updates for Distributed Search Structure 1993 SIGMOD 8.3494816e-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
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
10,093 AB-tree: Index for Concurrent Random Sampling and Updates 2022 VLDB 5.1530576e-05
12,955 Highly Concurrent Cache Consistency for Indices in Client-Server Database Systems 1997 SIGMOD 5.093636e-05
13,004 Index Concurrency Control in Firm Real-Time DBMS 1995 VLDB 5.093636e-05
13,036 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB 5.093636e-05
13,147 Concurrent Set Manipulation Without Locking 1988 PODS 5.093636e-05
13,175 Concurrency Control in Database Structures with Relaxed Balance 1987 PODS 5.093636e-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,246 Compact B-Trees 1979 SIGMOD
2 2,968 On-line Reorganization of Sparsely-populated B+-trees 1996 SIGMOD
3 13,175 Concurrency Control in Database Structures with Relaxed Balance 1987 PODS
4 9,518 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD
5 4,783 Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms 1984 PODS
6 14,548 On B-Trees: Routing Schemes And Concurrency 1980 SIGMOD
7 7,026 Operation Specific Locking In B-Trees 1987 PODS
8 5,530 A Framework for the Performance Analysis of Concurrent B-tree Algorithms 1990 PODS
9 1,663 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD
10 13,036 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB