B-epsilon trees: visible updates, deferred work

Published 2026-10-16 / Source review and constructed examples

An update can affect a query before it reaches the leaf that stores the old value. B-epsilon trees exploit this distinction to batch writes. Their outstanding work still matters: fewer flushes and earlier completion are different objectives.

The buffer belongs to the tree

A B-epsilon tree adds update buffers to internal search-tree nodes. Messages move toward leaves in batches. They are not merely a volatile queue outside the index: the buffers belong to nodes that can themselves be stored on disk. A query follows its key's path and combines pending messages with the leaf value. Merely reading that leaf can therefore return an obsolete answer. [1, section 2]

In the equal-size-item model, B is node capacity in items, not bytes or an SSD erase-block size. Fanout is approximately B to the power epsilon; the remaining space buffers messages. Reducing fanout improves batching but lengthens paths. The asymptotic result is not a device-latency multiplier. [2, pp. 23-25]

Read the messages in time order

Our constructed single-key example starts with 10 in a leaf. The older message, sequence 1, adds 5 and has reached a lower internal buffer. Sequence 2, still at the root, multiplies by 2. No new message has yet changed the stored leaf.

One key, two pending updates; exact integer arithmetic
Evaluation	Calculation	Answer
Leaf only, incorrect	10	10
Root first, incorrect	(10 x 2) + 5	25
Sequence order	(10 + 5) x 2	30

Collecting messages is not enough: order matters when operations do not commute. The evaluator sorts by sequence and leaves its inputs unchanged. Adding a sequence-3 tombstone returns absence even though this example's leaf still contains 10. That is logical visibility, not a claim that obsolete bytes have disappeared from storage.

A buffered upsert encodes a transformation of a value without first retrieving it. The callback and its arguments travel as a message. This usage is more specific than SQL's insert-or-update syntax. A mandatory lookup before every update can erase the benefit of cheap message insertion. [2, p. 26]

For an application, ask whether the operation really is blind. A rule that must reject an update based on the current balance, validate a version or return the old value needs a corresponding correctness contract. Renaming that operation an upsert does not remove the information it requires.

Four flushes, different completion times

Chung and colleagues study an offline scheduling problem: a fixed tree and a known set of messages, with completion defined as arrival at the destination leaf. Their objective is average completion time. The analysis is not a measurement of fsync latency, online arrivals or a deployed database. [3, sections 1-2]

Our smaller example has five messages at the root at step 0. Four target leaf A; one targets leaf B. Each path has two edges: root to internal node, then internal node to leaf. A flush carries at most four messages across one edge. Only one flush runs per step; each takes one abstract time unit. Internal buffers hold four messages, and root backlog is unrestricted.

We move each branch's messages as one batch. This leaves exactly four flush tasks. A branch's root flush must precede its leaf flush. Exhaustive enumeration gives six legal orders, not a sample drawn from a workload.

All messages arrive at step 0; completion is the end of a leaf flush
Flush order	A done	B done	Mean, steps
root-A / leaf-A / root-B / leaf-B	2	4	2.4
root-A / root-B / leaf-A / leaf-B	3	4	3.2
root-A / root-B / leaf-B / leaf-A	4	3	3.8
root-B / root-A / leaf-A / leaf-B	3	4	3.2
root-B / root-A / leaf-B / leaf-A	4	3	3.8
root-B / leaf-B / root-A / leaf-A	4	2	3.6

Every row performs four flushes and finishes the last message at step 4. Yet mean completion ranges from 2.4 to 3.8 steps. The denominator is five messages: mean = (4 x A completion + B completion) / 5. Averaging the two branch times would answer a different question.

Finishing A first completes four messages at step 2 and one at step 4. Doing both root flushes first can leave all five unfinished after step 2. These counts isolate scheduling, not physical speed. They do not implement the paper's approximation algorithm or establish an optimum for arbitrary trees.

Download the dependency-free evaluator, its tests and the generated inputs and results, with a reproducible JSON generator. Run node --test buffered-tree-example.test.mjs beside the evaluator. There are no sampling intervals: these are constructed, exhaustively checked cases. Timing uncertainty resides in the omitted real-system behavior.

BetrFS is evidence about a design, not every filesystem

The FAST 2015 prototype used a TokuDB-derived in-kernel index over ext4. The authors identified FUSE query traffic as an obstacle to write optimization. This is implementation-specific evidence, not a verdict on current FUSE. Renames and reclamation also had costs. [1, sections 4-7]

Check the erratum before reusing Table 6: the original transposed the btrfs results for find and grep. The corrected means are 3.87 seconds for find and 14.91 seconds for grep, with reported 95% confidence-interval half-widths of 0.94 and 1.18 seconds, respectively. These are published historical benchmark results, not measurements made by Hesela. [4]

Those cold-cache tests searched the Linux 3.11.10 source tree on a 250 GB, 7200 RPM ATA disk with 4 GB RAM. The cited evaluation section does not establish the repetition count; we do not calculate a new significance test. [1, sections 7 and 7.3]

The scheduling paper motivates leaf completion partly through deletion. Our interpretation is deliberately narrower than device sanitization: removing an item from a tree does not establish removal from journals, snapshots, replicas or flash translation-layer copies. See SSD sanitization evidence. [3, section 1]

Measure the work that remains

For a real evaluation, report the read-before-write pattern, key locality, message sizes, node sizes, cache state and concurrent activity. Separate accepted operations, query-visible state, durable acknowledgement and leaf materialization. Record backlog at the end of the timed interval and the cost of draining it.

Do not rank indexes by one insert loop without stating its stopping condition. A test that stops while messages remain buffered and one that waits for their application are observing different work. Our example supplies no throughput, endurance, durability or production-readiness claim.

Continue with LSM read costs, filesystem aging and BetrFS copy-on-abundant-write. Machine-readable definitions: B-epsilon tree and buffered upsert.

Primary sources and limits

No BetrFS deployment, hardware benchmark or paper replication was performed. The executable examples are original teaching models. Source figures are not reproduced.