triple-store lattice database - C=3 Bethe lattice with Bnoun/Bverb/Bmodifier branches, B-tree indexed per branch
git clone https://git.smesh.lol/iskradb.git
Multi-branch B-tree lattice database engine. Eight independent ordered trees share a single record pool and cross-link via stable record indices. In-memory or disk-backed with crash-safe page cache.
Built in Moxie. Module: git.smesh.lol/iskradb. Zero external dependencies.
Used by iskra (lattice language model) and transdb (bilingual translation lattice).
Each branch is an independent B-tree with coordination number C=8 (each node holds up to 8 keys). All eight branches share a single record pool.
| Constant | Index | Axis | Alias |
|---|---|---|---|
Bsemantic | 0 | ontological category (animacy, abstractness) | - |
Bgrammatical | 1 | syntactic role (nominal/verbal/function) | Bnoun |
Bcooccur | 2 | PVN co-occurrence context | - |
Bmorphology | 3 | morphological state (tense/polarity/aspect) | Bverb |
Bpragmatic | 4 | domain/register context | Bmodifier |
Bphonology | 5 | phonological (dormant) | - |
Bvalency | 6 | argument count | - |
Bregister | 7 | social register | - |
Bnoun, Bverb, Bmodifier are backward-compatibility aliases.
Keys [8]Key 128 bytes 8 x 128-bit SipHash keys
RecPtrs [8]uint32 32 bytes record index per key slot
Children [9]uint32 36 bytes child node indices
Mult uint8 1 byte expansion multiplier
Flags uint8 1 byte bits 4-7: key count, bits 1-3: branch, bit 0: deleted
_pad [2]byte
DataFile uint32 4 bytes overflow file selector / flag bits
DataOff uint32 4 bytes offset into string pool (overflow path)
DataLen uint32 4 bytes data length
Link [2]uint32 8 bytes cross-branch record indices
Branch uint8 1 byte packed POS + register + domain + special
_rpad [3]byte
Inline [24]byte 24 bytes inline data store (up to 23 bytes + 1 length byte)
Records are stable across B-tree splits. Nodes move during splits and compaction; records do not. Cross-branch links (Link[0], Link[1]) use record indices and never go stale.
type Key [2]uint64 // 128-bit SipHash
Keys are opaque hashes. Default derivation: HashKey(data []byte) Key computes SipHash with a fixed seed. Callers needing domain separation prepend a domain byte before hashing.
t := lattice.NewTree(cap int) *Tree
Allocates node and record slices in memory. No flush/close needed.
t, err := lattice.Create(path string) (*Tree, error)
t, err := lattice.Open(path string) (*Tree, error)
err := t.Flush() error
err := t.Close() error
Uses a PageCache with LRU clock eviction and dirty-page tracking. Default limits: 64K cached nodes, 128K cached records.
Crash safety: region growth moves records backward (high addresses first) before updating the header. After a crash, the file is in either the pre-grow or post-grow state, never corrupted.
Disk format (version 4):
[4B] magic = "ISKR"
[2B] version = 4
[4B] nCount
[4B] rCount
[4B] pendCount (expansion queue)
[32B] roots[8]
[4B] freeHead
[4B] freeCount
[4B] nodeCap
[4B] recCap
[8B] padding
---
[nodeCap x 200B] node region
[recCap x 48B] record region
[pendCount x 4B] pending expansion queue
err := lattice.SaveFile(path string, t *Tree) error
t, err := lattice.LoadFile(path string) (*Tree, error)
For pipeline use. Serializes the full tree to a flat file (nodes + records + string pool + RecKey map).
t.Insert(branch Branch, key Key, rec Record) uint32 // returns node index
t.InsertRec(branch Branch, key Key, rec Record) uint32 // returns record index
t.InsertTriple(nounKey, verbKey, modKey Key, nRec, vRec, mRec Record)
InsertRec resets Link[0] and Link[1] to NullRec after copy. Wire links after insertion. InsertTriple inserts three records (one per branch) and wires their cross-links.
t.Lookup(branch Branch, key Key) *Record
t.LookupRecIdx(branch Branch, key Key) uint32 // returns NullRec if not found
t.GetRecord(idx uint32) *Record
t.GetNode(idx uint32) *Node
t.Linked(recIdx uint32) (uint32, uint32) // returns Link[0], Link[1]
t.Delete(branch Branch, key Key) bool
Marks the node deleted; does not reclaim memory immediately. Call Compact to reclaim.
t.Walk(branch Branch, key Key) (nodeIdx uint32, pos int, found bool)
t.WalkPath(branch Branch, key Key) []uint32 // node indices from root to target
Records carry two link slots (Link[0], Link[1]) pointing to record indices in other branches. Because record indices are stable across splits, links remain valid after any structural change.
t.CrossWalk(startRecIdx uint32, pattern WalkPattern, visit func(uint32, *Record) bool)
t.TripleWalk(nounKey, verbKey, modKey Key) (*Record, *Record, *Record)
Built-in patterns:
PatNounVerbMod // noun -> verb -> modifier -> stop
PatNounMod // noun -> modifier -> stop
PatVerbNoun // verb -> noun -> stop
PatFull // noun -> verb -> modifier -> noun (cycle, max 3 hops)
branchToLinkIndex determines which Link slot corresponds to a given transition.
A self-contained sub-tree extracted from a parent, with remapped record indices and preserved cross-links.
sl := t.ExtractBranch(branch Branch) *SubLattice
sl := t.ExtractSubtree(rootNodeIdx uint32, branch Branch, filter ExportFilter) *SubLattice
sl := t.ExtractLinked(startRecIdx uint32) *SubLattice
ExtractLinked follows Link pointers from startRecIdx across branches and collects all reachable records. Cross-links are remapped to new indices.
ExportFilter: func(nodeIdx uint32, n *Node, recIdx uint32, r *Record) bool - return false to exclude.
err := sl.SaveFile(path string) error
sl, err := lattice.LoadSubLattice(path string) (*SubLattice, error)
inserted := t.Graft(sl *SubLattice) int
Merges a SubLattice into an existing tree. Deduplicates on key. Cross-links are remapped to target indices after all records are inserted.
t.NeedsCompact() bool
reclaimed := t.Compact() int
Reclaims free nodes after deletions, resolves pending expansion entries. Safe to call at any time.
Nodes carry a Mult (expansion multiplier) byte. Expansion entries are queued as PendingExp{Branch, Depth, Factor} and resolved lazily during Compact. TritPath.Resolve(p, mult) applies the multiplier to coordinate-space navigation.
type TritPath uint32 // up to 16 trits, 2 bits each
Encodes a path through the lattice coordinate space. Trit 0 = branch selector (1=noun, 2=verb, 3=modifier). Trits 1-15 encode the path within the branch.
MakeTritPath(trits ...uint8) TritPath
BranchTritPath(b Branch) TritPath
Parent(p TritPath) TritPath
Child(p TritPath, dir uint8) TritPath
LCA(a, b TritPath) TritPath
Distance(a, b TritPath) int
Resolve(p TritPath, mult uint8) TritPath
t.RecKey map[uint32]Key // record index -> key
Maintained automatically on every Insert/InsertRec. Enables reverse lookup (record index -> key) without B-tree traversal. t.SkipRecKey disables for performance during bulk loads.
Licensed under AGPL-3.0-or-later.