B-Epsilon Trees & Lock-Free NVMe Storage Engines: Technical Explainer

Introduction

Modern solid-state drives (SSDs) backed by Non-Volatile Memory Express (NVMe) deliver millions of I/O operations per second (IOPS) with sub-hundred-microsecond access latencies. However, traditional database storage engines fail to exploit these hardware capabilities. Classic $B^+$-trees incur severe write amplification and lock contention under random write workloads due to in-place page overwrites. Conversely, Log-Structured Merge (LSM) trees optimize write throughput at the cost of high point-lookup latency, read amplification, and background compaction stalls that degrade tail latency.

Bridging this gap requires a dual-paradigm architecture: a write-optimized fractal tree index combined with a lock-free, flash-aware page management layer. The $\mathcal{B}^\epsilon$-tree provides an optimal, mathematically parameterized balance between ingestion bandwidth and query latency. When paired with lock-free page mapping tables, pointer swizzling, and kernel-bypass asynchronous I/O (io_uring/SPDK), this architecture eliminates latch contention, minimizes write amplification, and fully saturates the internal parallelism of multi-queue NVMe devices.

Algorithmic Foundations of the $\mathcal{B}^\epsilon$-Tree

The $\mathcal{B}^\epsilon$-tree is a generalized write-optimized search tree defined over a tuning parameter $\epsilon \in [0, 1]$. It parameterizes the operational trade-off between the fast point reads of a $B^+$-tree ($\epsilon = 1$) and the high ingestion throughput of an LSM-tree or buffered repository tree ($\epsilon = 0$).

                      +-------------------------------+
                      | Node (Total Size: B)          |
                      | Pivots: B^ε | Buffer: B - B^ε |
                      +-------+---------------+-------+
                              |               |
               +--------------+               +---------------+
               v                                              v
      +-----------------+                            +-----------------+
      |  Child Node 1   |                            |  Child Node 2   |
      | Buffers/Pivots  |                            | Buffers/Pivots  |
      +-----------------+                            +-----------------+

Parameterization and Node Sizing

Let $B$ denote the maximum node size measured in key-value records (or raw bytes), and let $N$ represent the total number of records maintained in the storage engine.

Fanout (Pivots): An internal node maintains $B^\epsilon$ pivot keys and points to $B^\epsilon + 1$ child nodes.
Node Buffer: The remaining capacity of the internal node, sized at $B - B^\epsilon$, is allocated to an internal message buffer.
Tree Height: The height $h$ of a balanced $\mathcal{B}^\epsilon$-tree is given by:

$$h = \Theta\left(\log_{B^\epsilon} \left(\frac{N}{B}\right)\right) = \Theta\left(\frac{1}{\epsilon} \log_B N\right)$$

Asymptotic I/O Complexity

When an update (insert, update, or delete message) is ingested into the root node, it is appended to the root's local buffer. When this buffer fills to its capacity $B - B^\epsilon$, the storage engine flushes messages to the appropriate children.

Because the node contains $B^\epsilon$ child branches, routing messages evenly implies that, on average, a batch of:

$$\Delta = \frac{B - B^\epsilon}{B^\epsilon} = B^{1-\epsilon} - 1 = \Theta(B^{1-\epsilon})$$

messages is pushed down to a targeted child node within a single continuous disk I/O transaction. The amortized I/O cost per insertion across each level of the tree is therefore $\Theta(1 / B^{1-\epsilon})$. Multiplying this by the total tree height yields the global amortized insert I/O complexity:

$$\text{Cost}_{\text{insert}} = \Theta\left(\frac{1}{\epsilon B^{1-\epsilon}} \log_B N\right) \text{ I/Os}$$

Point queries must search the path from the root down to the target leaf, checking every intermediate buffer for overriding messages targeting the requested key. The point search cost matches the tree height:

$$\text{Cost}_{\text{point_query}} = \Theta\left(\frac{1}{\epsilon} \log_B N\right) \text{ I/Os}$$

Range queries over $s$ contiguous records take:

$$\text{Cost}_{\text{range_query}} = \Theta\left(\frac{1}{\epsilon} \log_B N + \frac{s}{B}\right) \text{ I/Os}$$

