btree

btree implements an in-memory B-Tree for Go programs that need an ordered, mutable collection with fast insert, delete, lookup, and range-scan operations. Rather than the pointer-heavy node layout of a red-black tree, each B-Tree node holds a small slice of items and a slice of children, giving a flatter structure that tends to use memory more efficiently and produce fewer cache misses for typical workloads.

The package ships two parallel implementations gated by Go build tags: a generic BTreeG[T] for Go 1.18 and newer that takes a caller-supplied Less function, and a pre-generics BTree built around an Item interface for older toolchains. Both share the same underlying algorithm and expose a near-identical API, explicitly designed to mirror github.com/petar/GoLLRB/llrb so it can act as a drop-in replacement.

Writes use a copy-on-write context so that Clone() is O(1) and lazy: cloned trees share the original’s nodes until a write forces a copy, at which point only the touched path is duplicated. A per-tree (or shared) FreeList recycles freed nodes to cut down on allocator churn during heavy insert/delete cycles.

What You Get

• A BTree/BTreeG[T] ordered container supporting ReplaceOrInsert, Delete, DeleteMin, DeleteMax, and Get/Has lookups
• Full range-iteration API: Ascend, AscendRange, AscendLessThan, AscendGreaterOrEqual, plus the Descend* mirror set, each taking a caller-supplied iterator callback
• O(1) lazy Clone() via copy-on-write node sharing, so branching a tree doesn’t require a deep copy
• A configurable FreeList for recycling freed nodes across one or more trees to reduce GC pressure
• Both a generics-based API (BTreeG[T], Go 1.18+) and a pre-generics Item-interface API for compatibility with older Go versions

Common Use Cases

• Maintaining a large, frequently-mutated in-memory sorted index (e.g. a key range in a storage engine) without the overhead of a full database
• Implementing range queries over ordered keys, such as scanning all values between two bounds in a KV store or scheduler
• Snapshotting or branching a mutable ordered collection cheaply via Clone(), e.g. for MVCC-style read snapshots
• Swapping in as a memory-efficient replacement for an existing gollrb/LLRB-based red-black tree with minimal API changes

Under The Hood

Architecture The library is organized around three cooperating pieces: a node holding an items slice and a children slice under the invariant that a node has either zero children or len(items)+1 children; a copyOnWriteContext that tags which tree “owns” a given node for mutation purposes; and the public BTree/BTreeG[T] type that drives split/merge/rebalance logic through maybeSplitChild, growChildAndRemove, and mutableFor. Before any write descends into a node, it checks the node’s COW-context against the tree’s own context and copies-on-demand if they differ, which is what makes Clone() an O(1) operation — the cloned and original trees get fresh contexts and only diverge node-by-node as writes actually touch shared structure. Iteration (Ascend/Descend) is implemented as a single recursive node.iterate walk parameterized by direction and optional start/stop bounds, avoiding duplicated traversal code for the eight public range methods.

Tech Stack Pure Go with zero third-party dependencies — only stdlib packages (fmt, io, sort, strings, sync) are imported. The module targets go 1.18 in go.mod, but the codebase is split via //go:build tags into btree.go (pre-1.18, Item-interface based) and btree_generic.go (1.18+, BTreeG[T] generics with a caller-supplied Less function), letting the same package build across a wide compiler matrix; CI (.github/workflows/test.yml) exercises Go 1.11 through 1.18 on Ubuntu.

Code Quality Both implementation files have matching test files (btree_test.go, btree_generic_test.go), each with roughly ten Test* functions and around fifteen Benchmark* functions covering insert, delete, range-iteration, and clone-under-concurrency scenarios. Errors are handled by explicit panic for programmer-error cases (nil item insertion, degree <= 1) rather than swallowed silently, and exported functions carry doc comments describing invariants and complexity. There’s no separate linter configuration or static-analysis step beyond go test, so quality enforcement leans on the test suite and code review rather than tooling.

API Design The public surface is deliberately narrow and mirrors the well-known gollrb/LLRB API so existing callers can swap in with minimal changes: New(degree), ReplaceOrInsert, Delete, Get/Has, Min/Max, and the Ascend*/Descend* iterator family, all documented with Big-O complexity notes. The main piece of onboarding friction is that callers must implement Item.Less (or supply a Less function for the generic variant) themselves, and the copy-on-write Clone semantics — while powerful — require reading the doc comments to use safely under concurrent access.