btree

README

btree

A Go generic library providing copy-on-write B-tree data structures including maps, sets, interval trees, and order-statistic trees. All variants share a common augmented B-tree implementation (package aug) and support O(1) lazy cloning, a configurable degree, and pluggable node free lists.

Note: This library is still in beta. Please report any issues on the GitHub issue tracker.

Read about the design in docs/design.md; the original blog post predates the aug package and the New constructors.

m := btree.NewOrdered[string, int](btree.WithDegree(16)) // or New(strings.Compare, ...)
m.Upsert("foo", 1)
snapshot := m.Clone() // O(1); writes to either side copy on write
it := snapshot.Iterator()
for it.First(); it.Valid(); it.Next() {
	fmt.Println(it.Key(), it.Value())
}
for k, v := range snapshot.Range("a", "n") { // also All, Backward, From
	fmt.Println(k, v)
}
snapshot.Clear() // returns nodes only this tree references to the free list

The stateful Iterator and the range-over-func views cost about the same per entry when the loop body does real work; the iterator is the one to use for seeking and stepping, the views for whole-range walks.

A Cursor is an iterator that can also mutate the entry it is on and stay valid: SetValue, Delete (leaves the cursor on the successor), Rekey (moves the entry to a new key) and a hinted Upsert, each returning the displaced entry as the map methods do. Each acts in place when the leaf allows it and otherwise falls back to the top-down algorithm plus a re-seek, so "seek, then move this entry" costs one descent instead of three.

Sets are keyed by a comparison function, so two items that compare equal are the same item; Set.Get(probe) returns the stored one. Set iterators and cursors have no phantom values.

Writes to a map must be serialized by the caller; any number of goroutines may read a map, or a clone of it, while no goroutine writes it. See the aug package documentation for details.

Augmentations

The aug package exposes the tree with a per-node augmentation of type A maintained through an Updater, plus a LowLevelIterator for implementing searches guided by the augmentation. The orderstat and interval packages are built on it.

Performance

Against google/btree v1.1.3 at equal degree, point operations (insert, get, delete, seek and scan) are at parity or ahead by 5-15% with a comparison function, and ahead by 20-25% with NewOrdered for keys that support < (ints, strings, floats). On a scheduler-shaped workload (clone a 20k-entry map with 24-byte keys, move 200 entries to new keys, release the clone) a round takes 50 µs with delete + upsert and 42 µs through a Cursor, against 53 µs for google/btree at degree 16, with two allocations per round. Numbers and method are in docs/review-2026-09-29.md.

Interval Trees

The interval package provides interval trees for efficiently finding all intervals that overlap a query. Stored intervals are described by Bounds (how to read a start and end from your type); queries are Spans built with HalfOpen(start, end) or Point(key), so asking about a range never requires building a stored object. Overlaps(span) returns an OverlapIterator whose Next always means the next overlap and whose Seek(span) reuses it for the next query; Overlapping(span) is the range-over-func form.

Order-Statistic Trees

The orderstat package provides order-statistic trees: Rank(key) (the number of keys less than a key, and whether the key exists), Nth(rank), and Count(lo, hi), each in one descent. The iterator adds Rank() for its current position and SeekNth(rank).

Custom augmentations