Comparative Asymptotic Bounds

Structure	Amortized Insert Complexity	Point Query Complexity	Range Query Complexity ($s$ items)
$B^+$-Tree	$\Theta(\log_B N)$	$\Theta(\log_B N)$	$\Theta(\log_B N + \frac{s}{B})$
LSM-Tree (Size ratio $T$)	$\Theta(\frac{1}{B} \log_T N)$	$\Theta(L \cdot \log_B N)$	$\Theta(L \cdot \log_B N + \frac{s}{B})$
$\mathcal{B}^\epsilon$-Tree ($\epsilon = 0.5$)	$\Theta(\frac{1}{\sqrt{B}} \log_B N)$	$\Theta(2 \log_B N)$	$\Theta(2 \log_B N + \frac{s}{B})$

Selecting $\epsilon = 0.5$ improves insert performance by a factor of $\sqrt{B}$ over a standard $B^+$-tree, while point query latencies remain within a constant factor of $2\times$ of standard $B^+$-tree performance.

Message Routing, Cascading Flushes, and Node Dynamics

The $\mathcal{B}^\epsilon$-tree implements late-binding mutation semantics. Write operations do not traverse immediately to the leaves; instead, they are converted into typed messages and buffered in internal nodes.

[Client Insert/Delete]
        │
        ▼
┌──────────────────┐
│  Root Node       │
│  ┌────────────┐  │
│  │ Message    │  │
│  │ Buffer     │  │
│  └──────┬─────┘  │
└─────────┼────────┘
          │ (Buffer full: Bulk push Δ keys)
          ▼
┌──────────────────┐
│ Intermediate Node│
│  ┌────────────┐  │
│  │ Message    │  │
│  │ Buffer     │  │
│  └──────┬─────┘  │
└─────────┼────────┘
          │ (Cascading flush to target leaf)
          ▼
┌──────────────────┐
│    Leaf Node     │ ──&gt; Applied mutations to sorted base arrays
└──────────────────┘

Message Types and Semantics

Internal node buffers process three primary operational primitives:

UPSERT(key, payload): Appends an update payload or inserts a default record if the key is not present.
POINT_UPDATE(key, delta): Applies an atomic transformation (e.g., integer increment) during eventual leaf reconciliation.
TOMBSTONE(key): Explicitly marks a key for deletion.

Each buffered entry is stamped with a monotonically increasing, 64-bit Log Sequence Number (LSN) to enforce strict causal ordering:

struct alignas(16) Message {
    uint64_t lsn;
    uint32_t key_len;
    uint32_t val_len;
    enum class OpType : uint8_t { 
        INSERT = 0x01, 
        UPDATE = 0x02, 
        DELETE = 0x03 
    } op;
    char payload[]; // Packed key followed by value/delta
};

Flushing Policies and Cascade Control

When an internal node buffer exceeds its capacity threshold, the storage engine triggers a buffer evacuation process:

Child Selection: The engine inspects the node buffer and identifies the child edge containing the highest density of queued messages.
Batch Extraction: Messages routed to this selected child are copied into an execution batch.
Compaction: If multiple messages within the batch target the identical key, they are merged in memory:
- A TOMBSTONE cancels out earlier INSERT or UPDATE commands.
- Successive UPDATE operations are combined into a single delta.
Pushdown: The compacted batch is flushed down to the child node's buffer.

If the child node's buffer becomes full as a result of the pushdown, the process recurses downward (a cascading flush). If a pushdown reaches a leaf node, the mutations are directly applied to the leaf's primary key-value store.

Structural Modifications (Splits and Merges)

Leaf Splits: When a leaf node exceeds its allocation threshold $B$, it splits into two leaves along its median key, and a new pivot is posted to its parent.
Internal Node Splits: If an internal node exceeds its pivot capacity ($B^\epsilon$) or buffer capacity ($B - B^\epsilon$), the node partitions its pivot arrays and splits its message buffer along the median pivot.
Flushing Before Splitting: To avoid unnecessary structural modifications, the engine always attempts to flush messages downward before triggering a node split.

Lock-Free Page Mapping and Pointer Swizzling

