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 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.
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 range. The iterator supports FirstOverlap() and NextOverlap() methods for querying overlapping intervals.
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 Monoid (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 SeekWhere(pred), which descends once to the first entry at which a monotone predicate on the running prefix flips (selection by rank, by cumulative sum, 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.
Index ¶
- type FreeList
- type Map
- 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]) 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
- type Set
- 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 bool)
- func (s *Set[T]) From(lo T) iter.Seq[T]
- 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
- type SetIterator
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type FreeList ¶ added in v0.2.0
FreeList recycles nodes between Maps and Sets with the same key and value types.
func NewFreeList ¶ added in v0.2.0
NewFreeList returns a FreeList that retains up to size nodes. See aug.NewFreeList.
type Map ¶
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 ¶ added in v0.2.0
New constructs a Map with the provided comparison function. See WithDegree and WithFreeList for the options.
func NewOrdered ¶ added in v0.2.0
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]) Backward ¶ added in v0.2.0
Backward returns an iterator over every entry in reverse key order.
func (*Map[K, V]) Clear ¶ added in v0.2.0
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]) Compare ¶ added in v0.2.0
Compare compares two keys with the map's comparison function.
func (*Map[K, V]) Cursor ¶ added in v0.2.0
Cursor returns a new cursor positioned before the first entry.
func (*Map[K, V]) Iterator ¶ added in v0.2.0
func (m *Map[K, V]) Iterator() MapIterator[K, V]
Iterator returns a new iterator positioned before the first entry.
func (*Map[K, V]) Range ¶ added in v0.2.0
Range returns an iterator over the entries with keys in [lo, hi).
type MapCursor ¶ added in v0.2.0
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.Key()
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 ¶
MapIterator is an iterator for a Map.
type Option ¶ added in v0.2.0
Option configures a Map or Set at construction.
func WithDegree ¶ added in v0.2.0
WithDegree sets the degree of the tree. See aug.WithDegree.
func WithFreeList ¶ added in v0.2.0
WithFreeList sets the free list a Map or Set allocates from. See aug.WithFreeList.
type Set ¶
Set is an ordered set of items of type T.
func NewOrderedSet ¶ added in v0.2.0
NewOrderedSet constructs a Set of a type that supports <, ordered that way. See NewOrdered.
func NewSet ¶ added in v0.2.0
NewSet constructs a Set with the provided comparison function. See WithDegree and WithFreeList for the options.
func (*Set[T]) Backward ¶ added in v0.2.0
Backward returns an iterator over every item in reverse order.
func (*Set[T]) Clear ¶ added in v0.2.0
func (s *Set[T]) Clear()
Clear removes all items, returning nodes no other set references to the free list.
func (*Set[T]) Compare ¶ added in v0.2.0
Compare compares two items with the set's comparison function.
func (*Set[T]) Cursor ¶ added in v0.2.0
Cursor returns a new cursor positioned before the first item.
func (*Set[T]) Iterator ¶ added in v0.2.0
func (s *Set[T]) Iterator() SetIterator[T]
Iterator returns a new iterator positioned before the first item.
type SetIterator ¶
type SetIterator[T any] = MapIterator[T, struct{}]
SetIterator is an iterator for a Set.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package aug implements a copy-on-write augmented B-tree.
|
Package aug implements a copy-on-write augmented B-tree. |
|
Package interval provides copy-on-write ordered maps and sets of intervals whose iterators find every interval overlapping a query in O(log n + k).
|
Package interval provides copy-on-write ordered maps and sets of intervals whose iterators find every interval overlapping a query in O(log n + k). |
|
Package orderstat provides copy-on-write ordered maps and sets with order-statistic queries: the rank of a key, the entry at a rank, and the number of entries in a key range, each in O(log n).
|
Package orderstat provides copy-on-write ordered maps and sets with order-statistic queries: the rank of a key, the entry at a rank, and the number of entries in a key range, each in O(log n). |