bptree

package
v0.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 1, 2026 License: Apache-2.0, UNKNOWN not legal advice Imports: 0 Imported by: 0

README

bptree — Immutable B+ Tree for Gno

A drop-in replacement for tm2/pkg/iavl, implementing a versioned, persistent B+ tree with ICS23 merkle proofs.

Why replace IAVL?

IAVL is a binary AVL+ tree. Every read traverses ~28 levels for 100M items. Every write COW-clones ~28 nodes. The B+ tree with branching factor 32 reduces this to ~6 levels — fewer disk reads, fewer writes, fewer round-trips to the underlying KV store.

Metric (100M items, 10K cache) IAVL B+32
GET disk reads 15 3
SET disk writes 28 7
SET total ops 43 10
Proof size ~1.4 KB ~1.0 KB

See PERFORMANCE.md for full analysis across tree sizes, cache configurations, and batched workloads.

Design choices

Branching factor B=32

A compile-time constant. Each inner node holds up to 31 separator keys and 32 child references. Each leaf holds up to 32 key-value pairs. The value 32 balances:

  • Read performance: tree height is log₃₂(n) ≈ 6 for 100M items
  • Write amplification: each COW'd node is ~1.7KB (vs IAVL's ~100B)
  • Proof size: log₂(32)=5 mini-merkle siblings per tree level
  • Cache efficiency: 10K nodes × ~4.3KB ≈ 43MB caches all inner nodes up to ~200M items
Out-of-line values

Leaf nodes store key + SHA256(value) + ValueKey(12B), not the raw value. Values are stored separately in the DB under their ValueKey (a per-allocation (version, nonce) identifier), with the SHA256(value) kept in the leaf for Merkle proofs. This means:

  • Smaller nodes: leaf nodes are ~1.4KB regardless of value size
  • Less COW amplification: modifying one key copies only hash references, not sibling values
  • Copy safety: callers cannot corrupt stored values by mutating their byte slices

Values are staged in the write batch (and an in-memory pending buffer so Get works before SaveVersion), then flushed to the DB atomically with the nodes and root at SaveVersion. Rollback discards the staged batch, so a working session abandoned before SaveVersion (including a process crash) leaves nothing in the DB. Dead values are reclaimed by pruning: overwrites and removes record the displaced ValueKey in a per-version orphan list, which PruneVersionsTo consumes (deleting the value rows) when the displacing version ages out of the retention window. The one exception is an Import: values referenced only by pre-import versions appear in no orphan list and are never reclaimed — a bounded, one-time leak per import (M21).

No content-addressed deduplication. Two Set calls with identical values each get a fresh ValueKey and a separate DB entry — there is no hash-based lookup table. This keeps the design simple (no reference counting, no "unreferenced hash" cleanup) at the cost of storage overhead when identical values are common. If your workload has highly duplicated values, dedupe at the application layer before Set.

Full SHA256 (32 bytes)

No hash truncation. ICS23 natively supports HashOp_SHA256. This avoids any need to fork the ICS23 library or define custom hash ops. Proof sizes are slightly larger than a 20-byte hash would give, but the simplicity and ICS23 compatibility are worth it.

Mini merkle tree within each node

Each node's hash is the root of a binary merkle tree over all B=32 slots. This collapses the B+ tree into what ICS23 sees as a uniform chain of binary InnerOps — a single InnerSpec works for all levels.

Domain separation follows RFC 6962:

  • Leaf slot: SHA256(0x00 || varint(len(key)) || key || 0x20 || SHA256(value))
  • Inner: SHA256(0x01 || left || right)
  • Sentinel: SHA256(0x02) for empty slots

The sentinel uses a short-circuit rule: if both children are the sentinel, the result is the sentinel (not SHA256(0x01 || sentinel || sentinel)). This ensures EmptyChild in the ICS23 spec works correctly at all mini-merkle depths for non-membership proofs.

The leaf slot hash includes varint length prefixes to match ICS23's LengthOp_VAR_PROTO exactly. Without this, proofs fail verification.

Mini merkle intermediates are not serialized to disk — only the leaf-level hashes (childHashes/valueHashes) are persisted. The full binary tree is cached in memory (miniTree [2*B][32]byte) and recomputed on load (~31 SHA256 calls per node, ~1.9μs). Incremental updates via SetSlot recompute only 5 hashes per slot change.

No leaf sibling pointers

B+ trees traditionally link leaves for fast range scans. In an immutable/COW tree, updating a sibling pointer on split requires cloning the neighbor leaf and its entire ancestor path — a cascade that doubles the write cost of every split.

Instead, both ascending and descending iteration use a stack-based traversal: a stack of (innerNode, childIndex) pairs. When a leaf is exhausted, pop the stack to find the parent, advance (or retreat) the child index, and descend to the next leaf. The amortized cost is O(1) node loads per leaf transition — the same as sibling pointers.

90/10 split for sequential keys

When the inserted key is larger than all existing keys in the leaf (append pattern), the leaf splits asymmetrically: left gets B-1=31 keys, right gets 2 keys. Without this, sequential inserts produce ~50% fill (each left half freezes at 16/32). With 90/10 splits, leaves stay ~97% full. Detection: insertPos == B.

For random inserts, the standard 50/50 split is used.

Copy-on-write versioning