To prevent lock contention from bottlenecking high-throughput I/O on multi-core architectures, in-memory tree nodes and physical flash pages are decoupled via a centralized, lock-free Page Mapping Table.

       Logical Page ID (LPID)
                 │
                 ▼
  ┌──────────────────────────────┐
  │ Lock-Free Page Mapping Table │
  ├──────────────────────────────┤
  │ LPID 0x01 -&gt; [State | Addr]  │ ──► CAS state transitions
  │ LPID 0x02 -&gt; [State | Addr]  │
  │ LPID 0x03 -&gt; [State | Addr]  │
  └──────────────┬───────────────┘
                 │
       ┌─────────┴─────────┐
       │                   │
       ▼                   ▼
┌──────────────┐    ┌──────────────┐
│ In-Memory    │    │ Physical NVMe│
│ Node Frame   │    │ Sector (LBA) │
└──────────────┘    └──────────────┘

The In-Memory Mapping Table

Nodes are referenced internally by an immutable 64-bit Logical Page ID (LPID). The Page Mapping Table is structured as a contiguous array of 64-bit atomic descriptors. Each descriptor encapsulates both the storage state of the page and its physical location:

union alignas(8) PageDescriptor {
    uint64_t raw_value;
    struct {
        uint64_t address     : 48; // Physical memory pointer OR NVMe LBA
        uint64_t epoch       : 12; // Epoch protection tag
        uint64_t is_flushing : 1;  // Page write in-flight
        uint64_t is_dirty    : 1;  // Modified relative to NVMe state
        uint64_t is_swizzled : 1;  // 1 = In-Memory Address, 0 = Disk LBA
        uint64_t is_locked   : 1;  // Exclusive transition flag
    } fields;
};

Atomic State Transitions and Pointer Swizzling

Traversing through an indirection table introduces memory latency overhead. To address this, pointer swizzling directly converts an LPID held in a parent node's pivot slot into a direct 64-bit virtual memory pointer to the child node once the child is paged into DRAM.

bool try_swizzle(std::atomic&amp; slot, uint64_t expected_lpid, void* memory_ptr) {
    uint64_t tagged_ptr = reinterpret_cast(memory_ptr) | (1ULL &lt;&lt; 63);
    return slot.compare_exchange_strong(
        expected_lpid,
        tagged_ptr,
        std::memory_order_release,
        std::memory_order_acquire
    );
}

bool is_swizzled(uint64_t slot_value) {
    return (slot_value &amp; (1ULL &lt;&lt; 63)) != 0;
}

[Unswizzled State]
Parent Slot: [0x0000000000000042] ──► Read via Mapping Table ──► NVMe Read
                                              │
                                              ▼ (Load page to DRAM)
[Swizzled State]
Parent Slot: [0x80007FFF12345678] ─────────────────────────────► Direct DRAM Access
              ▲
              │ Bit 63 set indicates direct memory pointer

Child In-Memory: If Bit 63 is asserted, the parent pointer is swizzled. The reader masks out Bit 63 and directly accesses the child node in DRAM without table lookups or latches.
Child On-Disk (Unswizzled): If Bit 63 is unasserted, the value is an LPID. The worker dereferences the Mapping Table, reserves an eviction frame, and schedules an asynchronous NVMe read.
Unswizzling under Eviction: When the buffer pool manager evicts an in-memory node to reclaim space, it issues a Compare-And-Swap (CAS) to change the parent reference from the pointer back to the raw LPID. It then uses a second CAS to update the mapping table descriptor, resetting is_swizzled to 0 and storing the page's new Physical Logical Block Address (LBA) on flash.

Memory Reclamation: Epoch-Based Reclamation (EBR)

Because worker threads traverse the tree without acquiring structural read latches, node unswizzling and buffer reclamation must avoid use-after-free conditions.

The engine uses an Epoch-Based Reclamation (EBR) scheme:

A global counter, GlobalEpoch, increments periodically (e.g., every 10 milliseconds).
Every active worker thread registers its local epoch in a thread-local variable upon starting an operation:

thread_local uint64_t LocalEpoch;

void enter_critical_section() {
    LocalEpoch = GlobalEpoch.load(std::memory_order_relaxed);
    std::atomic_signal_fence(std::memory_order_seq_cst);
}

