b-epsilon-tree · shipping · also Bε-tree, B^ε-tree, B-epsilon-tree

B-epsilon tree

A B-epsilon tree is an ordered index that buffers update messages in internal nodes and transfers them toward leaves in batches.

A lookup combines the leaf value with pending messages on its search path. The equal-size-item model trades node fanout against buffering; B denotes capacity in items, not a fixed number of bytes. TokuDB and the BetrFS research filesystem are implementation examples, not equivalent deployment guarantees. [1]

Relations

related
buffered-upsert, lsm-tree, copy-on-abundant-write

Citations

  1. William Jannen et al. BetrFS: A Right-Optimized Write-Optimized File System. FAST 2015, pp. 301-315; sections 2, 4, 5 and 7. Read with the publisher's erratum. (accessed 2026-10-16)

Further reading

  1. Hesela. B-epsilon trees: visible updates, deferred work (accessed 2026-10-16)

JSON: /data/terms/b-epsilon-tree.json