Every Set/Remove clones the root-to-leaf path. Unchanged subtrees are shared between versions. SaveVersion assigns NodeKey(version, nonce) to each dirty node and batch-writes them to the DB. The root reference R<version> stores the root's NodeKey + hash (44 bytes).

If a version already exists with a different hash, SaveVersion returns an error (matching IAVL behavior — prevents accidental overwrites).

Rollback discards COW'd nodes and reverts to the last saved snapshot.

Pruning via dual-tree-walk

No orphan index. To prune version V, walk V's tree and V+1's tree simultaneously. At each inner node, compare child hash sets (not positions — children may shift due to splits/merges). Matching hashes mean shared subtrees — skip. Unmatched hashes mean orphaned nodes — delete recursively. Cost: O(changed nodes per version).

Lazy node loading

LoadVersion loads only the root node from the DB. Children are loaded on demand by getChild, which checks childNodes[idx], and if nil, loads from DB via the ndb reference stored on each InnerNode. The 10K-node LRU cache prevents repeated DB hits for hot inner nodes.

ICS23 proof system

The BptreeSpec defines:

  • LeafOp: prefix 0x00, PrehashValue=SHA256, Length=VAR_PROTO
  • InnerSpec: ChildOrder=[0,1], prefix length 1 (0x01), EmptyChild=SHA256(0x02)
  • MinDepth=5 (at least one mini-merkle traversal), MaxDepth=60

Membership proofs: collect the path from root to leaf, then for each node emit log₂(B)=5 InnerOps from the mini merkle sibling path. Total: 5 × tree_height InnerOps + 1 LeafOp.

Non-membership proofs: find the two adjacent keys bracketing the missing key, produce existence proofs for both. ICS23's IsLeftNeighbor verifies adjacency using the EmptyChild sentinel for boundary checks.

Nil values rejected

Set(key, nil) returns an error, matching IAVL behavior. Use []byte{} for empty values.

Store integration

tm2/pkg/store/bptree provides a CommitStore wrapper that satisfies the same interfaces as tm2/pkg/store/iavl:

  • types.Store, types.CommitStore, types.Queryable, types.DepthEstimator
  • StoreConstructor is a drop-in replacement for iavl.StoreConstructor

The bptree proof decoder is registered alongside IAVL and simple merkle in DefaultProofRuntime — both proof types coexist.

Package structure

tm2/pkg/bptree/
  const.go           B=32, HashSize=32, domain separators, sentinel
  errors.go          Sentinel errors (ErrVersionDoesNotExist, etc.)
  logger.go          Logger interface and NopLogger
  options.go         Options struct and functional option constructors
  hash.go            SHA256 helpers, leaf slot hash, inner hash with short-circuit
  mini_merkle.go     Binary merkle over B slots, incremental updates, sibling path
  node.go            InnerNode, LeafNode, serialization, lazy getChild
  node_key.go        NodeKey (version + nonce), encoding
  search.go          Binary search within sorted node arrays
  insert.go          Insert with COW, split propagation
  split.go           50/50 and 90/10 leaf/inner splits
  remove.go          Remove with COW, merge/redistribute
  mutable_tree.go    MutableTree: Set, Get, Remove, SaveVersion, LoadVersion, ...
  immutable_tree.go  ImmutableTree: read-only snapshot with value resolution
  iterator.go        Stack-based ascending/descending iterator
  nodedb.go          DB persistence, LRU cache, version tracking, batch writes
  export.go          Post-order tree export with value inlining
  import.go          Tree reconstruction from export stream
  proof_spec.go      BptreeSpec for ICS23
  proof.go           Membership and non-membership proof generation/verification
  prune.go           Dual-tree-walk pruning

tm2/pkg/store/bptree/
  store.go           CommitStore wrapper, Query, Iterator, proof integration
  tree.go            Tree interface adapters (mutable/immutable)

Differences from IAVL

Aspect IAVL B+32
Structure Binary AVL+ B+ tree, B=32
Height (100M items) ~28 ~6
Node size ~100B ~1.7KB
Value storage Inline in leaf Out-of-line by hash
Fast node index Yes (separate KV index) No (tree is fast enough)
Proof hash includes height, size, version Nothing (pure merkle)
Proof type ics23:iavl ics23:bptree
Leaf iteration Goroutine + channel Synchronous stack
Orphan tracking Explicit orphan index Dual-tree-walk (no index)
Node loading Eager (full tree) Lazy (on demand)
Copy semantics Values shared by reference Values copied (keyed by ValueKey, not content-addressed)

Testing

314 tests covering:

  • 202 B+ tree specific tests (internals, edge cases, golden vectors)
  • 112 ported IAVL behavioral tests (identical function names)
go test ./tm2/pkg/bptree/ ./tm2/pkg/store/bptree/

Documentation

Index

Constants