void leave_critical_section() {
    LocalEpoch = UINT64_MAX; // Inactive
}

A page memory frame can be safely freed or recycled only when:

$$\min_{t \in \text{Active Threads}} (\text{LocalEpoch}t) > \text{Epoch}{\text{retired}}$$

This guarantees that no thread is still dereferencing the physical memory pointer of the unswizzled or replaced node.

Asynchronous NVMe Integration and Hardware Co-Design

Traditional synchronous I/O operations (pread/pwrite) incur system call overhead and context switches. To maximize throughput on high-performance NVMe SSDs, the storage engine bypasses POSIX abstractions and interacts directly with NVMe hardware queues using io_uring or the Storage Performance Development Kit (SPDK).

┌────────────────────────────────────────────────────────┐
│ Worker Thread (User Space)                             │
├────────────────────────────────────────────────────────┤
│ 1. Allocates DMA-aligned write buffer                   │
│ 2. Submits batch flush directly to Submission Queue    │
└───────────────────────────┬────────────────────────────┘
                            │
                            ▼ (Doorbell Register Write)
┌────────────────────────────────────────────────────────┐
│ NVMe Hardware Engine                                   │
├────────────────────────────────────────────────────────┤
│ 1. Direct Memory Access (DMA) fetches payload          │
│ 2. Out-of-place block write (Atomic Extent)            │
│ 3. Hardware posts entry to Completion Queue Ring       │
└───────────────────────────┬────────────────────────────┘
                            │
                            ▼ (Kernel-Bypass Polling)
┌────────────────────────────────────────────────────────┐
│ Polling Thread completes I/O, updates Mapping Table    │
└────────────────────────────────────────────────────────┘

Asynchronous I/O via `io_uring` Polling

The storage engine binds dedicated worker threads to independent NVMe Submission and Completion Queue pairs (SQ/CQ). Using the Linux io_uring interface with IORING_SETUP_SQPOLL and IORING_SETUP_IOPOLL flags enables pure, kernel-bypass polled I/O without issuing hardware interrupts:

struct IoEngine {
    struct io_uring ring;

    void submit_page_write(int fd, uint64_t lba, void* src_buf, size_t len, uint64_t user_data) {
        struct io_uring_sqe* sqe = io_uring_get_sqe(&amp;ring);
        
        io_uring_prep_write(sqe, fd, src_buf, len, lba * 4096);
        sqe-&gt;flags |= IOSQE_FIXED_FILE;
        sqe-&gt;user_data = user_data; // Encodes LPID and transaction sequence
        
        io_uring_submit(&amp;ring);
    }

    void poll_completions() {
        struct io_uring_cqe* cqe;
        unsigned head;
        unsigned count = 0;

        io_uring_for_each_cqe(&amp;ring, head, cqe) {
            uint64_t lpid = cqe-&gt;user_data;
            int res = cqe-&gt;res;
            
            if (res &gt;= 0) {
                // Finalize Mapping Table transition
                complete_page_write(lpid);
            }
            count++;
        }
        io_uring_cq_advance(&amp;ring, count);
    }
};

Out-of-Place Writes and Write Amplification Factor (WAF)

NAND flash memory cannot be overwritten in place; an entire flash erase block (typically 4 MB to 64 MB) must be erased before pages (typically 4 KB to 16 KB) can be reprogrammed.

When a traditional $B^+$-tree writes modified 4 KB pages in place:

The SSD's internal Flash Translation Layer (FTL) must remap the written LBA to a new physical flash location.
The stale physical page remains un-erased.
The FTL's garbage collector eventually reads the surviving valid pages out of an old erase block, writes them to a fresh block, and erases the old block.

This process induces high device-level Write Amplification ($WAF_{\text{device}}$):

$$WAF_{\text{device}} = \frac{\text{Bytes Written to NAND Flash}}{\text{Bytes Ingested by Host}}$$

The $\mathcal{B}^\epsilon$-tree engine mitigates this via large, log-structured allocation units. When internal buffers are pushed down or evicted, the node layout is serialized into large, naturally aligned sequential extents (e.g., 256 KB to 2 MB) matching the physical stripe size of the flash array:

