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 three decisions worth knowing
Backed by a B+ tree at fanout 128, not avl and not the package default of
32. 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
Raising the fanout amortises the node objects. Nothing below 592 is reachable:
the rest is the B+ tree's per-entry value box, which fanout cannot touch.
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, and 128 is not the package default of 32.
Measured against gno master 1fc4c140e on 2026-09-29, at n = 1,000 with string values: fanout 128 costs 592 bytes per entry and 152,975 gas per insert, against 671 and 162,161 at fanout 32, and against avl's 2,029 and 417,811. Raising the fanout amortises the node objects, and nothing below it can be recovered: the remaining cost is the B+ tree's per-entry value box.
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.