README
¶
BTree map based on google/btree
btreemap
An ordered, in‑memory B‑Tree map for Go – a generic key‑value store with fast range iteration and copy‑on‑write snapshots.
Forked from
github.com/google/btreeand modernized for Go1.22+ generics anditersequences.
Features
- Ordered map – keys are kept sorted; all operations are O(log(n)).
- Generic – works with any key/value types via a user‑supplied compare function.
- Fast range iteration – iterate forward or backward between arbitrary bounds without allocation.
- Copy‑on‑write snapshots –
Cloneproduces a cheap, immutable view that can be read concurrently with the parent. - Custom degree / free‑list – tune memory use vs. CPU by choosing the node degree and enabling node reuse.
Concurrency note
Reads may run concurrently on the sameBTreeMap. Writes (any method that mutates the map) must be serialized.
Clonecreates an independent snapshot that may be mutated safely in parallel with the original.
Quick start
package main
import (
"cmp"
"fmt"
"github.com/RaduBerinde/btreemap"
)
func main() {
// A 2‑3‑4 tree mapping int → string.
m := btreemap.New[int,string](2, cmp.Compare[int])
// Insert / replace
_, _, replaced := m.ReplaceOrInsert(42, "meaning")
fmt.Println(replaced) // false – key was new
// Lookup
_, v, ok := m.Get(42)
fmt.Println(ok, v) // true meaning
// Range iteration: 10 ≤ k < 100
for k, v := range m.Ascend(btreemap.GE(10), btreemap.LT(100)) {
fmt.Printf("%d → %s\n", k, v)
}
fmt.Println("len before:", m.Len())
// Delete single key
m.Delete(42)
fmt.Println("len after:", m.Len())
}
API overview
// Construction
func New[K,V any](degree int, cmp btreemap.CmpFunc[K]) *BTreeMap[K,V]
func NewWithFreeList[K,V any](degree int, cmp CmpFunc[K], fl *FreeList[K,V]) *BTreeMap[K,V]
// Mutations
ReplaceOrInsert(key, value) (oldKey, oldValue, replaced bool)
Delete(key) (oldKey, oldValue, found bool)
DeleteMin() / DeleteMax()
Clear(addNodesToFreeList bool)
// Queries
Get(key) (key, value, found bool)
Has(key) bool
Min()/Max() (key, value, found bool)
Len() int
// Iteration (log(n) to first element, then amortized O(1))
Ascend(start LowerBound[K], stop UpperBound[K]) iter.Seq2[K,V]
Descend(start UpperBound[K], stop LowerBound[K]) iter.Seq2[K,V]
// Snapshots
Clone() *BTreeMap[K,V]
Bounds helpers
// Lower bound
btreemap.Min[T]() // unbounded (−∞)
btreemap.GE(key) // ≥ key (inclusive)
btreemap.GT(key) // > key (exclusive)
// Upper bound
btreemap.Max[T]() // unbounded (+∞)
btreemap.LE(key) // ≤ key (inclusive)
btreemap.LT(key) // < key (exclusive)
Example: descending top‑N
// Print the 5 largest entries.
count := 0
for k, v := range m.Descend(btreemap.Max[int](), btreemap.Min[int]()) {
fmt.Println(k, v)
count++
if count == 5 {
break
}
}
Example: snapshot for concurrent readers
snapshot := m.Clone() // cheap, O(1)
go func() {
// Writer goroutine mutates the original map.
for i := 0; i < 1_000; i++ {
m.ReplaceOrInsert(i, "val")
}
}()
// Reader goroutine works on an immutable view.
for k, v := range snapshot.Ascend(btreemap.Min[int](), btreemap.Max[int]()) {
fmt.Println(k, v)
})
Tuning
| Parameter | Effect |
|---|---|
| degree | Maximum node size = 2*degree-1. Small degrees use more pointers but less per‑node scan time (good for small maps). Higher degrees shrink tree height and improve cache locality for large maps. Typical values:2…8. |
| FreeList | Reuses nodes after deletes/Clear, reducing GC pressure in high‑churn workloads. Use NewWithFreeList if you need fine control over freelist size or sharing between many maps. |
License
Apache 2.0 – see LICENSE.
Original work ©Google Inc. 2014‑2024
Documentation
¶
Overview ¶
Package btreemap implements an ordered key-value map using an in-memory B-Tree of arbitrary degree.
The internal B-Tree code is based on github.com/google/btree.
Index ¶
- Constants
- type BTreeMap
- func (t *BTreeMap[K, V]) Ascend(start LowerBound[K], stop UpperBound[K]) iter.Seq2[K, V]
- func (t *BTreeMap[K, V]) AscendFunc(start LowerBound[K], stop UpperBound[K], yield func(key K, value V) bool)
- func (t *BTreeMap[K, V]) Clear(addNodesToFreelist bool)
- func (t *BTreeMap[K, V]) Clone() (t2 *BTreeMap[K, V])
- func (t *BTreeMap[K, V]) Delete(key K) (K, V, bool)
- func (t *BTreeMap[K, V]) DeleteMax() (K, V, bool)
- func (t *BTreeMap[K, V]) DeleteMin() (K, V, bool)
- func (t *BTreeMap[K, V]) Descend(start UpperBound[K], stop LowerBound[K]) iter.Seq2[K, V]
- func (t *BTreeMap[K, V]) DescendFunc(start UpperBound[K], stop LowerBound[K], yield func(key K, value V) bool)
- func (t *BTreeMap[K, V]) Get(key K) (_ K, _ V, _ bool)
- func (t *BTreeMap[K, V]) Has(key K) bool
- func (t *BTreeMap[K, V]) Len() int
- func (t *BTreeMap[K, V]) Max() (K, V, bool)
- func (t *BTreeMap[K, V]) Min() (K, V, bool)
- func (t *BTreeMap[K, V]) ReplaceOrInsert(key K, value V) (_ K, _ V, replaced bool)
- type CmpFunc
- type FreeList
- type LowerBound
- type UpperBound
Constants ¶
const DefaultFreeListSize = 32
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTreeMap ¶
BTreeMap implements an ordered key-value map using an in-memory B-Tree of arbitrary degree. It allows easy insertion, removal, and iteration.
Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are.
func New ¶
New creates a new map backed by a B-Tree with the given degree.
New(2), for example, will create a 2-3-4 tree, where each node contains 1 to 3 items and 2 to 4 children).
The passed-in CmpFunc determines how objects of type T are ordered. For ordered basic types, use cmp.Compare.
func NewWithFreeList ¶
NewWithFreeList creates a new map that uses the given node free list.
func (*BTreeMap[K, V]) Ascend ¶
func (t *BTreeMap[K, V]) Ascend(start LowerBound[K], stop UpperBound[K]) iter.Seq2[K, V]
Ascend returns an iterator which yields all elements between the start and stop bounds, in ascending order.
func (*BTreeMap[K, V]) AscendFunc ¶
func (t *BTreeMap[K, V]) AscendFunc( start LowerBound[K], stop UpperBound[K], yield func(key K, value V) bool, )
AscendFunc calls yield() for all elements between the start and stop bounds, in ascending order.
func (*BTreeMap[K, V]) Clear ¶
Clear removes all items from the btree. If addNodesToFreelist is true, t's nodes are added to its freelist as part of this call, until the freelist is full. Otherwise, the root node is simply dereferenced and the subtree left to Go's normal GC processes.
This can be much faster than calling Delete on all elements, because that requires finding/removing each element in the tree and updating the tree accordingly. It also is somewhat faster than creating a new tree to replace the old one, because nodes from the old tree are reclaimed into the freelist for use by the new one, instead of being lost to the garbage collector.
This call takes:
O(1): when addNodesToFreelist is false, this is a single operation.
O(1): when the freelist is already full, it breaks out immediately
O(freelist size): when the freelist is empty and the nodes are all owned
by this tree, nodes are added to the freelist until full.
O(tree size): when all nodes are owned by another tree, all nodes are
iterated over looking for nodes to add to the freelist, and due to
ownership, none are.
func (*BTreeMap[K, V]) Clone ¶
Clone clones the btree, lazily. Clone should not be called concurrently, but the original tree (t) and the new tree (t2) can be used concurrently once the Clone call completes.
The internal tree structure of b is marked read-only and shared between t and t2. Writes to both t and t2 use copy-on-write logic, creating new nodes whenever one of b's original nodes would have been modified. Read operations should have no performance degradation. Write operations for both t and t2 will initially experience minor slow-downs caused by additional allocs and copies due to the aforementioned copy-on-write logic, but should converge to the original performance characteristics of the original tree.
func (*BTreeMap[K, V]) Delete ¶
Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns (zeroValue, false).
func (*BTreeMap[K, V]) DeleteMax ¶
DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns (zeroValue, false).
func (*BTreeMap[K, V]) DeleteMin ¶
DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns (zeroValue, false).
func (*BTreeMap[K, V]) Descend ¶
func (t *BTreeMap[K, V]) Descend(start UpperBound[K], stop LowerBound[K]) iter.Seq2[K, V]
Descend returns an iterator which yields all elements between the start and stop bounds, in ascending order.
func (*BTreeMap[K, V]) DescendFunc ¶
func (t *BTreeMap[K, V]) DescendFunc( start UpperBound[K], stop LowerBound[K], yield func(key K, value V) bool, )
DescendFunc calls yield() for all elements between the start and stop bounds, in ascending order.
func (*BTreeMap[K, V]) Get ¶
Get looks for the key in the tree, returning (key, value, true) if found, or (0, 0, false) otherwise.
func (*BTreeMap[K, V]) Max ¶
Max returns the largest key and associated value in the tree, or (0, 0, false) if the tree is empty.
func (*BTreeMap[K, V]) Min ¶
Min returns the smallest key and associated value in the tree, or (0, 0, false) if the tree is empty.
func (*BTreeMap[K, V]) ReplaceOrInsert ¶
ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned, and the second return value is true. Otherwise, (zeroValue, false)
nil cannot be added to the tree (will panic).
type CmpFunc ¶
CmpFunc returns: - 0 if the two keys are equal; - a negative number if a < b; - a positive number if a > b.
type FreeList ¶
type FreeList[K, V any] struct { // contains filtered or unexported fields }
FreeList represents a free list of btree nodes. By default each BTreeMap has its own FreeList, but multiple BTrees can share the same FreeList, in particular when they're created with Clone. Two Btrees using the same freelist are safe for concurrent write access.
type LowerBound ¶
type LowerBound[K any] bound[K]
LowerBound defines an (optional) lower bound for iteration.
func Min ¶
func Min[K any]() LowerBound[K]
Min returns a LowerBound that does not limit the lower bound of the iteration.
type UpperBound ¶
type UpperBound[K any] bound[K]
UpperBound defines an (optional) upper bound for iteration.
func Max ¶
func Max[K any]() UpperBound[K]
Max returns an UpperBound that does not limit the upper bound of the iteration.
Source Files