View Source 
const (
	// B is the branching factor. Inner nodes have up to B children
	// and B-1 separator keys. Leaf nodes have up to B key-value pairs.
	B = 32

	// MinKeys is the minimum occupancy for non-root nodes (B/2).
	MinKeys = B / 2

	// HashSize is the size of a SHA256 hash in bytes.
	HashSize = sha256.Size // 32

	// NodeKeySize is the size of a serialized NodeKey (version:8 + nonce:4).
	NodeKeySize = 12

	// Domain separator prefix bytes (RFC 6962).
	DomainLeaf  byte = 0x00
	DomainInner byte = 0x01
	DomainEmpty byte = 0x02

	// DB key prefixes.
	PrefixNode   byte = 'B'
	PrefixVal    byte = 'V'
	PrefixRoot   byte = 'R'
	PrefixMeta   byte = 'M'
	PrefixOrphan byte = 'O'
	// PrefixFast keys the optional latest-version fast index (user-key →
	// version‖value). It is an unauthenticated read accelerator outside the
	// Merkle commitment; see fast_index.go. PrefixMeta‖"fastidx" stamps the
	// version it is complete for.
	PrefixFast byte = 'F'

	// Node type bytes for serialization.
	TypeInner byte = 0x01
	TypeLeaf  byte = 0x02
)
View Source 
const MaxKeyLen = 1 << 20 // 1 MiB

MaxKeyLen caps how long a single key can be. Must stay at or below maxReadBytesLen in node.go — if we ever accepted a key larger than the read cap, the node would serialize successfully but fail to deserialize, permanently wedging that version of the tree.

Variables

View Source 
var (
	ErrVersionDoesNotExist = errors.New("version does not exist")
	ErrKeyDoesNotExist     = errors.New("key does not exist")
	ErrExportDone          = errors.New("export done")
	ErrNotInitializedTree  = errors.New("tree not initialized")
	ErrNoImport            = errors.New("no import in progress")
	ErrNodeMissingNodeKey  = errors.New("node missing node key")
	ErrEmptyTree           = errors.New("tree is empty")
	ErrActiveReaders       = errors.New("version has active readers")
	ErrEmptyKey            = errors.New("key must not be empty")
	ErrNoCommittedState    = errors.New("no committed state: call SaveVersion before generating proofs")
	ErrKeyTooLong          = errors.New("key exceeds maximum size")
	ErrUnsupported         = errors.New("operation not supported")
	ErrUncommittedChanges  = errors.New("uncommitted working-session changes")
	ErrChecksumMismatch    = errors.New("record checksum mismatch")
	// ErrSessionPoisoned wraps (via %w on the sentinel, with the original
	// failure flattened into the message) the first error that left the
	// working session inconsistent. Set/Remove/SaveVersion refuse while it is
	// set; Rollback or a successful LoadVersion clears it.
	ErrSessionPoisoned = errors.New("session poisoned by an earlier failure: Rollback before continuing")
)
View Source 
var BptreeSpec = &ics23.ProofSpec{
	LeafSpec: &ics23.LeafOp{
		Prefix:       []byte{DomainLeaf},
		PrehashKey:   ics23.HashOp_NO_HASH,
		PrehashValue: ics23.HashOp_SHA256,
		Hash:         ics23.HashOp_SHA256,
		Length:       ics23.LengthOp_VAR_PROTO,
	},
	InnerSpec: &ics23.InnerSpec{
		ChildOrder:      []int32{0, 1},
		MinPrefixLength: 1,
		MaxPrefixLength: 1,
		ChildSize:       int32(HashSize),
		EmptyChild:      sentinelHash[:],
		Hash:            ics23.HashOp_SHA256,
	},
	MinDepth: 5,
	MaxDepth: 60,
}

BptreeSpec is the ICS23 ProofSpec for the B+ tree. The mini merkle collapses into a uniform chain of binary InnerOps.

Functions

This section is empty.

Types

type ExportNode 

type ExportNode struct {
	Key           []byte
	Value         []byte   // actual value (inlined, not hash)
	Height        int8     // 0=leaf entry, -1=leaf boundary marker, >0=inner marker
	NumKeys       int16    // leaf boundary: keys in this leaf; inner: separator key count
	SeparatorKeys [][]byte // inner marker only: all separator keys
}

ExportNode is the format for export/import streaming.

type Exporter 

type Exporter struct {
	// contains filtered or unexported fields
}

Exporter streams tree nodes in depth-first post-order (children before parent).

Lifecycle: the caller MUST Close the Exporter when done — including on error or early return (use defer). Close stops the streaming goroutine and releases the version-reader reservation taken by Export. Abandoning an Exporter without Close leaks that goroutine (it blocks once the 32-entry channel buffer fills, i.e. for any tree with >32 nodes) AND permanently pins its version against pruning: PruneVersionsTo of that version returns ErrActiveReaders, and the store's auto-prune at Commit panics on it. Fully consuming the stream (Next until ErrExportDone) lets the goroutine exit but does NOT release the reservation — Close is still required. Close is idempotent.

func (*Exporter) Close 

func (e *Exporter) Close()

Close releases the exporter and decrements version readers. Safe to call multiple times. The goroutine exits promptly without needing to drain the channel.

func (*Exporter) Next 

func (e *Exporter) Next() (*ExportNode, error)

Next returns the next ExportNode, or ErrExportDone when finished.

type Hash 

type Hash = [HashSize]byte

Hash is a fixed-size SHA256 hash.

func HashInner 

func HashInner(left, right Hash) Hash

HashInner computes an inner mini-merkle node hash: 

SHA256(0x01 || left || right)

If both left and right are the sentinel, returns the sentinel (short-circuit rule for ICS23 EmptyChild compatibility).

func HashLeafSlot 

func HashLeafSlot(key, value []byte) Hash

HashLeafSlot computes the hash for an occupied leaf slot: 

SHA256(0x00 || varint(len(key)) || key || varint(32) || SHA256(value))

