v0 - Unaudited This is an initial version of this package that has not yet been formally audited. A fully audited version will be published as a subsequent release. Use in production at your own risk.

bptree - Mutable B+ tree

A mutable, in-place B+ tree for storing key-value data in Gno realms. Exposes the same ITree interface as gno.land/p/nt/avl/v0 but uses a B+ tree internally — fewer pointer dereferences per operation and better cache locality, with a configurable fanout.

Usage

 1package myrealm
 2
 3import "gno.land/p/nt/bptree/v0"
 4
 5// Zero value is usable (fanout 32). Persisted across transactions.
 6var tree bptree.BPTree
 7
 8func Set(key string, value int) {
 9    tree.Set(key, value)
10}
11
12func Get(key string) int {
13    raw := tree.Get(key)
14    if raw == nil {
15        panic("not found")
16    }
17    return raw.(int)
18}
19
20func RangeAsc(start, end string) {
21    tree.Iterate(start, end, func(key string, value any) bool {
22        // return true to stop early
23        return false
24    })
25}

For a different fanout, use a constructor:

1tree := bptree.NewBPTreeN(64) // fanout 64

API

 1type BPTree struct{ /* unexported */ }
 2
 3func NewBPTree32() *BPTree            // fanout 32
 4func NewBPTreeN(fanout int) *BPTree   // panics if fanout < 4
 5
 6// Read
 7func (t *BPTree) Size() int
 8func (t *BPTree) Has(key string) bool
 9func (t *BPTree) Get(key string) (value any) // nil if the key is absent
10func (t *BPTree) GetByIndex(index int) (key string, value any)
11func (t *BPTree) Iterate(start, end string, cb IterCbFn) bool
12func (t *BPTree) ReverseIterate(start, end string, cb IterCbFn) bool
13func (t *BPTree) IterateByOffset(offset, count int, cb IterCbFn) bool
14func (t *BPTree) ReverseIterateByOffset(offset, count int, cb IterCbFn) bool
15
16// Write
17func (t *BPTree) Set(key string, value any) (updated bool)
18func (t *BPTree) Remove(key string) (value any, removed bool)
19
20type IterCbFn func(key string, value any) bool
21
22type ITree interface { /* same shape as BPTree's methods */ }

The zero value of BPTree is a usable empty tree (fanout 32). Iterate uses [start, end) (start inclusive, end exclusive); ReverseIterate uses [start, end] (both inclusive). Empty strings mean unbounded. Callbacks return true to stop early. GetByIndex panics on out-of-range indices.

The tree must not be modified during iteration (no Set or Remove from the callback).

Subpackages

• gno.land/p/nt/bptree/v0/list - ordered list built on top of BPTree.
• gno.land/p/nt/bptree/v0/pager - pagination helper for trees and lists.
• gno.land/p/nt/bptree/v0/rotree - read-only view of a BPTree.

Notes

• API and semantics match gno.land/p/nt/avl/v0 exactly — "" is a valid key, Get returns nil for a missing key (use Has to distinguish a stored nil), and Remove returns (nil, false).
• Never return the live *BPTree from a realm getter: a caller can then call Set/Remove on it under your realm's authority. Return values, copies, or a read-only rotree view.
• Sequential keys from seqid (gno.land/p/nt/seqid/v0) pair well here: monotonic inserts hit the append-optimized split path.
• Fanout must be >= 4. Higher fanouts mean shallower trees and fewer object loads per lookup, at the cost of larger individual node objects.
• Each node (leaf or inner) is persisted as a separate object, so reads only load the O(log n) nodes on the search path — same storage-efficiency benefit as avl.
• No sibling pointers or first/last shortcuts: iteration uses an ephemeral stack to keep every persisted node at ref-count 1 (avoids Gno's object-escape penalty).