Describe an augmentation as a CommutativeMonoid (an Identity, a per-entry contribution and a commutative, associative Combine; add Uncombine for O(1) removals) and build the map with aug.NewMonoid(cmp, m). Ready-made pieces: aug.Count, aug.Sum(f), and aug.PairOf(a, b) to keep several side by side. A MonoidMap answers Total(), Prefix(key) and Aggregate(lo, hi), and its iterators and cursors answer Prefix() and SeekPrefix(pred), which descends once to the first entry whose inclusive prefix satisfies a predicate that turns from false to true at most once (selection by rank, by cumulative weight, and so on). See Example_customAugmentation in package aug. Augmentations that are not monoids (the interval tree's upper bound) implement aug.Updater directly with aug.New.

License

Copyright 2021 Andrew Werner. Licensed under the Apache License, Version 2.0.

Documentation

Overview

Package btree provides copy-on-write ordered maps and sets backed by a B-tree. See package aug for the ownership and concurrency rules, and the orderstat and interval packages for augmented variants.

Comparison

A map or set is ordered, and its entries identified, by a comparison function: cmp(a, b) is negative, zero or positive as a sorts before, with or after b, and must be a total order (in particular, transitive). Two keys that compare equal are the same key, so an Upsert of a key equal to a stored one replaces it, and Set.Get returns the stored item for an equal probe. Data that the comparison reads must not change while the key is stored.

NewOrdered and NewOrderedSet order keys with <, as cmp.Compare does except for floating-point NaN, which they cannot place; use New with cmp.Compare for keys that may be NaN.

Index

• type FreeList
  • func NewFreeList[K, V any](size int) FreeList[K, V]
• type Map
  • func New[K, V any](cmp func(K, K) int, opts ...Option) *Map[K, V]
  • func NewOrdered[K cmp.Ordered, V any](opts ...Option) *Map[K, V]
  • func (m *Map[K, V]) All() iter.Seq2[K, V]
  • func (m *Map[K, V]) Backward() iter.Seq2[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Clone() *Map[K, V]
  • func (m *Map[K, V]) Compare(a, b K) int
  • func (m *Map[K, V]) Cursor() MapCursor[K, V]
  • func (m *Map[K, V]) Degree() int
  • func (m *Map[K, V]) Delete(k K) (removedK K, v V, found bool)
  • func (m *Map[K, V]) From(lo K) iter.Seq2[K, V]
  • func (m *Map[K, V]) Get(k K) (v V, ok bool)
  • func (m *Map[K, V]) Height() int
  • func (m *Map[K, V]) Iterator() MapIterator[K, V]
  • func (m *Map[K, V]) Len() int
  • func (m *Map[K, V]) Lookup(k K) (key K, v V, ok bool)
  • func (m *Map[K, V]) Max() (k K, v V, ok bool)
  • func (m *Map[K, V]) Min() (k K, v V, ok bool)
  • func (m *Map[K, V]) Range(lo, hi K) iter.Seq2[K, V]
  • func (m *Map[K, V]) String() string
  • func (m *Map[K, V]) Upsert(k K, v V) (replacedK K, replacedV V, replaced bool)
  • func (m *Map[K, V]) Verify() error
• type MapCursor
• type MapIterator
• type Option
  • func WithDegree(degree int) Option
  • func WithFreeList[K, V any](fl FreeList[K, V]) Option
• type Set
  • func NewOrderedSet[T cmp.Ordered](opts ...Option) *Set[T]
  • func NewSet[T any](cmp func(T, T) int, opts ...Option) *Set[T]
  • func (s *Set[T]) All() iter.Seq[T]
  • func (s *Set[T]) Backward() iter.Seq[T]
  • func (s *Set[T]) Clear()
  • func (s *Set[T]) Clone() *Set[T]
  • func (s *Set[T]) Compare(a, b T) int
  • func (s *Set[T]) Contains(item T) bool
  • func (s *Set[T]) Cursor() SetCursor[T]
  • func (s *Set[T]) Degree() int
  • func (s *Set[T]) Delete(item T) (removed T, ok bool)
  • func (s *Set[T]) From(lo T) iter.Seq[T]
  • func (s *Set[T]) Get(probe T) (item T, found bool)
  • func (s *Set[T]) Height() int
  • func (s *Set[T]) Iterator() SetIterator[T]
  • func (s *Set[T]) Len() int
  • func (s *Set[T]) Max() (item T, ok bool)
  • func (s *Set[T]) Min() (item T, ok bool)
  • func (s *Set[T]) Range(lo, hi T) iter.Seq[T]
  • func (s *Set[T]) String() string
  • func (s *Set[T]) Upsert(item T) (replaced T, overwrote bool)
  • func (s *Set[T]) Verify() error
• type SetCursor
  • func (c *SetCursor[T]) Compare(a, b T) int
  • func (c *SetCursor[T]) Delete() T
  • func (c *SetCursor[T]) First() bool
  • func (c *SetCursor[T]) Item() T
  • func (c *SetCursor[T]) Last() bool
  • func (c *SetCursor[T]) Next() bool
  • func (c *SetCursor[T]) Prev() bool
  • func (c *SetCursor[T]) Rekey(item T) (displaced T, ok bool)
  • func (c *SetCursor[T]) Reset()
  • func (c *SetCursor[T]) SeekExact(item T) bool
  • func (c *SetCursor[T]) SeekGE(item T) bool
  • func (c *SetCursor[T]) SeekGT(item T) bool
  • func (c *SetCursor[T]) SeekLE(item T) bool
  • func (c *SetCursor[T]) SeekLT(item T) bool
  • func (c *SetCursor[T]) Upsert(item T) (replaced T, ok bool)
  • func (c *SetCursor[T]) Valid() bool
• type SetIterator
  • func (i *SetIterator[T]) Compare(a, b T) int
  • func (i *SetIterator[T]) First() bool
  • func (i *SetIterator[T]) Item() T
  • func (i *SetIterator[T]) Last() bool
  • func (i *SetIterator[T]) Next() bool
  • func (i *SetIterator[T]) Prev() bool
  • func (i *SetIterator[T]) Reset()
  • func (i *SetIterator[T]) SeekExact(item T) bool
  • func (i *SetIterator[T]) SeekGE(item T) bool
  • func (i *SetIterator[T]) SeekGT(item T) bool
  • func (i *SetIterator[T]) SeekLE(item T) bool
  • func (i *SetIterator[T]) SeekLT(item T) bool
  • func (i *SetIterator[T]) Valid() bool

Examples

• Map
• MapCursor

Types

type FreeList

type FreeList[K, V any] = aug.FreeList[K, V, struct{}]

FreeList recycles nodes between Maps and Sets with the same key and value types.

func NewFreeList

func NewFreeList[K, V any](size int) FreeList[K, V]

NewFreeList returns a FreeList that retains up to size nodes. See aug.NewFreeList.

type Map

type Map[K, V any] aug.Map[K, V, struct{}]

Map is an ordered map from K to V. It is an aug.Map without an augmentation; the conversion between the two is free.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/ajwerner/btree"
)

func main() {
	m := btree.New[string, int](strings.Compare)
	m.Upsert("foo", 1)
	m.Upsert("bar", 2)
	fmt.Println(m.Get("foo"))
	fmt.Println(m.Get("baz"))
	it := m.Iterator()
	for it.First(); it.Valid(); it.Next() {
		fmt.Println(it.Key(), it.Value())
	}

}

Output:
1 true
0 false
bar 2
foo 1

func New

func New[K, V any](cmp func(K, K) int, opts ...Option) *Map[K, V]

New constructs a Map with the provided comparison function. See WithDegree and WithFreeList for the options.

func NewOrdered

func NewOrdered[K cmp.Ordered, V any](opts ...Option) *Map[K, V]

NewOrdered constructs a Map keyed by a type that supports <, ordered that way. It is faster than New with cmp.Compare because nodes are searched with < directly.

func (*Map[K, V]) All

func (m *Map[K, V]) All() iter.Seq2[K, V]

All returns an iterator over every entry in key order.

func (*Map[K, V]) Backward

func (m *Map[K, V]) Backward() iter.Seq2[K, V]

Backward returns an iterator over every entry in reverse key order.

func (*Map[K, V]) Clear

func (m *Map[K, V]) Clear()

Clear removes all entries, returning nodes no other map references to the free list. See aug.Map.Clear.

func (*Map[K, V]) Clone

func (m *Map[K, V]) Clone() *Map[K, V]

Clone clones the map, lazily. It does so in constant time.

func (*Map[K, V]) Compare

func (m *Map[K, V]) Compare(a, b K) int

Compare compares two keys with the map's comparison function.

func (*Map[K, V]) Cursor

func (m *Map[K, V]) Cursor() MapCursor[K, V]

Cursor returns a new cursor positioned before the first entry.

func (*Map[K, V]) Degree

func (m *Map[K, V]) Degree() int

Degree returns the degree of the tree.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(k K) (removedK K, v V, found bool)

Delete removes the entry with key k, returning it.

func (*Map[K, V]) From

func (m *Map[K, V]) From(lo K) iter.Seq2[K, V]

From returns an iterator over the entries with keys >= lo.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(k K) (v V, ok bool)

Get returns the value for k, if any.

func (*Map[K, V]) Height

func (m *Map[K, V]) Height() int

Height returns the height of the tree.

func (*Map[K, V]) Iterator

func (m *Map[K, V]) Iterator() MapIterator[K, V]

Iterator returns a new iterator positioned before the first entry.

func (*Map[K, V]) Len

func (m *Map[K, V]) Len() int

Len returns the number of entries.

func (*Map[K, V]) Lookup

func (m *Map[K, V]) Lookup(k K) (key K, v V, ok bool)

Lookup returns the stored entry whose key compares equal to k, if any.

func (*Map[K, V]) Max

func (m *Map[K, V]) Max() (k K, v V, ok bool)

Max returns the entry with the largest key.

func (*Map[K, V]) Min

func (m *Map[K, V]) Min() (k K, v V, ok bool)

Min returns the entry with the smallest key.

func (*Map[K, V]) Range

func (m *Map[K, V]) Range(lo, hi K) iter.Seq2[K, V]

Range returns an iterator over the entries with keys in [lo, hi).

func (*Map[K, V]) String

func (m *Map[K, V]) String() string

String renders the tree in a Newick-like format.

func (*Map[K, V]) Upsert

func (m *Map[K, V]) Upsert(k K, v V) (replacedK K, replacedV V, replaced bool)

Upsert inserts or replaces the entry with key k, returning any replaced entry.

func (*Map[K, V]) Verify

func (m *Map[K, V]) Verify() error

Verify checks the tree's invariants; see aug.Map.Verify.

type MapCursor

type MapCursor[K, V any] = aug.Cursor[K, V, struct{}]

MapCursor is a cursor for a Map: an iterator that can mutate the entry it is positioned on. See aug.Cursor.

Example

ExampleMapCursor charges the least loaded host and moves it to its new position without a second descent.

package main

import (
	"cmp"
	"fmt"
	"strings"

	"github.com/ajwerner/btree"
)

func main() {
	type host struct {
		load int
		name string
	}
	byLoad := func(a, b host) int {
		if c := cmp.Compare(a.load, b.load); c != 0 {
			return c
		}
		return strings.Compare(a.name, b.name)
	}
	fleet := btree.NewSet(byLoad)
	fleet.Upsert(host{3, "a"})
	fleet.Upsert(host{1, "b"})
	fleet.Upsert(host{2, "c"})

	c := fleet.Cursor()
	for range 3 {
		c.First()
		h := c.Item()
		h.load += 2
		c.Rekey(h)
		fmt.Println("charged", h.name, "to", h.load)
	}
	for h := range fleet.All() {
		fmt.Println(h.name, h.load)
	}
}

Output:
charged b to 3
charged c to 4
charged a to 5
b 3
c 4
a 5

type MapIterator

type MapIterator[K, V any] = aug.Iterator[K, V, struct{}]

MapIterator is an iterator for a Map.

type Option

type Option = aug.Option

Option configures a Map or Set at construction.

func WithDegree

func WithDegree(degree int) Option

WithDegree sets the degree of the tree. See aug.WithDegree.

func WithFreeList

func WithFreeList[K, V any](fl FreeList[K, V]) Option

WithFreeList sets the free list a Map or Set allocates from. See aug.WithFreeList.

type Set

type Set[T any] Map[T, struct{}]

Set is an ordered set of items of type T.

func NewOrderedSet

func NewOrderedSet[T cmp.Ordered](opts ...Option) *Set[T]

NewOrderedSet constructs a Set of a type that supports <, ordered that way. See NewOrdered.

func NewSet

func NewSet[T any](cmp func(T, T) int, opts ...Option) *Set[T]

NewSet constructs a Set with the provided comparison function. See WithDegree and WithFreeList for the options.

func (*Set[T]) All

func (s *Set[T]) All() iter.Seq[T]

All returns an iterator over every item in order.

func (*Set[T]) Backward

func (s *Set[T]) Backward() iter.Seq[T]

Backward returns an iterator over every item in reverse order.

func (*Set[T]) Clear

func (s *Set[T]) Clear()

Clear removes all items, returning nodes no other set references to the free list.

func (*Set[T]) Clone

func (s *Set[T]) Clone() *Set[T]

Clone clones the set, lazily. It does so in constant time.

func (*Set[T]) Compare

func (s *Set[T]) Compare(a, b T) int

Compare compares two items with the set's comparison function.

func (*Set[T]) Contains

func (s *Set[T]) Contains(item T) bool

Contains reports whether an item equal to item is in the set.

func (*Set[T]) Cursor

func (s *Set[T]) Cursor() SetCursor[T]

Cursor returns a new cursor positioned before the first item.

func (*Set[T]) Degree

func (s *Set[T]) Degree() int

Degree returns the degree of the tree.

func (*Set[T]) Delete

func (s *Set[T]) Delete(item T) (removed T, ok bool)

Delete removes the item equal to item and returns it.

func (*Set[T]) From

func (s *Set[T]) From(lo T) iter.Seq[T]

From returns an iterator over the items >= lo.

func (*Set[T]) Get

func (s *Set[T]) Get(probe T) (item T, found bool)

Get returns the item in the set equal to probe, if any. Items that compare equal may differ in fields the comparison ignores.

func (*Set[T]) Height

func (s *Set[T]) Height() int

Height returns the height of the tree.

func (*Set[T]) Iterator

func (s *Set[T]) Iterator() SetIterator[T]

Iterator returns a new iterator positioned before the first item.

func (*Set[T]) Len

func (s *Set[T]) Len() int

Len returns the number of items.

func (*Set[T]) Max

func (s *Set[T]) Max() (item T, ok bool)

Max returns the largest item.

func (*Set[T]) Min

func (s *Set[T]) Min() (item T, ok bool)

Min returns the smallest item.

func (*Set[T]) Range

func (s *Set[T]) Range(lo, hi T) iter.Seq[T]

Range returns an iterator over the items in [lo, hi).

func (*Set[T]) String

func (s *Set[T]) String() string

String renders the tree in a Newick-like format.

func (*Set[T]) Upsert

func (s *Set[T]) Upsert(item T) (replaced T, overwrote bool)

Upsert inserts or replaces item, returning any replaced item.

func (*Set[T]) Verify

func (s *Set[T]) Verify() error

Verify checks the tree's invariants; see aug.Map.Verify.

type SetCursor

type SetCursor[T any] struct {
	// contains filtered or unexported fields
}

SetCursor is a SetIterator that can also mutate the set at its position; see aug.Cursor for the rules.

func (*SetCursor[T]) Compare

func (c *SetCursor[T]) Compare(a, b T) int

Compare compares two items with the set's comparison function.

func (*SetCursor[T]) Delete

func (c *SetCursor[T]) Delete() T

Delete removes the current item and returns it, leaving the cursor on the following item or past the end; see aug.Cursor.Delete.

func (*SetCursor[T]) First

func (c *SetCursor[T]) First() bool

First positions the cursor at the smallest item.

func (*SetCursor[T]) Item

func (c *SetCursor[T]) Item() T

Item returns the item at the cursor's position, which must be valid.

func (*SetCursor[T]) Last

func (c *SetCursor[T]) Last() bool

Last positions the cursor at the largest item.

func (*SetCursor[T]) Next

func (c *SetCursor[T]) Next() bool

Next positions the cursor at the following item.

func (*SetCursor[T]) Prev

func (c *SetCursor[T]) Prev() bool

Prev positions the cursor at the preceding item.

func (*SetCursor[T]) Rekey

func (c *SetCursor[T]) Rekey(item T) (displaced T, ok bool)

Rekey replaces the current item with item, which may sort elsewhere, and returns any other item equal to it that was displaced. Afterwards the cursor is on item.

func (*SetCursor[T]) Reset

func (c *SetCursor[T]) Reset()

Reset marks the cursor invalid, before the first item.

func (*SetCursor[T]) SeekExact

func (c *SetCursor[T]) SeekExact(item T) bool

SeekExact positions the cursor at item and reports whether it is in the set; if not, the cursor is at the first greater item.

func (*SetCursor[T]) SeekGE

func (c *SetCursor[T]) SeekGE(item T) bool

SeekGE positions the cursor at the first item >= item.

func (*SetCursor[T]) SeekGT

func (c *SetCursor[T]) SeekGT(item T) bool

SeekGT positions the cursor at the first item > item.

func (*SetCursor[T]) SeekLE

func (c *SetCursor[T]) SeekLE(item T) bool

SeekLE positions the cursor at the last item <= item.

func (*SetCursor[T]) SeekLT

func (c *SetCursor[T]) SeekLT(item T) bool

SeekLT positions the cursor at the last item < item.

func (*SetCursor[T]) Upsert

func (c *SetCursor[T]) Upsert(item T) (replaced T, ok bool)

Upsert inserts item, or replaces the equal item already present and returns it, using the cursor's position as a hint. Afterwards the cursor is on item.

func (*SetCursor[T]) Valid

func (c *SetCursor[T]) Valid() bool

Valid reports whether the cursor is at an item.

type SetIterator

type SetIterator[T any] struct {
	// contains filtered or unexported fields
}

SetIterator iterates over a set. Every positioning method reports whether the iterator is now at an item.

func (*SetIterator[T]) Compare

func (i *SetIterator[T]) Compare(a, b T) int

Compare compares two items with the set's comparison function.

func (*SetIterator[T]) First

func (i *SetIterator[T]) First() bool

First positions the iterator at the smallest item.

func (*SetIterator[T]) Item

func (i *SetIterator[T]) Item() T

Item returns the item at the iterator's position, which must be valid.

func (*SetIterator[T]) Last

func (i *SetIterator[T]) Last() bool

Last positions the iterator at the largest item.

func (*SetIterator[T]) Next

func (i *SetIterator[T]) Next() bool

Next positions the iterator at the following item.

func (*SetIterator[T]) Prev

func (i *SetIterator[T]) Prev() bool

Prev positions the iterator at the preceding item.

func (*SetIterator[T]) Reset

func (i *SetIterator[T]) Reset()

Reset marks the iterator invalid, before the first item.

func (*SetIterator[T]) SeekExact

func (i *SetIterator[T]) SeekExact(item T) bool

SeekExact positions the iterator at item and reports whether it is in the set; if not, the iterator is at the first greater item.

func (*SetIterator[T]) SeekGE

func (i *SetIterator[T]) SeekGE(item T) bool

SeekGE positions the iterator at the first item >= item.

func (*SetIterator[T]) SeekGT

func (i *SetIterator[T]) SeekGT(item T) bool

SeekGT positions the iterator at the first item > item.

func (*SetIterator[T]) SeekLE

func (i *SetIterator[T]) SeekLE(item T) bool

SeekLE positions the iterator at the last item <= item.

func (*SetIterator[T]) SeekLT

func (i *SetIterator[T]) SeekLT(item T) bool

SeekLT positions the iterator at the last item < item.

func (*SetIterator[T]) Valid

func (i *SetIterator[T]) Valid() bool

Valid reports whether the iterator is at an item.