size-tiered-b-epsilon-tree · research · also STBε-tree, STB-epsilon tree

Size-tiered B-epsilon tree

A size-tiered B-epsilon tree is an ordered index whose trunk routes searches through separate branch trees while deferring compaction.

Related Observatory article: Size-tiered B-epsilon tree on hesela.com

Flush-then-compact moves branch references before merging their contents; a flush need not rewrite every referenced record. Short scans still initialize iterators across active branches. [1]

The index structure does not specify a durability acknowledgment. In revision 73f89d8879e2, a successful update is visible but not necessarily durable; the public API distinguishes a blocking durability result from acceptance of an asynchronous barrier. [2]

A tracked notification must complete successfully before its durability guarantee applies. With no normal workers, polling alone does not advance the queued work. Notification storage must remain alive until completion. [3]

Relations

related

B-epsilon tree, Tiered compaction, Quotient filter, Write-ahead log

Citations

1. Conway et al. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. USENIX ATC 2020, pp. 49-63, sections 2-3 and 6. (accessed 2026-11-11)
2. SplinterDB public API: update visibility and durable-barrier completion, revision 73f89d8879e2 (2026-11-01) (accessed 2026-11-11)
3. SplinterDB: Durability notifications, revision 73f89d8879e2 (accessed 2026-11-11)

Further reading

4. Hesela: B-epsilon trees, flush-then-compact and durability acknowledgments (accessed 2026-11-11)

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