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)
Incoming Non-self Citations Over Time
Authors
- 1. Ziqi Wang (Carnegie Mellon University)
- 2. Andrew Pavlo (Carnegie Mellon University)
- 3. Hyeontaek Lim (Carnegie Mellon University)
- 4. Viktor Leis (Technical University of Munich)
- 5. Huanchen Zhang (Carnegie Mellon University)
- 6. Michael Kaminsky (Intel)
- 7. David G. Andersen (Carnegie Mellon University)
BibTeX Citation
@inproceedings{wang_sigmod18,
title = {{Building a Bw-Tree Takes More Than Just Buzz Words}},
author = {Wang, Ziqi and Pavlo, Andrew and Lim, Hyeontaek and Leis, Viktor and Zhang, Huanchen and Kaminsky, Michael and Andersen, David G.},
series = {{SIGMOD} '18},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3183713.3196895},
url = {https://dl.acm.org/doi/10.1145/3183713.3196895},
year = {2018}
}Incoming Citations (Sorted by Pagerank)
Showing 47 of 47 citing papers.
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 |
|---|---|---|---|---|
| 542 | FOEDUS: OLTP Engine for a Thousand Cores and NVRAM | 2015 | SIGMOD | 0.00016620527 |
| 636 | ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads | 2016 | SIGMOD | 0.00015329098 |
| 773 | Cicada: Dependably Fast Multi-Core In-Memory Transactions | 2017 | SIGMOD | 0.00014075557 |
| 964 | Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes | 2016 | SIGMOD | 0.00012798312 |
| 1,085 | High Performance Transactions in Deuteronomy | 2015 | CIDR | 0.00012086316 |
| 1,402 | LLAMA: A Cache/Storage Subsystem for Modern Hardware | 2013 | VLDB | 0.00010754882 |
| 1,724 | Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems | 2001 | VLDB | 9.7779713e-05 |
| 3,309 | To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing | 2015 | VLDB | 7.4176874e-05 |
| 4,087 | Indexing on Modern Hardware: Hekaton and Beyond | 2014 | SIGMOD | 6.7974724e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,675 | A Framework for the Performance Analysis of Concurrent B-tree Algorithms | 1990 | PODS |
| 2 | 13,373 | New Concurrency Control Algorithms for Accessing and Compacting B-Trees | 1994 | VLDB |
| 3 | 8,812 | Automatic Workload Driven Index Defragmentation | 2011 | VLDB |
| 4 | 1,698 | Performance of B-Tree Concurrency Control Algorithms | 1991 | SIGMOD |
| 5 | 7,049 | BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees | 2023 | VLDB |
| 6 | 6,500 | Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index | 2024 | VLDB |
| 7 | 11,301 | FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update | 2025 | VLDB |
| 8 | 967 | BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory | 2018 | VLDB |
| 9 | 3,309 | To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing | 2015 | VLDB |
| 10 | 4,087 | Indexing on Modern Hardware: Hekaton and Beyond | 2014 | SIGMOD |