Bw-tree
The Bw-tree is a B+ tree design that uses a page mapping table and immutable delta chains to install node changes with atomic compare-and-swap.
Updates: Logical page identifiers survive relocation. A writer links a delta to the observed head and compares that head when publishing; a competing change can force a retry. [1]
Consolidation: A replacement base page incorporates a captured chain. Installation must still validate its head; a stale replacement is discarded. Retired storage cannot be reused while protected readers may access it. [1]
Scan boundary: The 2013 design makes individual next-record operations atomic, not the whole scan. Its index and log-structured storage layers are distinct; pointer publication alone is not durability. [1]
Physical order: OpenBw-Tree preallocates delta space, but allocation order can differ from chain-publication order. Readers must follow links, not assume address order reconstructs history. [2]
Performance: The 2018 in-memory study identifies allocation, indirection, traversal and epoch-accounting costs. Its comparisons do not establish a universal lock-free speed advantage or SSD endurance result. [2]
Executable example: Six event orderings cover one writer and one consolidation. Guarded publication retains the accepted update in all six; an intentionally unchecked replacement loses it in two. These are model cases, not failure probabilities or native Bw-tree defects. [3] [4]
Stable-log boundary: With a transactional log, consolidation and flushing require LSN <= ESL; newer deltas remain separable. [1] ESL/EOSL covers a gap-free prefix, not the largest logged LSN: physical log order may differ. [5] RSSP acknowledgement instead requires every earlier update durable. [1]
Relations
- related
- B-tree, B+ tree, B-link tree, LLAMA
Limitations
- The example excludes splits, merges, memory reclamation, weak-memory ordering, I/O and crashes; it is not a complete concurrency or recovery proof. [3]
- The stable-log model reconstructs durable operations, not committed transactions; it excludes undo, RSSP truncation and actual power-loss behavior. [6, 5]
Citations
- Levandoski, Lomet and Sengupta. The Bw-Tree: A B-tree for New Hardware Platforms. ICDE 2013; sections II, III.A-D and V.A. DOI: 10.1109/ICDE.2013.6544834.
- Wang et al. Building a Bw-Tree Takes More Than Just Buzz Words. SIGMOD 2018, pp. 473-488, sections 3-6. DOI: 10.1145/3183713.3196895.
- Hesela: bounded consolidation-publication model and executable negative control (Node.js; no dependencies).
- Hesela: all six modeled interleavings, guarded and intentionally unchecked outcomes.
- Levandoski, Lomet, Mokbel and Zhao. Deuteronomy: Transaction Support for Cloud Data. CIDR 2011, pp. 123-133, sections 4.5-4.5.2 and 5.1.
- Hesela: stable-log eligibility and abstract recovery model; executable Node.js source.
- Hesela: 45 stable-log model cases with guarded and intentionally unchecked outcomes.
Sources & caveats
- Primary-paper comparison plus a deterministic teaching model; no native Bw-tree execution, hardware benchmark or crash experiment was performed.
- The model's accepted update means successful in-memory publication, not durable database commit.
- The 2018 baseline is a good-faith reconstruction of Microsoft's proposed design, not its private engine; OpenBw-Tree is the study's optimized implementation.
- The separate 45-case model covers log holes, delayed notifications, overwrites, deletion and reinsertion. Eligible state plus replay is checked against a per-key oracle. [6] [7]
- The unchecked variant preserves the memory view but can persist an unlogged update. The examples are abstract operation reconstruction, not native crash tests or committed-transaction recovery. [6]