This matches ICS23 LeafOp with Prefix=0x00, PrehashValue=SHA256, Length=VAR_PROTO.

func HashLeafSlotFromValueHash 

func HashLeafSlotFromValueHash(key []byte, valueHash Hash) Hash

HashLeafSlotFromValueHash computes the leaf slot hash from a pre-computed value hash. 

SHA256(0x00 || varint(len(key)) || key || 0x20 || valueHash)

type ImmutableTree 

type ImmutableTree struct {
	// contains filtered or unexported fields
}

ImmutableTree is a read-only snapshot of the tree at a specific version. It is safe for concurrent reads. Created by MutableTree.GetImmutable() or by snapshotting the root after SaveVersion.

When the snapshot is backed by a DB, ndb is non-nil. Iterators and exporters created from it register as version readers (via ndb.incrVersionReaders) so that PruneVersionsTo cannot delete nodes they still depend on.

func NewImmutableTree 

func NewImmutableTree(root Node, version int64) *ImmutableTree

NewImmutableTree creates an ImmutableTree from a root node and version.

func (*ImmutableTree) Close 

func (t *ImmutableTree) Close() error

Close releases this snapshot's version-reader reservation, if it holds one, allowing a prune of its version to proceed. It is idempotent (sync.Once) so double or concurrent Close cannot over-decrement. A snapshot from GetImmutable or proof generation is registered and MUST be Closed; unregistered snapshots (Snapshot, GetImmutableUnregistered) make Close a no-op.

func (*ImmutableTree) Export 

func (t *ImmutableTree) Export(ndb *nodeDB) (*Exporter, error)

Export creates an Exporter for the tree. The tree's version is protected from pruning via a version reader held for the Exporter's lifetime; the caller MUST Close the returned Exporter (use defer) to release it — see the Exporter docs.

func (*ImmutableTree) Get 

func (t *ImmutableTree) Get(key []byte) ([]byte, error)

Get returns the value for a key, or nil if not found.

func (*ImmutableTree) GetByIndex 

func (t *ImmutableTree) GetByIndex(index int64) ([]byte, []byte, error)

GetByIndex returns the key and value at the given index.

func (*ImmutableTree) GetMembershipProof 

func (t *ImmutableTree) GetMembershipProof(key []byte) (*ics23.CommitmentProof, error)

GetMembershipProof generates an ICS23 existence proof for a key. Proofs over empty-valued keys generate but can never verify: ics23's LeafOp rejects empty values (the value-side twin of the empty-key constraint; IAVL behaves identically). See TestProof_EmptyValueUnprovable.

func (*ImmutableTree) GetNonMembershipProof 

func (t *ImmutableTree) GetNonMembershipProof(key []byte) (*ics23.CommitmentProof, error)

GetNonMembershipProof generates an ICS23 non-existence proof for a key. The proof embeds the gap's neighbor existence proofs, so it cannot verify when an adjacent key holds an empty value (see GetMembershipProof).

func (*ImmutableTree) GetWithIndex 

func (t *ImmutableTree) GetWithIndex(key []byte) (int64, []byte, error)

GetWithIndex returns the index, value, and whether the key was found.

func (*ImmutableTree) Has 

func (t *ImmutableTree) Has(key []byte) (bool, error)

Has returns true if the key exists.

func (*ImmutableTree) Hash 

func (t *ImmutableTree) Hash() []byte

Hash returns the root hash. Returns SHA256("") for empty trees, matching IAVL.

func (*ImmutableTree) Height 

func (t *ImmutableTree) Height() int8

Height returns the tree height.

func (*ImmutableTree) IsEmpty 

func (t *ImmutableTree) IsEmpty() bool

IsEmpty returns true if the tree has no keys.

func (*ImmutableTree) Iterate 

func (t *ImmutableTree) Iterate(fn func(key []byte, value []byte) bool) (bool, error)

Iterate calls fn for each key-value pair in sorted order. If a value resolver is set, values are resolved to actual bytes.

func (*ImmutableTree) IterateRange 

func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key, value []byte) bool) (stopped bool, err error)

IterateRange iterates over [start, end) calling fn. Stops early if fn returns true. A value-resolution or node-load failure is returned as err — fn is never called with the failing row, and stopped is meaningless when err != nil.

func (*ImmutableTree) Iterator 

func (t *ImmutableTree) Iterator(start, end []byte, ascending bool) (*Iterator, error)

ImmutableTree.Iterator returns an iterator over [start, end).

When the immutable tree is DB-backed (t.ndb != nil), the iterator registers as a version reader so concurrent pruning cannot delete the nodes it walks. The reader is released on Close. For snapshot-only trees without an ndb, values are resolved via t.valueResolver (no version tracking needed).

func (*ImmutableTree) SetValueResolver 

func (t *ImmutableTree) SetValueResolver(resolver ValueResolver)

SetValueResolver sets the function used to resolve valueKeys to raw values.

func (*ImmutableTree) Size 

func (t *ImmutableTree) Size() int64

Size returns the total number of key-value pairs.

func (*ImmutableTree) VerifyMembership 

func (t *ImmutableTree) VerifyMembership(proof *ics23.CommitmentProof, key []byte) (bool, error)

VerifyMembership verifies an ICS23 existence proof against the tree's root hash. The value is taken from the proof itself (no tree lookup needed).

func (*ImmutableTree) VerifyNonMembership 