[NVMe Flash Striping Layout]
┌────────────────────────────────────────────────────────┐
│ Erase Block N (Size: 4MB - 64MB)                       │
├──────────────┬──────────────┬──────────────┬───────────┤
│ Chunk 0      │ Chunk 1      │ Chunk 2      │ ...       │
│ (256 KB)     │ (256 KB)     │ (256 KB)     │           │
│ Node Flush A │ Node Flush B │ Node Flush C │           │
└──────────────┴──────────────┴──────────────┴───────────┘
 * Direct sequential extent writing eliminates FTL random rewrite fragmentation.

Sequential allocations eliminate internal FTL fragmentation, reducing both the internal $WAF_{\text{device}}$ and host-side $WAF_{\text{engine}}$, which extends flash drive endurance.

Cache Alignment and SIMD Pivot Search

Within each node's serialized memory layout, pivot keys are decoupled from variable-length payloads and packed into contiguous, 64-byte cache-line-aligned search arrays:

struct alignas(64) NodePivots {
    static constexpr size_t COUNT = 8;
    int64_t keys[COUNT]; // Fits precisely within one 64-byte CPU cache line
};

#include 

// Vectorized SIMD pivot lower-bound search for AVX-512
int find_child_avx512(const int64_t* keys, int64_t search_key) {
    __m512i target = _mm512_set1_epi64(search_key);
    __m512i pivots = _mm512_load_si512((const __m512i*)keys);
    
    // Vectorized packed comparison: target &lt; pivots
    __mmask8 mask = _mm512_cmplt_epi64_mask(target, pivots);
    
    // Count trailing zeros gives first index where target &lt; pivot
    return __builtin_ctz(mask | (1 &lt;&lt; 8));
}

By organizing node pivots into 64-byte chunks, modern CPUs can execute vectorized binary searches over internal fanout routing tables in a single clock cycle using AVX-512 comparison masks, removing in-memory search bottlenecks during deep tree traversals.

Complete End-to-End System Life Cycle

To understand how these components interact in practice, consider the end-to-end execution paths for writes and point queries:

================================================================================
                      WRITE / INGESTION DATA PATH
================================================================================
1. [Client Mutation] 
   └── Invokes `engine.put(Key, Value)`
2. [Root Routing]
   └── Navigates root buffer. Appends `Message{OpType::INSERT, Key, Value}`.
3. [Buffer Threshold Check]
   ├── Buffer Size &lt; (B - B^ε): Returns SUCCESS immediately (Memory-only latency).
   └── Buffer Size &gt;= (B - B^ε): Initiates Buffer Flush Pipeline.
4. [Buffer Flush Pipeline]
   ├── Finds child edge with highest message density (~B^(1-ε) messages).
   ├── Traverses child pointer:
   │   ├── Pointer is Swizzled: Resolves direct virtual DRAM pointer.
   │   └── Pointer is Unswizzled: Reads LPID via Mapping Table, fetches from NVMe.
   ├── Merges and compacts messages into child's message buffer.
   └── If child buffer overflows: Recursively cascades down to leaves.
5. [Log-Structured Extent Persistence]
   ├── Evicted/flushed nodes serialized to continuous aligned extents (e.g., 256 KB).
   ├── Submits vector write to `io_uring` ring via `io_uring_prep_writev`.
   └── Poller thread processes completions:
       └── Atomic CAS updates Page Mapping Table descriptor (clears `is_dirty`, updates LBA).

================================================================================
                      POINT LOOKUP DATA PATH
================================================================================
1. [Client Query]
   └── Invokes `engine.get(Key)`
2. [Epoch Registration]
   └── Thread registers `LocalEpoch = GlobalEpoch` (Lock-free memory protection).
3. [Top-Down Traversal]
   └── For each level from Root to Leaf:
       ├── 1. Binary searches local packed SIMD pivot array to identify target branch.
       ├── 2. Scans local message buffer for target `Key`:
       │      ├── Found `TOMBSTONE` -&gt; Return NOT_FOUND.
       │      ├── Found `INSERT`    -&gt; Return Value.
       │      └── Found `UPDATE`    -&gt; Stash delta in local mutation chain.
       └── 3. Resolves child pointer:
              ├── If Swizzled: Follow direct memory pointer to next level.
              └── If Unswizzled: Read LPID -&gt; Mapping Table -&gt; NVMe async load.
