DBScholar

Back to papers

PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors

Summary: PALM replaces latch-based B+ tree concurrency with BSP-style, staged atomic batches and point-to-point synchronization, eliminating races and contention. It exploits many-core parallelism to deliver 2.3–19× higher update throughput with sub-350 μs latency. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
10499
Venue
VLDB
Year
2011
Pagerank
9.6765747e-05
Overall Rank
1,822 | 87.51%
DOI
10.14778/3402707.3402712

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{sewall_vldb11,
        title = {{PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors}},
        author = {Sewall, Jason and Chhugani, Jatin and Kim, Changkyu and Satish, Nadathur and Dubey, Pradeep},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {795--806},
        doi = {10.14778/3402707.3402712},
        url = {https://doi.org/10.14778/3402707.3402712},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
1,461 LLAMA: A Cache/Storage Subsystem for Modern Hardware 2013 VLDB 0.00010703712
2,309 A Scalable Lock Manager for Multicores 2013 SIGMOD 8.7691698e-05
3,256 To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing 2015 VLDB 7.591263e-05
3,378 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.4587887e-05
4,090 The bionic DBMS is coming, but what will it look like? 2013 CIDR 6.9096664e-05
4,296 Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold? 2017 CIDR 6.7773228e-05
5,823 HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication 2020 VLDB 6.0752299e-05
5,954 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD 6.0292226e-05
6,012 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 6.0102675e-05
6,710 PIM-tree: A Skew-resistant Index for Processing-in-Memory 2023 VLDB 5.796491e-05
7,996 When Database Meets New Storage Devices: Understanding and Exposing Performance Mismatches via Configurations 2023 VLDB 5.5096162e-05
9,498 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.2606222e-05
10,829 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
3 Pregel: A System for Large-Scale Graph Processing 2010 SIGMOD 0.0012250108
67 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00038461275
105 Quickly Generating Billion-Record Synthetic Databases 1994 SIGMOD 0.00033877899
204 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00025342994
278 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022476841
632 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00015575286
678 Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort 2010 SIGMOD 0.00015061068
712 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.0001468812
966 A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database 2009 SIGMOD 0.00012920281
1,110 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00012140661
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,394 A Case for Staged Database Systems 2003 CIDR 8.6362653e-05
2,679 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.2675008e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,710 Mining Tree-Structured Data on Multicore Systems 2009 VLDB
2 10,824 Efficient Concurrent Updates to Persistent Randomized Binary Search Trees 2025 VLDB
3 1,710 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB
4 10,829 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB
5 948 BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory 2018 VLDB
6 5,993 NBTree: a Lock-free PM-friendly Persistent B+-Tree for eADR-enabled PM Systems 2022 VLDB
7 5,530 A Framework for the Performance Analysis of Concurrent B-tree Algorithms 1990 PODS
8 1,663 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD
9 13,036 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB
10 10,568 Operation-Aware Hybrid Locking for Modern In-Memory Indexes 2026 VLDB