fractaltree

A write-optimized Bε-tree (fractal tree) for Go.
Buffer writes, flush in batches, iterate in sorted order.

What is this?

fractaltree is a pure-Go, generic, concurrent-safe implementation of the Bε-tree data structure. It is an ordered key-value store that is optimized for write-heavy workloads: instead of propagating every write to a leaf immediately (like a B-tree), it buffers mutations as messages in internal nodes and flushes them downward in batches. This amortizes the cost of random I/O across many writes.

The library works entirely in-memory by default, but ships with a pluggable Flusher interface and Codec system for disk persistence. Zero external runtime dependencies.

Installation

go get github.com/aalhour/fractaltree@latest

Quick Start

package main

import (
    "fmt"
    "log"

    "github.com/aalhour/fractaltree"
)

func main() {
    t, err := fractaltree.New[string, int]()
    if err != nil {
        log.Fatal(err)
    }

    t.Put("alice", 100)
    t.Put("bob", 200)
    t.Put("charlie", 300)

    v, ok := t.Get("bob")
    fmt.Println(v, ok) // 200 true

    for k, v := range t.Range("alice", "charlie") {
        fmt.Println(k, v) // alice 100, bob 200
    }
}

Background: Bε-Trees

How It Works

A fractal tree, more formally known as an Bε-tree (pronounced "B-epsilon tree"), is a search tree from the family of write-optimized data structures introduced by Brodal and Fagerberg (2003) and later refined in the context of databases by Bender, Farach-Colton, Fineman, Fogel, Kuszmaul, and Nelson.

Key papers:

• G. S. Brodal and R. Fagerberg, Lower Bounds for External Memory Dictionaries, SODA 2003 — introduced the Bε-tree model and proved optimal write-amortization bounds.
• M. A. Bender, M. Farach-Colton, J. T. Fineman, Y. R. Fogel, B. C. Kuszmaul, and J. Nelson, Cache-Oblivious Streaming B-trees, SICOMP 2007 — extended the model with streaming and cache-oblivious analysis.
• B. C. Kuszmaul, A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees, Tokutek White Paper 2014 — practical comparison of fractal trees vs LSM-trees as used in TokuDB.

The core mechanism is simple:

1. Buffered writes. Every internal node carries a message buffer. A write (put, delete, upsert) inserts a message into the root's buffer and returns immediately. No leaf is touched.
2. Batch flush. When a node's buffer fills up, all messages are sorted by key, partitioned by the node's pivot keys, and pushed to the appropriate child. If the child is a leaf, messages are applied directly. If it is internal, they land in that child's buffer.
3. Reads check buffers. A point query walks from root to leaf, collecting pending messages for the target key at every level. The most recent message wins (a DELETE cancels a prior PUT, an UPSERT transforms the value).

                    ┌──────────────────────────────────┐
         Root       │  pivots: [10, 20, 30]            │
       (internal)   │  buffer:  [PUT(25,"y"), DEL(7)]  │  ← writes land HERE first
                    └──┬──────┬──────┬──────┬──────────┘
                       │      │      │      │
                  <10  │ 10-20│ 20-30│  ≥30 │
                       ▼      ▼      ▼      ▼
                    [leaf]  [leaf] [leaf]  [leaf]
                    1,3,7   12,15  22,28   35,40

The Epsilon Parameter

The parameter ε (epsilon, where 0 < ε ≤ 1) controls how the block size B is divided between fanout and buffer capacity:

Values shown for default B = 4096.

Complexity

For ε = 0.5 and B = 4096, writes are ~64x fewer I/Os than a B-tree in the amortized case.

Use Cases

Bε-trees were designed for workloads where writes dominate reads:

• Databases and storage engines — TokuDB (MySQL), PerconaFT, BetrFS (file system). Any LSM-tree alternative that needs sorted order without compaction storms.
• Time-series and event logging — high-throughput append of timestamped records with occasional range scans.
• Write-ahead logs with indexed access — buffer mutations and flush periodically, while still supporting point lookups.
• Counters and accumulators — the Upsert / Increment pattern lets you bump values without reading first.
• Rate limiters and leaderboards — sorted structure supports both fast updates and ranked range queries.
• ETL and bulk ingest pipelines — batch-load millions of records, then scan or export in sorted order.

Features

