PLAN.md
18.34 Kb · 413 lines
1# Mutable B+ Tree for Gno
2
3## Goal
4
5A mutable (in-place) B+ tree with the same API as `gno.land/p/nt/avl/v0`.
6No merkle hashing, no versioning, no persistence — just a simple, efficient
7ordered map with configurable fanout.
8
9## API
10
11```go
12// Constructors
13func NewBPTreeN(fanout int) *BPTree // arbitrary fanout (minimum 4)
14func NewBPTree32() *BPTree // convenience: fanout 32
15
16// ITree interface (same as avl.ITree)
17type ITree interface {
18 Size() int
19 Has(key string) bool
20 Get(key string) (value any, exists bool)
21 GetByIndex(index int) (key string, value any)
22 Iterate(start, end string, cb IterCbFn) bool
23 ReverseIterate(start, end string, cb IterCbFn) bool
24 IterateByOffset(offset int, count int, cb IterCbFn) bool
25 ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
26 Set(key string, value any) (updated bool)
27 Remove(key string) (value any, removed bool)
28}
29
30type IterCbFn func(key string, value any) bool
31```
32
33`var _ ITree = (*BPTree)(nil)` enforces the interface at compile time.
34
35## Semantics (matching avl exactly)
36
37- `Set`: insert or update. Returns true if key already existed.
38- `Remove`: delete key. Returns (old value, true) if found.
39- `GetByIndex`: 0-based index into sorted keys. Panics on invalid index.
40- `Iterate(start, end, cb)`: ascending, start inclusive, end exclusive.
41 Empty string means no bound.
42- `ReverseIterate(start, end, cb)`: descending, start inclusive, end inclusive.
43 Empty string means no bound.
44- `IterateByOffset(offset, count, cb)`: ascending from the offset-th leaf entry
45 (0-indexed from the smallest key). Returns false if offset >= size or count <= 0.
46- `ReverseIterateByOffset(offset, count, cb)`: descending, where offset is
47 0-indexed from the largest key. offset=0 starts at the largest key,
48 offset=1 skips the largest and starts at the second-largest, etc.
49 Equivalent to: visit entries in descending order, skip `offset`, take `count`.
50- All iteration callbacks return true to stop early.
51
52## Node types
53
54### leafNode
55
56```go
57type leafNode struct {
58 keys []string // sorted, len <= fanout
59 values []*any // parallel to keys
60}
61```
62
63Leaf nodes store all key-value data. No sibling pointers — iteration
64uses stack-based traversal to avoid ref-count >= 2 (see
65[Ref-Count Safety](#ref-count-safety)).
66
67Capacity: up to `fanout` entries. Splits when full after insert.
68Minimum occupancy enforced during deletion: `fanout/2` (except the root leaf).
69Note: the 90/10 split optimization intentionally creates a right leaf with
70only 2 entries, which may be below `fanout/2` for large fanouts. This is
71standard B+ tree practice — if a subsequent Remove causes underflow, the
72normal rebalance logic (redistribute or merge) handles it.
73
74### innerNode
75
76```go
77type innerNode struct {
78 keys []string // separator keys, len = len(children)-1
79 children []node // child pointers, len <= fanout
80 sizes []int // sizes[i] = total leaf count in children[i] subtree
81}
82```
83
84`keys[i]` = minimum key of `children[i+1]` (standard B+ tree convention).
85An inner node with k separator keys has k+1 children.
86
87Capacity: up to `fanout` children (= `fanout-1` keys). Splits when full.
88Minimum occupancy: `fanout/2` children (except root, which may have as few as 2).
89
90### node interface
91
92```go
93type node interface {
94 isLeaf() bool
95 nodeSize() int // total leaf entries in subtree
96 minKey() string // leftmost key in subtree
97}
98```
99
100`nodeSize()`: leafNode returns `len(keys)` (O(1)), innerNode sums `sizes[]` (O(fanout)).
101
102Used internally so tree methods can handle both node types polymorphically.
103Type assertions to `*leafNode` or `*innerNode` are used when accessing
104type-specific fields (children, sizes).
105
106## BPTree struct
107
108```go
109type BPTree struct {
110 root node
111 size int // total number of key-value pairs
112 fanout int // max children per inner node / max entries per leaf
113}
114```
115
116No `first`/`last` pointers — they would create ref-count >= 2 on leaves.
117Full-range iteration descends from the root (O(height) to find the first
118or last leaf, amortized O(1) per entry thereafter).
119
120## Key algorithms
121
122### Search (Get, Has)
123
124Descend from root. At each inner node, binary search `keys` to find the
125child index. At the leaf, binary search `keys` for exact match.
126
127### Insert (Set)
128
1291. Descend root-to-leaf, recording the path (stack of `(innerNode, childIdx)` pairs).
1302. Binary search in the leaf for the key.
1313. If found: update value in place, return `updated=true`. No structural change.
1324. If not found: insert key-value at the sorted position.
133 - Increment `size` on the tree and all ancestor `sizes[childIdx]` entries.
134 - If the leaf now has `fanout+1` entries, **split**:
135 - **90/10 split** (append pattern): if the new key was inserted at
136 position `fanout` in the overflowed leaf (i.e., it is greater than
137 all pre-existing keys), split asymmetrically: left gets `fanout-1` entries, right
138 gets 2 entries (the last existing key + the new key). This keeps left
139 leaves ~97% full for sequential inserts.
140 - **50/50 split** (random pattern): otherwise, left gets `(fanout+1)/2`
141 (floor), right gets the rest.
142 - Create new right leaf node.
143 - Promote `right.keys[0]` as separator to the parent.
144 - Update parent's `sizes` for both children.
145 - If the parent now has `fanout+1` children, split the parent recursively.
146 - If the root splits, create a new inner root with 2 children.
147
148### Remove
149
1501. Descend root-to-leaf, recording the path.
1512. Binary search in the leaf for the key.
1523. If not found: return `(nil, false)`.
1534. If found: remove entry, decrement `size` and ancestor `sizes`.
154 - If the leaf is the root and now empty: set root to nil.
155 - If the leaf is the root and non-empty: done (root has no minimum).
156 - Otherwise, if leaf has fewer than `fanout/2` entries, **rebalance**:
157 - Try to **redistribute** from left sibling (if it has more than `fanout/2`).
158 - Try to **redistribute** from right sibling (if it has more than `fanout/2`).
159 - Otherwise **merge** with a sibling:
160 - Concatenate into the left node, remove the right child and its
161 separator from parent.
162 - Update parent's `sizes` and `size`.
163 - If parent is the root and drops to 1 child, replace root with that child.
164 - If parent is not the root and has fewer than `fanout/2` children,
165 rebalance recursively (the root is exempt — it may have as few as 2 children).
166 - If the minimum key was removed (pos == 0), update ancestor separator keys
167 before rebalancing. Rebalance operations also fix separators as needed.
168
169### Redistribute detail
170
171**Redistribute from left sibling to deficient child (both leaves):**
1721. Move left sibling's last key-value to the front of the deficient child.
1732. Update parent `keys[childIdx-1]` = deficient child's new `keys[0]` (its min key changed).
1743. Adjust parent `sizes`: decrement left's size, increment child's size.
175
176**Redistribute from right sibling to deficient child (both leaves):**
1771. Move right sibling's first key-value to the end of the deficient child.
1782. Update parent `keys[childIdx]` = right sibling's new `keys[0]` (its min key changed).
1793. Adjust parent `sizes`: decrement right's size, increment child's size.
180
181**Redistribute from left sibling to deficient child (both inner nodes):**
1821. Pull down parent's separator `keys[childIdx-1]` — **prepend** it to deficient child's keys
183 (insert at position 0, since the moved child goes to the front).
1842. Move left sibling's last child to the **front** of deficient child's children.
185 Move left sibling's last `sizes` entry to the front of deficient's sizes too.
1863. Push up left sibling's last key to replace parent's `keys[childIdx-1]`.
1874. Remove left sibling's last key, last child, and last size entry.
1885. Update parent's `sizes[childIdx-1]` and `sizes[childIdx]` to reflect
189 the new child sizes. (Parent's total size is unchanged since we just
190 moved entries between siblings.)
191
192**Redistribute from right sibling to deficient child (both inner nodes):**
1931. Pull down parent's separator `keys[childIdx]` — **append** it to deficient child's keys
194 (insert at the end, since the moved child goes to the end).
1952. Move right sibling's first child to the **end** of deficient child's children.
196 Move right sibling's first `sizes` entry to the end of deficient's sizes too.
1973. Push up right sibling's first key to replace parent's `keys[childIdx]`.
1984. Remove right sibling's first key, first child, and first size entry.
1995. Update parent's `sizes[childIdx]` and `sizes[childIdx+1]` to reflect
200 the new child sizes. (Parent's total size is unchanged.)
201
202**Merge two inner nodes:**
2031. Pull down the parent's separator between them into the left node's keys.
2042. Append all of right node's keys, children, and sizes to left node.
2053. Remove right child and its separator from parent.
2064. Update parent's `sizes` for the merged left child.
207
208### GetByIndex
209
210Use `sizes[]` at each inner node to find which child contains the i-th
211leaf entry, then descend. At the leaf, index directly into `keys[i]`/`values[i]`.
212Panics if index is out of range (matching avl behavior).
213
214### Stack-based iteration
215
216All iteration uses a stack of `(innerNode, childIndex)` pairs representing
217the path from root to the current leaf. When a leaf is exhausted, pop the
218stack, advance (or retreat) the child index, and descend to the next leaf.
219Amortized O(1) per entry — each node is pushed/popped at most once across
220the full traversal.
221
222The stack is a local slice built during iteration and discarded after —
223it creates no persistent references to nodes and does not affect ref-counts.
224
225### Iterate / ReverseIterate (key-range)
226
227**Ascending (Iterate):**
2281. Descend from root using separator keys to find the leaf containing `start`
229 (or descend to the leftmost leaf if start is ""), recording the path.
2302. Within the leaf, find the first key >= start.
2313. Visit entries from that position forward.
2324. When the leaf is exhausted, advance to the next leaf via the stack:
233 pop the stack, increment childIdx. If childIdx is now past the last
234 child, pop again (repeat until a valid childIdx is found or the stack
235 is empty — if empty, iteration is done). Then descend to the leftmost
236 leaf of that child, pushing each inner node onto the stack.
2375. Stop when key >= end (if end != "") or tree is exhausted.
2386. Call `cb(key, value)` for each entry; stop if cb returns true.
239
240**Descending (ReverseIterate):**
2411. Descend from root to find the leaf containing `end` (or the rightmost
242 leaf if end is ""), recording the path.
2432. Within the leaf, find the last key <= end.
2443. Visit entries from that position backward.
2454. When the leaf is exhausted going backward, retreat to the previous leaf
246 via the stack: pop the stack, decrement childIdx. If childIdx < 0, pop
247 again (repeat until a valid childIdx is found or the stack is empty —
248 if empty, iteration is done). Then descend to the rightmost leaf of
249 that child, pushing each inner node onto the stack.
2505. Stop when key < start (if start != "") or tree is exhausted.
2516. Call `cb(key, value)` for each entry; stop if cb returns true.
252
253### IterateByOffset / ReverseIterateByOffset
254
255**Ascending:**
2561. Use `sizes[]` to descend to the leaf containing the offset-th entry,
257 recording the path. Maintain a running offset counter: at each inner node,
258 subtract `sizes[i]` for each skipped child. When `offset < sizes[i]`,
259 descend into that child. Upon reaching a leaf, the remaining offset is
260 the position within the leaf.
2612. Visit entries from that position forward, advancing through leaves via
262 the stack (same as Iterate), counting up to `count`.
263
264**Descending:**
265The descending view is: entries in reverse sorted order, 0-indexed from
266the largest key. offset=0 is the largest, offset=1 is the second-largest, etc.
267
2681. Compute the ascending index of the starting entry:
269 `ascIdx = size - 1 - offset` (the entry at position `offset` in descending order).
2702. Use `sizes[]` to descend to the leaf containing entry `ascIdx`,
271 recording the path.
2723. Visit entries from that position backward, retreating through leaves via
273 the stack (same as ReverseIterate), counting up to `count`.
2744. If `ascIdx < 0` or `offset >= size` or `count <= 0`, return false.
275
276## Split details
277
278### Leaf split
279
280Given a leaf with `fanout+1` entries (one over capacity):
281
282**Detection:** after inserting the new key, if it ended up at position
283`fanout` in the overflowed `fanout+1`-entry leaf, it is an append-pattern
284insert (the new key is greater than all pre-existing keys).
285
286**90/10 split (append pattern):**
287- `mid = fanout - 1`
288- Left leaf keeps entries `[0, fanout-1)` = `fanout-1` entries.
289- New right leaf gets entries `[fanout-1, fanout+1)` = 2 entries.
290- Left has `fanout-1` entries (~97% full), right has 2.
291- For large fanouts, the right leaf may be below the `fanout/2` deletion
292 threshold. This is intentional — the 90/10 split prioritizes fill factor
293 for append-heavy workloads. If a subsequent Remove causes the right leaf
294 to underflow, the standard rebalance logic handles it.
295
296**50/50 split (random pattern):**
297- `mid = (fanout + 1) / 2`
298- Left leaf keeps entries `[0, mid)`.
299- New right leaf gets entries `[mid, fanout+1)`.
300
301In both cases:
302- Separator promoted to parent = `right.keys[0]`.
303- No linked list updates needed (no sibling pointers).
304
305### Inner split
306
307Given an inner node with `fanout+1` children:
308- `mid = (fanout + 1) / 2`
309- Left keeps children `[0, mid)` with keys `[0, mid-1)` and sizes `[0, mid)`.
310- Right gets children `[mid, fanout+1)` with keys `[mid, fanout)` and sizes `[mid, fanout+1)`.
311- The separator at `keys[mid-1]` is **promoted** to the parent (not kept in either child).
312- Parent's sizes entry for the original child is replaced by the sum of left's sizes,
313 and a new entry is inserted for the right child with the sum of right's sizes.
314
315## Minimum fanout
316
317Fanout must be >= 4. With fanout 3, a leaf splits into (2, 2) and
318the minimum occupancy is 1, which makes merge logic degenerate. Fanout 4
319gives minimum occupancy 2 and clean split/merge behavior.
320
321`NewBPTreeN` panics if fanout < 4.
322
323## File structure
324
325```
326examples/gno.land/p/nt/bptree/v0/
327 gnomod.toml
328 doc.gno — package doc
329 node.gno — leafNode, innerNode, node interface, binary search
330 tree.gno — BPTree struct, constructors, ITree methods,
331 insert/split, remove/merge/redistribute, iteration
332 tree_test.gno — comprehensive tests (mirroring avl tests + B+ tree specifics)
333```
334
335Two source files (`node.gno` + `tree.gno`) plus one test file. The node
336types and tree logic are tightly coupled, so fewer files is better than
337spreading thin.
338
339## Ref-count safety
340
341In Gno's persistence model, objects with ref-count >= 2 "escape" — they are
342persisted separately in an iavl tree rather than inlined in their parent's
343serialized form. Once escaped, they are forever escaped. This is expensive
344and should be avoided.
345
346**Design constraint: every node must have exactly one persistent reference.**
347
348This means:
349- **No sibling pointers** on leaf nodes (a leaf would be referenced by both
350 its parent and its neighbor → ref-count >= 2).
351- **No `first`/`last` pointers** on BPTree (a leaf would be referenced by
352 both BPTree and its parent inner node → ref-count >= 2).
353- **No shared subtrees** (each child is owned by exactly one parent).
354
355The tree structure is a pure tree (not a graph) — every node has exactly
356one parent reference. The `BPTree.root` is the sole reference to the root
357node. Each `innerNode.children[i]` is the sole reference to child `i`.
358
359Iteration uses an ephemeral stack (local slice) that is built and discarded
360within a single method call. It does not create any persistent references.
361
362## Edge cases (must match avl behavior exactly)
363
364### Values and keys
365- `nil` is a valid value. `Set("foo", nil)` stores it; `Get("foo")` returns
366 `(nil, true)`. `Remove("foo")` returns `(nil, true)`.
367- `""` is a valid key. Stored, retrieved, removed like any other key.
368- `Get` on missing key returns `(nil, false)`.
369- `Remove` on missing key returns `(nil, false)`.
370- `Set` same key twice replaces value, returns `updated=true`.
371
372### Zero-value and structural
373- `var t BPTree` must work — zero-value tree is usable without a constructor.
374 All methods work on it immediately. This means `root == nil` must be handled
375 gracefully everywhere, and the default `fanout` (0) must be promoted to 32
376 on first use. `Set` promotes on first call: `if t.fanout == 0 { t.fanout = 32 }`.
377 All other methods that read `t.fanout` guard with `if t.root == nil` first, so
378 fanout is always initialized before it is read. Once set, fanout never resets
379 (even if tree becomes empty again).
380- Remove last key → tree returns to empty state (root = nil).
381- Insert after removing everything works normally.
382- `Size()` on empty tree returns 0.
383- `GetByIndex` on empty tree panics. Negative index or index >= size also panics.
384- Single entry: root is a leafNode with 1 entry.
385- Root is a leaf: no inner nodes until first split.
386- Root inner node collapses: after merge leaves root with 1 child,
387 replace root with that child.
388
389### Separator key maintenance
390- When the minimum key of a subtree changes (deletion of leftmost key,
391 or redistribution), the parent's separator key must be updated.
392 After modifying a child, check if `keys[childIdx-1]` still equals
393 `children[childIdx].minKey()`.
394
395### Iteration — key range
396- All iteration on an empty tree returns `false` without calling cb.
397- `Iterate("", "", cb)` visits ALL entries ascending (canonical pattern).
398- `ReverseIterate("", "", cb)` visits ALL entries descending.
399- `Iterate("a", "a", cb)` → empty. [a,a) = nothing (start inclusive, end exclusive).
400- `ReverseIterate("a", "a", cb)` → visits "a". [a,a] = one entry (both inclusive).
401- `Iterate("z", "a", cb)` → empty (no validation, logic just excludes everything).
402- `ReverseIterate("z", "a", cb)` → empty (bounds don't swap).
403- `Iterate("", "a", cb)` → visits all keys < "a".
404- `ReverseIterate("a", "", cb)` → visits all keys >= "a", in descending order.
405- Return value = true if callback stopped iteration early, false otherwise.
406
407### Iteration — offset
408- `IterateByOffset(0, 0, cb)` → nothing (count <= 0).
409- `IterateByOffset(size, 1, cb)` → nothing (offset >= size).
410- `ReverseIterateByOffset(0, N, cb)` → starts at largest key, takes N descending.
411- `ReverseIterateByOffset(1, 2, cb)` on [a,b,c,d,e] → [d, c].
412- Negative count → treated as count <= 0 (no iteration).
413- Negative offset → clamped to 0 (avl silently treats negative as 0; we do the same explicitly).