4. [Leaf Materialization]
   └── Reaches target Leaf base array. Applies accumulated update deltas to the base value.
5. [Epoch Deregistration]
   └── Sets `LocalEpoch = UINT64_MAX`. Returns materialized record to client.

Conclusion

Maximizing database performance on modern hardware requires co-designing indexing algorithms with the physical characteristics of NVMe storage. The $\mathcal{B}^\epsilon$-tree replaces the costly in-place updates of standard $B^+$-trees and the compaction bottlenecks of LSM-trees with an optimal balance between point queries ($\Theta(\frac{1}{\epsilon} \log_B N)$) and ingestion throughput ($\Theta(\frac{1}{\epsilon B^{1-\epsilon}} \log_B N)$).

By decoupling physical memory locations from logical IDs using a lock-free Page Mapping Table and pointer swizzling, the engine removes latch contention across high-core-count processors.

Finally, aligning batched buffer flushes with physical flash erase blocks and driving them through asynchronous interfaces (io_uring/SPDK) eliminates kernel overhead, lowers the Write Amplification Factor, and fully saturates NVMe SSD hardware channels.

References

Bender, M. A., Farach-Colton, M., Jannen, W., Kuszmaul, B. C., Porter, D. E., Yuan, J., & Zhan, P. An Introduction to B-epsilon-trees and Write-Optimization. USENIX ;login:, 40(5), 2015. https://www.usenix.org/system/files/login/articles/login_oct15_04_bender.pdf
Graefe, G., Volos, H., Kimura, H., Kuno, H., Tucek, J., & Lillibridge, M. In-Memory Performance for Big Data (Bw-Tree Architecture). IEEE 29th International Conference on Data Engineering (ICDE), 2013. https://ieeexplore.ieee.org/document/6544839
Leis, V., Haubenschild, M., & Kemper, A. LeanStore: In-Memory Performance for Durable Database Systems. IEEE 36th International Conference on Data Engineering (ICDE), 2020. https://db.in.tum.de/~leis/papers/leanstore.pdf

B-Epsilon Tree Database Storage Engines and Lock-Free Flash Page Management on NVMe SSDs

Introduction

Algorithmic Foundations of the $\mathcal{B}^\epsilon$-Tree

Parameterization and Node Sizing

Asymptotic I/O Complexity

Comparative Asymptotic Bounds

Message Routing, Cascading Flushes, and Node Dynamics

Message Types and Semantics

Flushing Policies and Cascade Control

Structural Modifications (Splits and Merges)

Lock-Free Page Mapping and Pointer Swizzling

The In-Memory Mapping Table

Atomic State Transitions and Pointer Swizzling

Memory Reclamation: Epoch-Based Reclamation (EBR)

Asynchronous NVMe Integration and Hardware Co-Design

Asynchronous I/O via `io_uring` Polling

Out-of-Place Writes and Write Amplification Factor (WAF)

Cache Alignment and SIMD Pivot Search

Complete End-to-End System Life Cycle

Conclusion

References

Verified References & Citations

Privacy & Cookies

Introduction

Algorithmic Foundations of the $\mathcal{B}^\epsilon$-Tree

Parameterization and Node Sizing

Asymptotic I/O Complexity

Comparative Asymptotic Bounds

Message Routing, Cascading Flushes, and Node Dynamics

Message Types and Semantics

Flushing Policies and Cascade Control

Structural Modifications (Splits and Merges)

Lock-Free Page Mapping and Pointer Swizzling

The In-Memory Mapping Table

Atomic State Transitions and Pointer Swizzling

Memory Reclamation: Epoch-Based Reclamation (EBR)

Asynchronous NVMe Integration and Hardware Co-Design

Asynchronous I/O via io_uring Polling

Out-of-Place Writes and Write Amplification Factor (WAF)

Cache Alignment and SIMD Pivot Search

Complete End-to-End System Life Cycle

Conclusion

References

Verified References & Citations

Privacy & Cookies

Asynchronous I/O via `io_uring` Polling