What's Changed

Eliminates runtime.memmove (16% CPU) from the write path by replacing sorted buffer insertion with unsorted append and lazy sorting.

• appendToBuffer switched from sorted insertion (O(B) memmove per insert) to O(1) unsorted append
• Removed eager sorting from flushNode — sorting now only happens at leaf merge time via resolveMessages
• Added linear-scan fallback in bufferMessagesForKey and bufferSlice for reads on unsorted buffers (safe under RLock)
• Batch leaf merge and iterator refactor
• Cross-impl benchmarks now match Google BTree node config (WithBlockSize(63))

Benchmarks (vs v0.3.0)

Read regressions are expected and acceptable — this is a write-optimized B^ε-tree. The write path no longer pays any sorting or memmove cost on insert. Full
comparison in benchmarks/benchstat_v0.3.0...v0.4.0.txt.

Docs

• ADR-004: design rationale, alternatives rejected, invariants

Performance Improvements

Three-path batch merge in applyToLeaf replaces per-message leafInsert/leafDelete loop:

Geomean -13.9% across all benchmarks vs v0.2.1. Zero allocation regressions.

See docs/PERFORMANCE.md for full numbers and Google BTree comparison.

Documentation

• docs/ADR.md — Architecture decision records for batch merge, size tracking, flush bucket reuse
• docs/PERFORMANCE.md — Full benchmarks, cross-implementation comparison, reproduction instructions
• CONTRIBUTING.md — Development workflow, testing practices, benchmark procedures
• docs/ROADMAP.md — Completed work, profiling data, remaining optimizations

Design Details

See ADR-001 for the full decision record including alternatives benchmarked and rejected.

Performance Optimizations

P1: Reuse flush bucket allocations and compact buffer in-place

flushNode previously allocated a fresh [][]Message bucket slice and a remaining slice on every flush — producing 85.7% of all heap objects. This release:

• Adds a reusable flushBuckets field to internal nodes, reset via [:0] each flush
• Compacts the buffer in-place instead of allocating a new remaining slice

Benchmarks (vs v0.2.0, Apple M2 Max, Go 1.26, -count=6)

Full benchstat comparison in benchmarks/benchstat_v0.2.0...v0.2.1.txt.

Performance Optimizations

P0: Eliminate buffer scans in putLocked existence check

Replaced getFromNode (full root-to-leaf traversal with O(bufferCap) linear buffer scan per level) with existsInLeaf (leaf-only binary search) in the write path. A pendingDeletes counter triggers fallback to the full check only when buffered
deletes are in flight.

Benchmark improvements (Apple M2 Max, Go 1.26):

Other changes

• Fix BenchmarkDelete timer/setup issue (was rebuilding 100K tree inside timed loop)
• Add benchstat to tooling dependencies via tools.go

fractaltree v0.1.0

Initial release of a write-optimized B-epsilon-tree (fractal tree) for Go.

Highlights

• Generic ordered key-value store (cmp.Ordered or custom comparator)
• Concurrent-safe with sync.RWMutex (read-many / write-one)
• Buffered writes with configurable epsilon and block size
• iter.Seq2 iterators: All, Ascend, Descend, Range, DescendRange
• Stateful Cursor with Seek / Next / Prev
• Upsert, PutIfAbsent, Increment, CompareAndSwap
• DeleteRange for bulk key removal
• DiskBETree with pluggable Flusher and Codec interfaces
• Zero runtime dependencies
• 97.8% test coverage, 159 tests, fuzz/stress/race clean
• 15 runnable examples