func (t *ImmutableTree) VerifyNonMembership(proof *ics23.CommitmentProof, key []byte) (bool, error)

VerifyNonMembership verifies an ICS23 non-existence proof.

func (*ImmutableTree) Version 

func (t *ImmutableTree) Version() int64

Version returns the version of this snapshot.

type Importer 

type Importer struct {
	// contains filtered or unexported fields
}

Importer reconstructs a tree from a stream of ExportNodes, preserving the exact tree structure (and thus the root hash).

The stream is structurally validated as it arrives: leaf keys must be strictly ascending across the whole stream, every leaf marker must drain the entry buffer exactly, separators must sit in the window (max(left child) < sep <= min(right child)), and inner heights must equal derived child height + 1. Combined with the caller's final root-hash check against a trusted app hash (which covers keys, value hashes, and shape), a malicious stream cannot produce a tree that mis-routes reads. The one residual freedom — a separator moved WITHIN its window under an unchanged root hash — does not affect reads, iteration, or pruning; its first consequence is an app-hash mismatch at the first write that routes differently, which halts the node loudly.

func (*Importer) Add 

func (imp *Importer) Add(node *ExportNode) error

Add adds an ExportNode to the tree being imported. Nodes must arrive in depth-first post-order as produced by the Exporter. A validation failure leaves the importer's stack and buffer untouched, but values staged by earlier Adds remain staged until Close (which rolls the session back) — a rejected stream must be Closed, not Committed.

func (*Importer) Close 

func (imp *Importer) Close() error

Close releases the importer. If the import was not committed (abandoned, rejected stream, or failed Commit), the staged session state — value records Add wrote into the shared batch, and any root/version mutation a failed Commit left behind — is rolled back; otherwise those value records would ride into the NEXT commit as unreferenced, unreclaimable records in a future version's namespace. Idempotent; safe after Commit.

func (*Importer) Commit 

func (imp *Importer) Commit() error

Commit finalizes the import by saving the version.

The caller wiring state-sync MUST compare the committed version's hash against the consensus-trusted app hash: the structural checks in Add cover what the hash cannot (separator windows, heights), and the hash covers what the checks cannot (keys, value hashes, shape). An empty stream commits an empty tree — accepted for tests, though no honest Exporter can produce it (Export fails on an empty tree), so a state-sync caller should treat it like any other hash mismatch.

type InnerNode 

type InnerNode struct {
	// contains filtered or unexported fields
}

InnerNode stores separator keys and child references. It has numKeys separator keys and numKeys+1 children.

func (*InnerNode) Clone 

func (n *InnerNode) Clone() *InnerNode

Clone creates a shallow copy of the node with nodeKey set to nil (marking it as unsaved/new for COW). Keys and childNodes are shared slice/pointer references (COW-safe: keys are never mutated in-place, only replaced by shifting). The ndb reference is preserved for lazy loading.

func (*InnerNode) GetNodeKey 

func (n *InnerNode) GetNodeKey() *NodeKey

func (*InnerNode) Hash 

func (n *InnerNode) Hash() Hash

Hash returns the mini merkle root of the node.

func (*InnerNode) NumChildren 

func (n *InnerNode) NumChildren() int

NumChildren returns the number of children (numKeys + 1).

func (*InnerNode) RebuildMiniMerkle 

func (n *InnerNode) RebuildMiniMerkle()

RebuildMiniMerkle recomputes the full mini merkle tree from the slot-level hashes. For InnerNode, slots are childHashes. For LeafNode, slots are HashLeafSlotFromValueHash(key, valueHash). Cost: B-1 = 31 SHA256 calls (sets leaf slots directly, then Build).

func (*InnerNode) Serialize 

func (n *InnerNode) Serialize(w io.Writer) error

func (*InnerNode) SetNodeKey 

func (n *InnerNode) SetNodeKey(nk *NodeKey)

type Iterator 

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator traverses key-value pairs in a B+ tree within a [start, end) range. Implements the same contract as tm2/pkg/db.Iterator. Uses a stack of (innerNode, childIndex) pairs for traversal — no leaf sibling pointers needed.

func NewIteratorWithNDB 

func NewIteratorWithNDB(imm *ImmutableTree, start, end []byte, ascending bool, mtree *MutableTree) *Iterator

NewIteratorWithNDB creates an iterator over an immutable tree with value resolution via the mutable tree's nodeDB. Used by the store wrapper.

When the immutable tree carries a DB-backed ndb, the iterator registers as a version reader on imm.version so that concurrent PruneVersionsTo cannot delete nodes this iterator still walks. The reader is released on Close.

func (*Iterator) Close 

func (it *Iterator) Close() error

func (*Iterator) Domain 

func (it *Iterator) Domain() (start, end []byte)

func (*Iterator) Error 

func (it *Iterator) Error() error

func (*Iterator) Key 

func (it *Iterator) Key() []byte

func (*Iterator) Next 

func (it *Iterator) Next()

func (*Iterator) Valid 

func (it *Iterator) Valid() bool

func (*Iterator) Value 

func (it *Iterator) Value() []byte

type LeafNode 

type LeafNode struct {
	// contains filtered or unexported fields
}

LeafNode stores sorted key-value hash pairs.

func (*LeafNode) Clone 

func (n *LeafNode) Clone() *LeafNode

func (*LeafNode) GetNodeKey 

