Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

/p/nt/bptree/v0

Directory · 8 Files
README.md Open

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/list/v0 - ordered list built on top of BPTree.
  • gno.land/p/nt/bptree/pager/v0 - pagination helper for trees and lists.
  • gno.land/p/nt/bptree/rotree/v0 - 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).