• Generic — works with any key type: cmp.Ordered types via New, composite keys via NewWithCompare.
• Concurrent-safe — sync.RWMutex with read-many / write-one semantics. Iterators take a snapshot and release the lock.
• Rich query API — All, Ascend, Descend, Range, DescendRange as Go 1.23+ iter.Seq2 iterators, plus a stateful Cursor with Seek / Next / Prev.
• Upsert primitives — Upsert(key, fn), PutIfAbsent, Increment, CompareAndSwap for atomic read-modify-write.
• Range deletion — DeleteRange(lo, hi) removes an entire key range in one call.
• Disk persistence — DiskBETree with pluggable Flusher interface and Codec system (ships with GobCodec).
• Tunable — WithEpsilon and WithBlockSize to control the write/read tradeoff.
• Zero runtime dependencies — only stretchr/testify and uber/goleak for tests.

API Overview

Constructors

// For cmp.Ordered keys (int, string, float64, ...)
t, err := fractaltree.New[string, int](
    fractaltree.WithEpsilon(0.5),   // default
    fractaltree.WithBlockSize(4096), // default
)

// For composite or custom-ordered keys
t, err := fractaltree.NewWithCompare[MyKey, MyVal](compareFn)

// With disk persistence
t, err := fractaltree.NewDisk[string, int](flusher,
    fractaltree.WithKeyCodec[string, int](myCodec),
    fractaltree.WithValueCodec[string, int](myCodec),
)

Core Operations

t.Put(key, value)               // Insert or overwrite
v, ok := t.Get(key)             // Point lookup
ok := t.Contains(key)           // Existence check
deleted := t.Delete(key)        // Remove single key
n := t.DeleteRange(lo, hi)      // Remove keys in [lo, hi)
t.Clear()                       // Remove all keys
n := t.Len()                    // Key count
t.Close()                       // Release resources

Upsert

// Read-modify-write with a custom function
t.Upsert("counter", func(existing *int, exists bool) int {
    if exists {
        return *existing + 1
    }
    return 1
})

// Built-in helpers
t.Upsert("hits", fractaltree.Increment(1))
t.Upsert("flag", fractaltree.CompareAndSwap(oldVal, newVal))
inserted := t.PutIfAbsent("key", value)

Iteration

All iterators use Go 1.23+ range-over-func (iter.Seq2[K, V]):

for k, v := range t.All()                { ... }  // ascending
for k, v := range t.Ascend()             { ... }  // same as All
for k, v := range t.Descend()            { ... }  // descending
for k, v := range t.Range(lo, hi)        { ... }  // [lo, hi) ascending
for k, v := range t.DescendRange(hi, lo) { ... }  // (lo, hi] descending

Cursor

For stateful traversal with seek support:

c := t.Cursor()
defer c.Close()

c.Seek(42)               // position at first key >= 42
for c.Valid() {
    fmt.Println(c.Key(), c.Value())
    c.Next()
}

Disk Persistence

Implement the Flusher interface to control where nodes are stored:

type Flusher[K, V any] interface {
    WriteNode(id uint64, data []byte) error
    ReadNode(id uint64) ([]byte, error)
    Sync() error
    Close() error
}

Key and value serialization uses the Codec interface:

type Codec[T any] interface {
    Encode(T) ([]byte, error)
    Decode([]byte) (T, error)
}

The default GobCodec works out of the box. See the examples/disktree-* directories for custom binary encodings.

Concurrency Model

BETree uses a single sync.RWMutex:

Iterators and cursors use snapshot semantics: they materialize a consistent view of the data under a read lock, then release the lock immediately. The snapshot is iterated without holding any lock, so writers are not blocked during traversal.

Tuning

Rules of thumb:

• For write-heavy workloads (logging, counters, bulk ingest): lower ε (0.3 – 0.5) gives larger buffers and fewer flushes.
• For read-heavy workloads (lookups, range scans): higher ε (0.5 – 0.8) gives more fanout and shallower trees.
• For mixed workloads: the default (ε = 0.5, B = 4096) is a good starting point.
• Larger block sizes improve throughput but increase memory per node.

Performance

All benchmarks on Apple M2 Max, 32 GB RAM, Go 1.26.2. Full results, Google BTree comparison, and reproduction instructions in docs/PERFORMANCE.md.

vs Google BTree (highlights)

The Bε-tree and B-tree have different design points. FractalTree wins on sequential writes and point reads; Google BTree wins on random in-memory writes and range scans.

FractalTree achieves 99.6% fewer allocations on write operations. See docs/PERFORMANCE.md for the full comparison with reclassified design-point analysis.

Examples

The examples/ directory contains 15 runnable programs:

Run any example:

go run ./examples/basic

Run all examples:

make examples

Contributing

See CONTRIBUTING.md for the development workflow, testing practices, and benchmark procedures.

Design decisions are documented in docs/ADR.md — read the relevant records before modifying the flush or size-tracking paths.

License

Apache 2.0