func (n *LeafNode) GetNodeKey() *NodeKey

func (*LeafNode) Hash 

func (n *LeafNode) Hash() Hash

func (*LeafNode) RebuildMiniMerkle 

func (n *LeafNode) RebuildMiniMerkle()

func (*LeafNode) Serialize 

func (n *LeafNode) Serialize(w io.Writer) error

func (*LeafNode) SetNodeKey 

func (n *LeafNode) SetNodeKey(nk *NodeKey)

type Logger 

type Logger interface {
	Info(msg string, keyVals ...any)
	Warn(msg string, keyVals ...any)
	Error(msg string, keyVals ...any)
	Debug(msg string, keyVals ...any)
}

Logger is the interface for tree logging.

func NewNopLogger 

func NewNopLogger() Logger

NewNopLogger returns a Logger that discards all output.

type MiniMerkle 

type MiniMerkle struct {
	// contains filtered or unexported fields
}

MiniMerkle is a binary merkle tree over B slots, stored as a heap-style array of size 2*B. Index 1 is the root. Indices B..2B-1 are the leaf-level slots. Index 0 is unused.

The tree uses the sentinel short-circuit rule: if both children are the sentinel, the parent is the sentinel (not SHA256(0x01 || sentinel || sentinel)). This ensures ICS23 EmptyChild compatibility at all depths.

func NewMiniMerkle 

func NewMiniMerkle() MiniMerkle

NewMiniMerkle creates a MiniMerkle with all slots set to the sentinel.

func (*MiniMerkle) Build 

func (m *MiniMerkle) Build()

Build recomputes the entire mini merkle tree from the leaf-level slots. Cost: B-1 = 31 SHA256 calls for B=32.

func (*MiniMerkle) Clear 

func (m *MiniMerkle) Clear()

Clear sets all slots to the sentinel hash.

func (*MiniMerkle) GetSlot 

func (m *MiniMerkle) GetSlot(index int) Hash

GetSlot returns the hash at leaf-level slot index (0..B-1).

func (*MiniMerkle) Root 

func (m *MiniMerkle) Root() Hash

Root returns the mini merkle root hash (index 1).

func (*MiniMerkle) SetSlot 

func (m *MiniMerkle) SetSlot(index int, h Hash)

SetSlot sets the hash at leaf-level slot index (0..B-1) and recomputes the path from that slot to the root. Cost: log₂(B) = 5 SHA256 calls.

func (*MiniMerkle) SiblingPath 

func (m *MiniMerkle) SiblingPath(index int) (siblings []Hash, positions []int)

SiblingPath returns the log₂(B) sibling hashes needed to prove that slot[index] is part of the mini merkle root. The path goes from the leaf level toward the root. Each entry is the sibling's hash at that level. Also returns the position indices (0=left child, 1=right child) indicating which side the proven slot is on at each level.

type MutableTree 

type MutableTree struct {
	// contains filtered or unexported fields
}

MutableTree is the working (writable) B+ tree: Set, Get, Has, Remove, SaveVersion, LoadVersion, Rollback, pruning, proofs, and iteration.

Concurrency

A MutableTree is SINGLE-GOROUTINE. Its mutators (Set, Remove, SaveVersion, LoadVersion, Load, Rollback, DeleteVersionsTo, PruneVersionsTo, Import, SetInitialVersion) and its working-tree reads (Get, Has, Hash, WorkingHash, Version, WorkingVersion, Size, IsEmpty, Height, Iterate, Iterator, GetByIndex, GetWithIndex, GetValueByKey, GetMembershipProof, GetNonMembershipProof, Snapshot) read and write the working-tree fields (root, lastSaved, version, size, nextValueNonce, versionOrphans) WITHOUT locking, so none of them may be called concurrently with each other or with a mutator.

For concurrent reads at a COMMITTED version, call GetImmutable(version) — it is safe to call concurrently with the writer (it reads only the internally-synchronized nodeDB, never the working-tree fields) — and read the returned ImmutableTree, which is safe for concurrent reads against an active writer; Close it when done (it holds a version-reader reservation that blocks pruning of that version until released). GetVersioned, GetCommittedValueByKey, VersionExists, and AvailableVersions are likewise safe to call concurrently with the writer.

The gno ABCI path satisfies this contract by serializing all store access through the connection mutex.

func NewMutableTreeWithDB 

func NewMutableTreeWithDB(db dbm.DB, cacheSize int, logger Logger, options ...Option) *MutableTree

NewMutableTreeWithDB creates a DB-backed MutableTree.

func (*MutableTree) AvailableVersions 

func (t *MutableTree) AvailableVersions() []int

AvailableVersions returns all available version numbers.

func (*MutableTree) Close 

func (t *MutableTree) Close() error

Close closes the tree and its underlying DB resources.

func (*MutableTree) DeleteVersionsFrom 

func (t *MutableTree) DeleteVersionsFrom(_ int64) error

DeleteVersionsFrom is not supported — it would leak values and nodes. Not called by gno.land, the SDK, or the store layer.

func (*MutableTree) DeleteVersionsTo 

func (t *MutableTree) DeleteVersionsTo(toVersion int64) error

DeleteVersionsTo deletes versions from first to toVersion (inclusive), including orphaned nodes via dual-tree-walk pruning.

func (*MutableTree) Get 

func (t *MutableTree) Get(key []byte) ([]byte, error)

