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
5542
Venue
SIGMOD
Year
2018
Pagerank
9.0546844e-05
Overall Rank
2,313 | 83.93%
DOI
10.1145/3183713.3196895

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
844 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015964123
1,085 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00014173956
2,370 Aria: A Fast and Practical Deterministic OLTP Database 2020 VLDB 8.9457118e-05
2,910 Teseo and the Analysis of Structural Dynamic Graphs 2021 VLDB 7.9276339e-05
4,056 Are Updatable Learned Indexes Ready? 2022 VLDB 6.4905689e-05
4,523 ScaleStore: A Fast and Cost-Efficient Storage Engine using DRAM, NVMe, and RDMA 2022 SIGMOD 6.1102901e-05
4,579 Virtual-Memory Assisted Buffer Management 2023 SIGMOD 6.0651118e-05
5,760 MxTasks: How to Make Efficient Synchronization and Prefetching Easy 2021 SIGMOD 5.3369902e-05
5,776 Epoch-based Commit and Replication in Distributed OLTP Databases 2021 VLDB 5.328271e-05
5,847 Order-Preserving Key Compression for In-Memory Search Trees 2020 SIGMOD 5.3040014e-05
6,314 HydraList: A Scalable In-Memory Index Using Asynchronous Updates and Partial Replication 2020 VLDB 5.1108651e-05
6,456 Toward a Better Understanding and Evaluation of Tree Structures on Flash SSDs 2021 VLDB 5.0505636e-05
6,566 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.0030559e-05
6,668 Mainlining Databases: Supporting Fast Transactional Workloads on Universal Columnar Data File Formats 2021 VLDB 4.9647176e-05
6,742 DEX: Scalable Range Indexing on Disaggregated Memory 2024 VLDB 4.9385502e-05
6,838 LeanStore: A High-Performance Storage Engine for NVMe SSDs 2024 VLDB 4.906223e-05
7,092 Revisiting the Design of LSM-tree Based OLTP Storage Engine with Persistent Memory 2021 VLDB 4.83025e-05
7,140 Everything is a Transaction: Unifying Logical Concurrency Control and Physical Data Structure Maintenance in Database Management Systems 2021 CIDR 4.8153926e-05
7,152 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.8126591e-05
7,837 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6342964e-05
7,990 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6086117e-05
8,245 Index Checkpoints for Instant Recovery in In-Memory Database Systems 2022 VLDB 4.5463745e-05
8,595 OptiQL: Robust Optimistic Locking for Memory-Optimized Indexes 2023 SIGMOD 4.4844188e-05
8,653 Adaptive Hybrid Indexes 2022 SIGMOD 4.4696663e-05
9,370 FluidKV: Seamlessly Bridging the Gap between Indexing Performance and Memory-Footprint on Ultra-Fast Storage 2024 VLDB 4.3461752e-05
9,371 BonsaiKV: Towards Fast, Scalable, and Persistent Key-Value Stores with Tiered, Heterogeneous Memory System 2024 VLDB 4.3461752e-05
9,401 Tabular: Efficiently Building Efficient Indexes 2025 VLDB 4.3399748e-05
9,744 GTX: A Write-Optimized Latch-free Graph Data System with Transactional Support 2025 SIGMOD 4.2856385e-05
9,945 AB-tree: Index for Concurrent Random Sampling and Updates 2022 VLDB 4.240067e-05
10,063 Counting Is All You Need for Instant Tuple Discovery: Enabling Real-Time HTAP in Standalone DBMSs 2026 SIGMOD 4.1905499e-05
10,105 RABIT: Efficient Range Queries with Bitmap Indexing 2026 SIGMOD 4.1905499e-05
10,190 P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction 2026 SIGMOD 4.1905499e-05
10,193 Predictive Translation: High-Performance Buffer Management Without the Trade-Offs 2026 SIGMOD 4.1905499e-05
10,257 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.1905499e-05
10,281 Operation-Aware Hybrid Locking for Modern In-Memory Indexes 2026 VLDB 4.1905499e-05
10,331 LiBox: A Learned Index as an Array to Minimize Last-Mile Search 2026 VLDB 4.1905499e-05
10,380 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 4.1905499e-05
10,571 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1905499e-05
11,010 Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives 2024 VLDB 4.1905499e-05
11,231 Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 4.1905499e-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
756 FOEDUS: OLTP Engine for a Thousand Cores and NVRAM 2015 SIGMOD 0.00017079523
1,036 ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads 2016 SIGMOD 0.00014515226
1,066 Cicada: Dependably Fast Multi-Core In-Memory Transactions 2017 SIGMOD 0.00014340396
1,300 Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes 2016 SIGMOD 0.00012711153
1,447 High Performance Transactions in Deuteronomy 2015 CIDR 0.0001192999
1,772 LLAMA: A Cache/Storage Subsystem for Modern Hardware 2013 VLDB 0.00010603139
2,233 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2299873e-05
3,630 To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing 2015 VLDB 6.8989362e-05
4,363 Indexing on Modern Hardware: Hekaton and Beyond 2014 SIGMOD 6.2476591e-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.6060584e-05
12,852 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB 4.1905499e-05
8,640 Automatic Workload Driven Index Defragmentation 2011 VLDB 4.4743572e-05
1,573 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD 0.00011293832
7,990 BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees 2023 VLDB 4.6086117e-05
7,152 Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index 2024 VLDB 4.8126591e-05
10,571 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1905499e-05
1,306 BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory 2018 VLDB 0.00012674725
3,630 To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing 2015 VLDB 6.8989362e-05
4,363 Indexing on Modern Hardware: Hekaton and Beyond 2014 SIGMOD 6.2476591e-05