The secondary index every realm with a store was writing by hand: a lookup from
a key a human typed to the store.IDs that carry it.
1import( 2"gno.land/p/moul/kit/index/v0" 3"gno.land/p/moul/kit/store/v0" 4) 5 6varnotes=store.Named("note") 7varbyTagindex.Index// the zero value is an empty, usable index 8 9funcPost(currealm,tag,bodystring)int64{10id:=notes.Add(¬e{Tag:tag,Body:body})11iferr:=byTag.Add(tag,id);err!=nil{12panic(err)// the store write is not committed either: same frame13}14returnint64(id)15}1617funcRender(pathstring)string{18for_,e:=rangebyTag.Page(1,20){// keys ascending, one page19_,_=e.Key,e.IDs20}21return""22}
Fifth package of the p/moul/kit/* layer, after ui, store, num and
tally. Live demo: r/moul/x/kitindexdemo.
What it is not
Not a multi-index record store.p/moul/collection is
that, and measured at n = 1,000 an update there costs 964,833 gas against the
508,977 that created the record, because Update removes and re-adds every
index entry for every index whether or not the indexed value changed. Two
containers written side by side cost a third of that, and the realm can see what
it is paying for.
Not a bound. An index grows with the store it indexes. The realm owns the
bound, because only the realm knows what it is willing to pay a storage deposit
for.
The decisions worth knowing
Backed by a B+ tree at fanout 32, not avl, and not 128. A wider node is
cheaper to store and to insert into, measured against gno master 1fc4c140e on
2026-09-29, n = 1,000, string values:
backing
bytes/entry
gas/insert
bptree fanout 128
592
152,975
bptree fanout 32
671
162,161
avl
2,029
417,811
But an index's keys are removed whenever its records move, and a removal
rewrites every later value in its leaf. Measured on a real node against gno
master 3cc494ec4 on 2026-10-02: removing the first key of a fanout-128 leaf
holding 120 cost 35.3M gas, the last 8.0M, about 230k per value shifted (its
values are *entry, a pointer). At 32 one removal rewrites about 45 values at
most (its own leaf, and a neighbour's when the leaf underflows and borrows), so
it is the cheaper default for something that moves.
The ids under a key are kept ascending, not in insertion order. So Lookup
depends on the set of ids and not on the order they arrived in: two realms
that indexed the same records in a different order render identically. A
Render whose output depends on insertion history is a determinism bug, and
this is where it would have come from.
Lookup and Each hand out a copy. Returning the stored slice would make
every caller a writer: an assignment into it corrupts the index with no write
path having been called. A realm that passes the result onward is passing its
own data, not a handle to ours.
The Index itself is a handle. Its state sits behind one pointer, so a copy
taken after the first write (or of anything Unique() returned) is the same
index, and Len can never disagree with Keys about what it holds.
API
New(), Unique()
many ids per key, or at most one. The zero value is New()
Add(key, id) error
idempotent for the same pair; ErrEmptyKey, ErrZeroID, ErrDuplicateKey
Keys counts keys, Len counts pairs, and the difference is the fan-out
Each(fn) bool
ascending by key; true means stop, matching bptree and kit/store. fn must not write to the index
Page(page, size) []Entry, Pages(size) int
1-based, every out-of-range page is nil (kit/store's Page returns an empty slice instead), Pages is never 0
Add returns an error rather than aborting, because a p/ package does not
know the caller's policy. In a realm the handling is almost always panic(err):
every one of the three is a bug in the realm rather than a value a user chose.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
Dependency graph:
⚠️ Disclaimer: provided as-is, without warranty; not security-audited. Full disclaimer: DISCLAIMER.
Overview
Package index is the secondary index every realm with a store was writing by hand: a lookup from a key a human typed to the [store.ID]s that carry it.
A realm keeps its records in a gno.land/p/moul/kit/store and answers "entry 7". The moment it also has to answer "every entry tagged gno" it needs a second container, and the correctness of the pair is entirely in the discipline of writing both in the same function. This package owns the second container and as much of that discipline as a package can.
Example
1var notes = store.Named("note")
2var byTag index.Index // the zero value is an empty, usable index
3 4func Post(cur realm, tag, body string) int64 {
5 id := notes.Add(¬e{Tag: tag, Body: body})
6 if err := byTag.Add(tag, id); err != nil {
7 panic(err) // the store write is not committed either: same frame
8 }
9 return int64(id)
10}
It is NOT a multi-index record store. gno.land/p/moul/collection is that, and at n = 1,000 an update there costs 964,833 gas against the 508,977 that created the record, because it re-indexes every index whether or not the indexed value changed. Two containers written side by side cost a third of that and the realm can see what it is paying for.
Fanout is the B+ tree fanout this package uses: 32, because an index's keys are removed as its records move.
A removal shifts every later value in its leaf and rewrites each one, and an index's values are pointers: measured on a real node against gno master 3cc494ec4 on 2026-10-02, removing the first key of a fanout-128 leaf holding 120 cost 35.3M gas against 8.0M for the last, about 230k per value shifted. Fanout 32 bounds what one removal rewrites to about 45 values: its own leaf, and a neighbour's when the leaf underflows and borrows. What it costs, measured against gno master 1fc4c140e on 2026-09-29 at n = 1,000 with string values: 671 bytes per entry and 162,161 gas per insert, against 592 and 152,975 at fanout 128, and avl's 2,029 and 417,811.
1var( 2// ErrEmptyKey is returned for "". An empty key sorts before every real one 3// and is almost always an unset field rather than a deliberate bucket, so 4// it is refused rather than silently indexed. 5ErrEmptyKey=errors.New("index: the key is empty") 6 7// ErrZeroID is returned for store.ID(0), which [store.Store] never assigns, 8// so indexing it can only produce a lookup that cannot hit. 9ErrZeroID=errors.New("index: the id is zero")1011// ErrDuplicateKey is returned by a [Unique] index asked to attach a second12// id to a key that already has one.13ErrDuplicateKey=errors.New("index: the key is already taken")14)
Errors an Add can return. A /p/ package returns errors and lets the realm decide whether they are fatal; every one of these is a programming error in the realm rather than a value a user chose, so panicking on them is the normal handling.
Unique returns an empty index where a key carries at most one id, and a second Index.Add to the same key fails with ErrDuplicateKey instead of appending.
Unique is a constructor rather than a field or a setter because flipping it on a populated index would have to either reject the duplicates already in it or silently keep them, and both are worse than not offering the operation.
Index maps a key to the ids carrying it, ordered by key.
The zero value is an empty, usable, non-unique index: a realm declares `var byTag index.Index` and writes to it, exactly as it does with a store.Store. Use Unique when at most one id may carry a key.
An Index is a handle, like the store.Store it sits next to: copies taken after the first write, or of anything Unique returned, are the same index, and a write through one is seen through all of them. A copy of a zero value that was never written is a separate empty index.
Adding a pair that is already present is a no-op and returns nil, so a realm re-running a write is not punished for it. The ids under a key are kept ascending, which makes Index.Lookup depend on the set of ids and not on the order they arrived in: two realms that indexed the same records in a different order render identically, and a Render whose output depends on insertion history is the determinism bug this avoids.
Each visits every key in ascending order with a copy of its ids, and stops when fn returns true. It reports whether it stopped early.
True means stop, matching bptree.IterCbFn and kit/store's EachUntil exactly, so a callback moved between them keeps its meaning.
fn must not call Index.Add, Index.Remove or Index.RemoveKey on this index. The walk is the B+ tree's own, which holds a position inside a leaf: removing the key being visited shifts the next one into that slot and the walk steps over it, and inserting one ahead of it is visited twice. Collect what to change, then change it after Each returns.
Len returns the number of (key, id) pairs, which is what the index actually costs. It is NOT Index.Keys, and the two differ by exactly the amount of fan-out a realm has.
Lookup returns the ids carrying key, ascending, or nil.
The slice is a COPY. Handing out the stored one would make every caller a writer: an append past its length would be invisible to the index, and an assignment into it would corrupt the index with no write path having been called. A realm that returns this value onward is returning its own data, not a handle to ours.
Page returns page number page of size keys, ascending, each with a copy of its ids.
Pages are 1-based, and every out-of-range page (zero, negative, past the end, any page of an empty index) returns nil rather than panicking, because the page number usually arrives from a Render path and is user input. This is NOT store.Store.Page, which returns an empty non-nil slice past the end; test with len, not with nil, when code handles both.
Remove detaches id from key and reports whether the pair was there. A key whose last id is removed is removed with it, so Index.Keys never counts an empty bucket.