Get retrieves the value for a key.

func (*MutableTree) GetByIndex 

func (t *MutableTree) GetByIndex(index int64) ([]byte, []byte, error)

GetByIndex returns the key and value at the given zero-based index.

func (*MutableTree) GetCommittedValueByKey 

func (t *MutableTree) GetCommittedValueByKey(vk []byte) ([]byte, error)

GetCommittedValueByKey resolves a valueKey to the raw value bytes from the DB ONLY (never the uncommitted working-session buffer). It is the race-free read for cross-package committed-snapshot consumers (the store's GetImmutable / proof resolvers), which run concurrently with the writer.

func (*MutableTree) GetImmutable 

func (t *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)

GetImmutable returns a committed read-only snapshot at version, REGISTERED as a version reader: a concurrent PruneVersionsTo(version) is blocked until the snapshot is Closed. Callers MUST Close it (else that version can never prune).

func (*MutableTree) GetImmutableUnregistered 

func (t *MutableTree) GetImmutableUnregistered(version int64) (*ImmutableTree, error)

GetImmutableUnregistered returns a committed read-only snapshot WITHOUT registering as a version reader. For long-lived snapshots that have no Close hook (e.g. the store's immutable LoadVersion view) — registering them would pin the version against pruning forever. Such a snapshot is not protected against a concurrent prune of its version (acceptable: prune and queries are serialized by the ABCI mutex today).

func (*MutableTree) GetMembershipProof 

func (t *MutableTree) GetMembershipProof(key []byte) (*ics23.CommitmentProof, error)

GetMembershipProof returns an ICS23 existence proof for key against the last committed version (verifiable against MutableTree.Hash()), not the working tree. Returns ErrNoCommittedState if no version has been committed yet, or ErrEmptyTree if the committed tree is empty.

Single-goroutine: it reads the working tree's lastSaved/version (see the MutableTree concurrency contract). For concurrent or historical proofs, use GetImmutable(version).GetMembershipProof instead.

func (*MutableTree) GetNonMembershipProof 

func (t *MutableTree) GetNonMembershipProof(key []byte) (*ics23.CommitmentProof, error)

GetNonMembershipProof returns an ICS23 non-existence proof for key against the last committed version (verifiable against MutableTree.Hash()), not the working tree. Returns ErrNoCommittedState if no version has been committed yet, or ErrEmptyTree if the committed tree is empty.

Single-goroutine: it reads the working tree's lastSaved/version (see the MutableTree concurrency contract). For concurrent or historical proofs, use GetImmutable(version).GetNonMembershipProof instead.

func (*MutableTree) GetValueByKey 

func (t *MutableTree) GetValueByKey(vk []byte) ([]byte, error)

GetValueByKey resolves a valueKey to the raw value bytes, consulting the uncommitted working-session buffer first (read-your-writes). Safe only on the single writer goroutine.

func (*MutableTree) GetVersioned 

func (t *MutableTree) GetVersioned(key []byte, version int64) ([]byte, error)

GetVersioned returns the value for a key at a specific version.

func (*MutableTree) GetWithIndex 

func (t *MutableTree) GetWithIndex(key []byte) (int64, []byte, error)

GetWithIndex returns the index, value, and whether the key was found.

func (*MutableTree) Has 

func (t *MutableTree) Has(key []byte) (bool, error)

Has returns true if the key exists in the tree.

func (*MutableTree) Hash 

func (t *MutableTree) Hash() []byte

Hash returns the root hash of the last saved version. Returns SHA256("") for empty trees, matching IAVL behavior.

func (*MutableTree) Height 

func (t *MutableTree) Height() int8

Height returns the tree height.

func (*MutableTree) Import 

func (t *MutableTree) Import(version int64) (*Importer, error)

Import creates an Importer that will reconstruct a tree at the given version.

The target version must be beyond the latest committed version: importing into the live key namespace would overwrite node/value records shared with retained versions (silent corruption). Import then rolls back any uncommitted working-session state (pending batch, orphan list, value-nonce counter) so stale state from a prior un-committed session cannot leak into the import's SaveVersion. Import rebuilds the root from scratch, so reverting t.root to lastSaved here is harmless.

func (*MutableTree) IsEmpty 

func (t *MutableTree) IsEmpty() bool

IsEmpty returns true if the tree has no keys.

func (*MutableTree) Iterate 

func (t *MutableTree) Iterate(fn func(key []byte, value []byte) bool) (bool, error)

Iterate calls fn for each key-value pair in sorted order. Values are resolved from the value store.

func (*MutableTree) IterateRange 

func (t *MutableTree) IterateRange(start, end []byte, ascending bool, fn func(key, value []byte) bool) (stopped bool, err error)

IterateRange on MutableTree. Same contract as ImmutableTree.IterateRange.

func (*MutableTree) Iterator 

func (t *MutableTree) Iterator(start, end []byte, ascending bool) (*Iterator, error)

Iterator returns an iterator over [start, end) in the given direction. MutableTree iterators walk the in-memory working tree and do not take a version reader: pruning rejects toVersion >= latest, and a working tree loaded at an older version is protected by the working-tree-reader guard (PruneVersionsTo rejects t.version <= toVersion with ErrActiveReaders).

func (*MutableTree) Load 

func (t *MutableTree) Load() (int64, error)

Load loads the latest version from the DB.

func (*MutableTree) LoadVersion 

func (t *MutableTree) LoadVersion(version int64) (int64, error)

LoadVersion loads a specific version from the DB.

All fallible reads happen BEFORE the working session is discarded: on any error the previous session survives fully intact (a failed load must not wipe staged values the working tree still references — committing that would persist dangling valueKeys).

func (*MutableTree) LoadVersionForOverwriting 

func (t *MutableTree) LoadVersionForOverwriting(_ int64) error

LoadVersionForOverwriting is not supported — it would leak values and nodes. Not called by gno.land, the SDK, or the store layer.

func (*MutableTree) PruneVersionsTo 

func (t *MutableTree) PruneVersionsTo(toVersion int64) error

PruneVersionsTo deletes all versions from firstVersion through toVersion (inclusive), removing orphaned nodes via the dual-tree-walk algorithm. Sharing with the successor is decided by NodeKey record identity (COW shares records by reference; content hashes can collide across distinct records).

func (*MutableTree) Remove 

func (t *MutableTree) Remove(key []byte) ([]byte, bool, error)

Remove removes a key from the tree. Returns the old value and whether the key was found.

func (*MutableTree) Rollback 

func (t *MutableTree) Rollback()

Rollback discards all mutations since the last save. Values staged this session live only in the uncommitted batch, so discarding it drops them — nothing was written to the DB to clean up.

func (*MutableTree) SaveVersion 

func (t *MutableTree) SaveVersion() (rootHash []byte, savedVersion int64, err error)

SaveVersion persists the current tree state as a new version. Returns (rootHash, version, error).

func (*MutableTree) Set 

func (t *MutableTree) Set(key, value []byte) (updated bool, err error)

Set inserts or updates a key-value pair. Returns true if the key already existed (update), false if it was a new insert.

func (*MutableTree) SetInitialVersion 

func (t *MutableTree) SetInitialVersion(version uint64)

SetInitialVersion sets the version number for the first SaveVersion.

func (*MutableTree) Size 

func (t *MutableTree) Size() int64

Size returns the total number of key-value pairs.

func (*MutableTree) Snapshot 

func (t *MutableTree) Snapshot(version int64) *ImmutableTree

Snapshot creates an ImmutableTree snapshot of the current working tree with a properly wired value resolver. For tests and lightweight snapshots.

The snapshot wraps the LIVE working tree, whose most recent Sets may live only in pendingVals (uncommitted), so it resolves with read-your-writes (committed=false). It is a single-writer-only convenience: unlike GetImmutable, it is NOT safe to read concurrently with the writer.

func (*MutableTree) Version 

func (t *MutableTree) Version() int64

Version returns the last saved version.

func (*MutableTree) VersionExists 

func (t *MutableTree) VersionExists(version int64) bool

VersionExists returns true if the given version exists.

func (*MutableTree) WorkingHash 

func (t *MutableTree) WorkingHash() []byte

WorkingHash computes the hash of the current unsaved working tree. Returns SHA256("") for empty trees, matching IAVL behavior.

func (*MutableTree) WorkingVersion 

func (t *MutableTree) WorkingVersion() int64

WorkingVersion returns the version that will be used by the next SaveVersion.

type Node 

type Node interface {
	GetNodeKey() *NodeKey
	SetNodeKey(nk *NodeKey)
	Hash() Hash
	// contains filtered or unexported methods
}

Node is the interface implemented by both InnerNode and LeafNode.

func ReadNode 

func ReadNode(nk *NodeKey, data []byte) (Node, error)

ReadNode deserializes a node from bytes. Returns either *InnerNode or *LeafNode. Returns an error if the payload has trailing bytes not consumed by the type-specific decoder — a tight framing check that catches on-disk corruption early instead of silently returning a truncated view.

type NodeKey 

type NodeKey struct {
	Version int64
	Nonce   uint32
}

NodeKey identifies a node in the database: (version, nonce). Version is the tree version when the node was created. Nonce is a per-version counter distinguishing nodes within a version.

func GetNodeKey 

func GetNodeKey(key []byte) *NodeKey

GetNodeKey deserializes a NodeKey from a 12-byte slice.

func (*NodeKey) GetKey 

func (nk *NodeKey) GetKey() []byte

GetKey serializes the NodeKey to a 12-byte slice (big-endian).

type Option 

type Option func(*Options)

Option is a functional option for tree construction.

func FastIndexOption 

func FastIndexOption(b bool) Option

FastIndexOption enables the optional latest-version fast index: a flat user-key → version‖value map that accelerates committed point Gets of present keys (1 read instead of a full tree descent + value read). It is an unauthenticated read accelerator — not part of the Merkle root — so it can be toggled per-node without affecting the app hash. Default off.

func FlushThresholdOption 

func FlushThresholdOption(ft int) Option

func InitialVersionOption 

func InitialVersionOption(iv uint64) Option

func SyncOption 

func SyncOption(sync bool) Option

type Options 

type Options struct {
	Sync           bool   // fsync writes
	InitialVersion uint64 // first version number
	FlushThreshold int    // batch flush size in bytes
	FastIndex      bool   // maintain the latest-version fast index (read accelerator)
}

Options configures tree behavior.

func DefaultOptions 

func DefaultOptions() Options

type ValueResolver 

type ValueResolver func(vk []byte) ([]byte, error)

ValueResolver resolves a valueKey to the raw value bytes.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL