Database Paper Browser

Back to papers

Building a Bw-Tree Takes More Than Just Buzz Words

Summary: Provides the missing guide to building a lock-free Bw-Tree by clarifying Microsoft's design gaps and proposing optimization techniques for future lock-free in-memory structures. Evaluation shows 1.1-2.5x throughput gains over the original Bw-Tree for highly concurrent workloads, but lock-based structures still outperform it. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5541
Venue
SIGMOD
Year
2018
Pagerank
8.9001843e-05
Overall Rank
2,394 | 83.35%
DOI
10.1145/3183713.3196895

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
857 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015882892
1,087 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00014162909
2,369 Aria: A Fast and Practical Deterministic OLTP Database 2020 VLDB 8.9490403e-05
2,905 Teseo and the Analysis of Structural Dynamic Graphs 2021 VLDB 7.9352789e-05
4,128 Are Updatable Learned Indexes Ready? 2022 VLDB 6.4292373e-05
4,544 ScaleStore: A Fast and Cost-Efficient Storage Engine using DRAM, NVMe, and RDMA 2022 SIGMOD 6.1000636e-05
4,583 Virtual-Memory Assisted Buffer Management 2023 SIGMOD 6.0676378e-05
5,748 MxTasks: How to Make Efficient Synchronization and Prefetching Easy 2021 SIGMOD 5.341943e-05
5,768 Epoch-based Commit and Replication in Distributed OLTP Databases 2021 VLDB 5.3333911e-05
5,835 Order-Preserving Key Compression for In-Memory Search Trees 2020 SIGMOD 5.30905e-05
6,316 HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication 2020 VLDB 5.1141977e-05
6,460 Toward a Better Understanding and Evaluation of Tree Structures on Flash SSDs 2021 VLDB 5.0554178e-05
6,574 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.0055505e-05
6,666 Mainlining Databases: Supporting Fast Transactional Workloads on Universal Columnar Data File Formats 2021 VLDB 4.9691571e-05
6,741 DEX: Scalable Range Indexing on Disaggregated Memory 2024 VLDB 4.9432931e-05
6,840 LeanStore: A High-Performance Storage Engine for NVMe SSDs 2024 VLDB 4.9109345e-05
7,106 Revisiting the Design of LSM-tree Based OLTP Storage Engine with Persistent Memory 2021 VLDB 4.8300429e-05
7,142 Everything is a Transaction: Unifying Logical Concurrency Control and Physical Data Structure Maintenance in Database Management Systems 2021 CIDR 4.8197508e-05
7,154 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.815267e-05
7,831 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6387445e-05
7,995 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6109825e-05
8,258 Index Checkpoints for Instant Recovery in In-Memory Database Systems 2022 VLDB 4.5487249e-05
8,655 Adaptive Hybrid Indexes 2022 SIGMOD 4.4739554e-05
9,362 FluidKV: Seamlessly Bridging the Gap between Indexing Performance and Memory-Footprint on Ultra-Fast Storage 2024 VLDB 4.3503444e-05
9,363 BonsaiKV: Towards Fast, Scalable, and Persistent Key-Value Stores with Tiered, Heterogeneous Memory System 2024 VLDB 4.3503444e-05
9,454 OptiQL: Robust Optimistic Locking for Memory-Optimized Indexes 2023 SIGMOD 4.3391522e-05
9,745 GTX: A Write-Optimized Latch-free Graph Data System with Transactional Support 2025 SIGMOD 4.2897489e-05
9,949 AB-tree: Index for Concurrent Random Sampling and Updates 2022 VLDB 4.2421586e-05
10,063 Counting Is All You Need for Instant Tuple Discovery: Enabling Real-Time HTAP in Standalone DBMSs 2026 SIGMOD 4.1945683e-05
10,105 RABIT: Efficient Range Queries with Bitmap Indexing 2026 SIGMOD 4.1945683e-05
10,190 P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction 2026 SIGMOD 4.1945683e-05
10,193 Predictive Translation: High-Performance Buffer Management Without the Trade-Offs 2026 SIGMOD 4.1945683e-05
10,257 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.1945683e-05
10,319 LiBox: A Learned Index as an Array to Minimize Last-Mile Search 2026 VLDB 4.1945683e-05
10,368 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 4.1945683e-05
10,562 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1945683e-05
10,583 Tabular: Efficiently Building Efficient Indexes 2025 VLDB 4.1945683e-05
11,007 Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives 2024 VLDB 4.1945683e-05
11,229 Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
763 FOEDUS: OLTP Engine for a Thousand Cores and NVRAM 2015 SIGMOD 0.00017025851
1,036 ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads 2016 SIGMOD 0.0001452166
1,069 Cicada: Dependably Fast Multi-Core In-Memory Transactions 2017 SIGMOD 0.00014319266
1,312 Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes 2016 SIGMOD 0.00012652548
1,457 High Performance Transactions in Deuteronomy 2015 CIDR 0.00011897016
1,780 LLAMA: A Cache/Storage Subsystem for Modern Hardware 2013 VLDB 0.00010580669
2,244 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2097912e-05
3,826 To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing 2015 VLDB 6.7250243e-05
4,386 Indexing on Modern Hardware: Hekaton and Beyond 2014 SIGMOD 6.2320098e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,239 A Framework for the Performance Analysis of Concurrent B-tree Algorithms 1990 PODS 5.6106291e-05
12,843 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB 4.1945683e-05
8,642 Automatic Workload Driven Index Defragmentation 2011 VLDB 4.4785896e-05
1,573 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD 0.00011295081
7,995 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6109825e-05
7,154 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.815267e-05
10,562 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1945683e-05
1,405 BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory 2018 VLDB 0.00012174592
3,826 To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing 2015 VLDB 6.7250243e-05
4,386 Indexing on Modern Hardware: Hekaton and Beyond 2014 SIGMOD 6.2320098e-05