tree.gno
20.44 Kb · 818 lines
1package bptree
2
3type ITree interface {
4 Size() int
5 Has(key string) bool
6 Get(key string) any
7 GetByIndex(index int) (key string, value any)
8 Iterate(start, end string, cb IterCbFn) bool
9 ReverseIterate(start, end string, cb IterCbFn) bool
10 IterateByOffset(offset int, count int, cb IterCbFn) bool
11 ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
12 Set(key string, value any) (updated bool)
13 Remove(key string) (value any, removed bool)
14}
15
16type IterCbFn func(key string, value any) bool
17
18// Verify BPTree implements ITree.
19var _ ITree = (*BPTree)(nil)
20
21// The zero value is usable as an empty tree with fanout 32.
22type BPTree struct {
23 root node
24 size int
25 fanout int
26}
27
28// NewBPTreeN creates a new empty B+ tree with the given fanout.
29// It panics when fanout is lower than 4.
30func NewBPTreeN(fanout int) *BPTree {
31 if fanout < 4 {
32 panic("bptree: fanout must be >= 4")
33 }
34 return &BPTree{fanout: fanout}
35}
36
37// NewBPTree32 creates a new empty B+ tree with fanout 32.
38func NewBPTree32() *BPTree {
39 return NewBPTreeN(32)
40}
41
42func (t *BPTree) Size() int {
43 return t.size
44}
45
46func (t *BPTree) Has(key string) bool {
47 if t.root == nil {
48 return false
49 }
50 n := t.root
51 for !n.isLeaf() {
52 inner := n.(*innerNode)
53 idx := inner.findChild(key)
54 n = inner.children[idx]
55 }
56 leaf := n.(*leafNode)
57 _, found := leaf.find(key)
58 return found
59}
60
61// Get retrieves the value associated with the given key.
62// It returns the value if the key exists, or nil if it doesn't.
63// This allows for a simpler usage pattern with type assertions:
64//
65// if value, ok := tree.Get("key").(MyType); ok {
66// // use value
67// }
68//
69// Use Has to distinguish a stored nil value from a missing key.
70func (t *BPTree) Get(key string) any {
71 if t.root == nil {
72 return nil
73 }
74 n := t.root
75 for !n.isLeaf() {
76 inner := n.(*innerNode)
77 idx := inner.findChild(key)
78 n = inner.children[idx]
79 }
80 leaf := n.(*leafNode)
81 pos, found := leaf.find(key)
82 if !found {
83 return nil
84 }
85 return *leaf.values[pos]
86}
87
88// GetByIndex returns the key-value pair at the given 0-based index.
89// Panics if index is out of range.
90func (t *BPTree) GetByIndex(index int) (key string, value any) {
91 if t.root == nil || index < 0 || index >= t.size {
92 panic("GetByIndex asked for invalid index")
93 }
94 n := t.root
95 rem := index
96 for !n.isLeaf() {
97 inner := n.(*innerNode)
98 found := false
99 for i, s := range inner.sizes {
100 if rem < s {
101 n = inner.children[i]
102 found = true
103 break
104 }
105 rem -= s
106 }
107 if !found {
108 panic("GetByIndex asked for invalid index")
109 }
110 }
111 leaf := n.(*leafNode)
112 return leaf.keys[rem], *leaf.values[rem]
113}
114
115//----------------------------------------
116// Set
117
118// pathEntry records a step in the root-to-leaf descent.
119type pathEntry struct {
120 inner *innerNode
121 childIdx int
122}
123
124// Set inserts or updates a key-value pair. Returns true if the key already existed.
125func (t *BPTree) Set(key string, value any) (updated bool) {
126 if t.fanout == 0 {
127 t.fanout = 32
128 }
129 fanout := t.fanout
130
131 vp := &value // wrap value in *any for lazy loading
132
133 // Empty tree: create a single leaf.
134 if t.root == nil {
135 leaf := newLeafNode(fanout)
136 leaf.keys = append(leaf.keys, key)
137 leaf.values = append(leaf.values, vp)
138 t.root = leaf
139 t.size = 1
140 return false
141 }
142
143 // Descend to the leaf, recording the path.
144 var path []pathEntry
145 n := t.root
146 for !n.isLeaf() {
147 inner := n.(*innerNode)
148 idx := inner.findChild(key)
149 path = append(path, pathEntry{inner, idx})
150 n = inner.children[idx]
151 }
152 leaf := n.(*leafNode)
153
154 // Check if key already exists.
155 pos, found := leaf.find(key)
156 if found {
157 *leaf.values[pos] = value
158 return true
159 }
160
161 // Insert new key-value.
162 leaf.insertAt(pos, key, vp)
163 t.size++
164
165 // Increment sizes up the path.
166 for i := range path {
167 path[i].inner.sizes[path[i].childIdx]++
168 }
169
170 // Split if leaf overflows.
171 if len(leaf.keys) > fanout {
172 t.splitLeaf(leaf, pos, path)
173 }
174
175 return false
176}
177
178// splitLeaf splits an overflowed leaf node. Uses 90/10 split for append
179// patterns (insertPos == fanout) and 50/50 otherwise.
180func (t *BPTree) splitLeaf(leaf *leafNode, insertPos int, path []pathEntry) {
181 fanout := t.fanout
182
183 // 90/10 split for append pattern: new key ended up at position fanout
184 // (greater than all pre-existing keys).
185 var mid int
186 if insertPos == fanout {
187 mid = fanout - 1
188 } else {
189 mid = (fanout + 1) / 2
190 }
191
192 // Create right leaf with entries [mid, fanout+1).
193 right := newLeafNode(fanout)
194 right.keys = append(right.keys, leaf.keys[mid:]...)
195 right.values = append(right.values, leaf.values[mid:]...)
196
197 // Truncate left leaf to [0, mid).
198 for i := mid; i < len(leaf.keys); i++ {
199 leaf.keys[i] = ""
200 leaf.values[i] = nil
201 }
202 leaf.keys = leaf.keys[:mid]
203 leaf.values = leaf.values[:mid]
204
205 // Promote separator to parent.
206 sep := right.keys[0]
207 leftSize := len(leaf.keys)
208 rightSize := len(right.keys)
209
210 if len(path) == 0 {
211 // Root was the leaf; create a new inner root.
212 newRoot := newInnerNode(fanout)
213 newRoot.keys = append(newRoot.keys, sep)
214 newRoot.children = append(newRoot.children, leaf, right)
215 newRoot.sizes = append(newRoot.sizes, leftSize, rightSize)
216 t.root = newRoot
217 return
218 }
219
220 // Insert into parent.
221 pe := path[len(path)-1]
222 parent := pe.inner
223 childIdx := pe.childIdx
224
225 parent.sizes[childIdx] = leftSize
226 parent.insertChildAt(childIdx+1, sep, right, rightSize)
227
228 if len(parent.children) > fanout {
229 t.splitInner(parent, path[:len(path)-1])
230 }
231}
232
233// splitInner splits an overflowed inner node (always 50/50).
234func (t *BPTree) splitInner(inner *innerNode, path []pathEntry) {
235 fanout := t.fanout
236 mid := (fanout + 1) / 2
237
238 promotedKey := inner.keys[mid-1]
239
240 right := newInnerNode(fanout)
241 right.keys = append(right.keys, inner.keys[mid:]...)
242 right.children = append(right.children, inner.children[mid:]...)
243 right.sizes = append(right.sizes, inner.sizes[mid:]...)
244
245 for i := mid - 1; i < len(inner.keys); i++ {
246 inner.keys[i] = ""
247 }
248 for i := mid; i < len(inner.children); i++ {
249 inner.children[i] = nil
250 }
251 inner.keys = inner.keys[:mid-1]
252 inner.children = inner.children[:mid]
253 inner.sizes = inner.sizes[:mid]
254
255 if len(path) == 0 {
256 newRoot := newInnerNode(fanout)
257 newRoot.keys = append(newRoot.keys, promotedKey)
258 newRoot.children = append(newRoot.children, inner, right)
259 newRoot.sizes = append(newRoot.sizes, inner.nodeSize(), right.nodeSize())
260 t.root = newRoot
261 return
262 }
263
264 pe := path[len(path)-1]
265 parent := pe.inner
266 childIdx := pe.childIdx
267
268 parent.sizes[childIdx] = inner.nodeSize()
269 parent.insertChildAt(childIdx+1, promotedKey, right, right.nodeSize())
270
271 if len(parent.children) > fanout {
272 t.splitInner(parent, path[:len(path)-1])
273 }
274}
275
276//----------------------------------------
277// Remove
278
279// Remove deletes a key. Returns the old value and true if the key was found.
280func (t *BPTree) Remove(key string) (value any, removed bool) {
281 if t.root == nil {
282 return nil, false
283 }
284 fanout := t.fanout
285
286 var path []pathEntry
287 n := t.root
288 for !n.isLeaf() {
289 inner := n.(*innerNode)
290 idx := inner.findChild(key)
291 path = append(path, pathEntry{inner, idx})
292 n = inner.children[idx]
293 }
294 leaf := n.(*leafNode)
295
296 pos, found := leaf.find(key)
297 if !found {
298 return nil, false
299 }
300
301 var vp *any
302 _, vp = leaf.removeAt(pos)
303 value = *vp
304 t.size--
305
306 for i := range path {
307 path[i].inner.sizes[path[i].childIdx]--
308 }
309
310 // Handle root leaf.
311 if len(path) == 0 {
312 if len(leaf.keys) == 0 {
313 t.root = nil
314 }
315 return value, true
316 }
317
318 // Check underflow.
319 minKeys := fanout / 2
320 if len(leaf.keys) >= minKeys {
321 if pos == 0 {
322 t.updateSeparator(path)
323 }
324 return value, true
325 }
326
327 // If the minimum key was removed, fix ancestor separators before rebalancing.
328 if pos == 0 {
329 t.updateSeparator(path)
330 }
331
332 // Rebalance.
333 t.rebalanceLeaf(leaf, path)
334 return value, true
335}
336
337// updateSeparator fixes the parent's separator key if the child's min key changed
338// (e.g., after removing the leftmost entry).
339func (t *BPTree) updateSeparator(path []pathEntry) {
340 for i := len(path) - 1; i >= 0; i-- {
341 pe := path[i]
342 if pe.childIdx > 0 {
343 child := pe.inner.children[pe.childIdx]
344 pe.inner.keys[pe.childIdx-1] = child.minKey()
345 return
346 }
347 }
348}
349
350// rebalanceLeaf handles a leaf that has underflowed (< fanout/2 entries).
351// Tries redistribute from left, then right, then merges with a sibling.
352func (t *BPTree) rebalanceLeaf(leaf *leafNode, path []pathEntry) {
353 fanout := t.fanout
354 minKeys := fanout / 2
355 pe := path[len(path)-1]
356 parent := pe.inner
357 childIdx := pe.childIdx
358
359 // Try redistribute from left sibling.
360 if childIdx > 0 {
361 leftSib := parent.children[childIdx-1].(*leafNode)
362 if len(leftSib.keys) > minKeys {
363 k, v := leftSib.removeAt(len(leftSib.keys) - 1)
364 leaf.insertAt(0, k, v)
365 parent.keys[childIdx-1] = leaf.keys[0]
366 parent.sizes[childIdx-1] = len(leftSib.keys)
367 parent.sizes[childIdx] = len(leaf.keys)
368 return
369 }
370 }
371
372 // Try redistribute from right sibling.
373 if childIdx < len(parent.children)-1 {
374 rightSib := parent.children[childIdx+1].(*leafNode)
375 if len(rightSib.keys) > minKeys {
376 k, v := rightSib.removeAt(0)
377 leaf.insertAt(len(leaf.keys), k, v)
378 parent.keys[childIdx] = rightSib.keys[0]
379 parent.sizes[childIdx] = len(leaf.keys)
380 parent.sizes[childIdx+1] = len(rightSib.keys)
381 return
382 }
383 }
384
385 // Merge.
386 if childIdx > 0 {
387 leftSib := parent.children[childIdx-1].(*leafNode)
388 mergeLeaves(leftSib, leaf, parent, childIdx)
389 } else {
390 rightSib := parent.children[childIdx+1].(*leafNode)
391 mergeLeaves(leaf, rightSib, parent, childIdx+1)
392 }
393
394 t.rebalanceInner(path[:len(path)-1])
395}
396
397// mergeLeaves merges right leaf into left and removes right from parent.
398func mergeLeaves(left, right *leafNode, parent *innerNode, rightIdx int) {
399 left.keys = append(left.keys, right.keys...)
400 left.values = append(left.values, right.values...)
401 parent.removeChildAt(rightIdx)
402 parent.sizes[rightIdx-1] = len(left.keys)
403}
404
405// rebalanceInner handles an inner node that has underflowed after a child merge.
406func (t *BPTree) rebalanceInner(path []pathEntry) {
407 if len(path) == 0 {
408 root := t.root.(*innerNode)
409 if len(root.children) == 1 {
410 t.root = root.children[0]
411 }
412 return
413 }
414
415 pe := path[len(path)-1]
416 parent := pe.inner
417 childIdx := pe.childIdx
418 child := parent.children[childIdx].(*innerNode)
419 fanout := t.fanout
420 minChildren := fanout / 2
421
422 if len(child.children) >= minChildren {
423 if childIdx > 0 {
424 parent.keys[childIdx-1] = child.minKey()
425 }
426 return
427 }
428
429 // Try redistribute from left sibling.
430 if childIdx > 0 {
431 leftSib := parent.children[childIdx-1].(*innerNode)
432 if len(leftSib.children) > minChildren {
433 redistributeInnerLeft(parent, childIdx, leftSib, child)
434 return
435 }
436 }
437
438 // Try redistribute from right sibling.
439 if childIdx < len(parent.children)-1 {
440 rightSib := parent.children[childIdx+1].(*innerNode)
441 if len(rightSib.children) > minChildren {
442 redistributeInnerRight(parent, childIdx, child, rightSib)
443 return
444 }
445 }
446
447 // Merge.
448 if childIdx > 0 {
449 leftSib := parent.children[childIdx-1].(*innerNode)
450 mergeInner(leftSib, child, parent, childIdx)
451 } else {
452 rightSib := parent.children[childIdx+1].(*innerNode)
453 mergeInner(child, rightSib, parent, childIdx+1)
454 }
455
456 grandPath := path[:len(path)-1]
457 if len(grandPath) == 0 {
458 root := t.root.(*innerNode)
459 if len(root.children) == 1 {
460 t.root = root.children[0]
461 }
462 return
463 }
464
465 gpe := grandPath[len(grandPath)-1]
466 gparent := gpe.inner
467 gchildIdx := gpe.childIdx
468 gchild := gparent.children[gchildIdx].(*innerNode)
469 minChildren = t.fanout / 2
470
471 if len(gchild.children) < minChildren {
472 t.rebalanceInner(grandPath)
473 } else if gchildIdx > 0 {
474 gparent.keys[gchildIdx-1] = gchild.minKey()
475 }
476}
477
478// redistributeInnerLeft moves the last child from left sibling to the
479// deficient child, pulling down the parent separator and pushing up a new one.
480func redistributeInnerLeft(parent *innerNode, childIdx int, leftSib, child *innerNode) {
481 sep := parent.keys[childIdx-1]
482 child.keys = append(child.keys, "")
483 copy(child.keys[1:], child.keys)
484 child.keys[0] = sep
485
486 lastChild := leftSib.children[len(leftSib.children)-1]
487 lastSize := leftSib.sizes[len(leftSib.sizes)-1]
488 child.children = append(child.children, nil)
489 copy(child.children[1:], child.children)
490 child.children[0] = lastChild
491 child.sizes = append(child.sizes, 0)
492 copy(child.sizes[1:], child.sizes)
493 child.sizes[0] = lastSize
494
495 parent.keys[childIdx-1] = leftSib.keys[len(leftSib.keys)-1]
496
497 leftSib.keys[len(leftSib.keys)-1] = ""
498 leftSib.keys = leftSib.keys[:len(leftSib.keys)-1]
499 leftSib.children[len(leftSib.children)-1] = nil
500 leftSib.children = leftSib.children[:len(leftSib.children)-1]
501 leftSib.sizes = leftSib.sizes[:len(leftSib.sizes)-1]
502
503 parent.sizes[childIdx-1] = leftSib.nodeSize()
504 parent.sizes[childIdx] = child.nodeSize()
505}
506
507// redistributeInnerRight moves the first child from right sibling to the
508// deficient child, pulling down the parent separator and pushing up a new one.
509func redistributeInnerRight(parent *innerNode, childIdx int, child, rightSib *innerNode) {
510 sep := parent.keys[childIdx]
511 child.keys = append(child.keys, sep)
512
513 firstChild := rightSib.children[0]
514 firstSize := rightSib.sizes[0]
515 child.children = append(child.children, firstChild)
516 child.sizes = append(child.sizes, firstSize)
517
518 parent.keys[childIdx] = rightSib.keys[0]
519
520 copy(rightSib.keys, rightSib.keys[1:])
521 rightSib.keys[len(rightSib.keys)-1] = ""
522 rightSib.keys = rightSib.keys[:len(rightSib.keys)-1]
523 copy(rightSib.children, rightSib.children[1:])
524 rightSib.children[len(rightSib.children)-1] = nil
525 rightSib.children = rightSib.children[:len(rightSib.children)-1]
526 copy(rightSib.sizes, rightSib.sizes[1:])
527 rightSib.sizes = rightSib.sizes[:len(rightSib.sizes)-1]
528
529 parent.sizes[childIdx] = child.nodeSize()
530 parent.sizes[childIdx+1] = rightSib.nodeSize()
531}
532
533// mergeInner merges right inner node into left, pulling down the parent
534// separator, and removes right from parent.
535func mergeInner(left, right *innerNode, parent *innerNode, rightIdx int) {
536 sep := parent.keys[rightIdx-1]
537 left.keys = append(left.keys, sep)
538 left.keys = append(left.keys, right.keys...)
539 left.children = append(left.children, right.children...)
540 left.sizes = append(left.sizes, right.sizes...)
541 parent.removeChildAt(rightIdx)
542 parent.sizes[rightIdx-1] = left.nodeSize()
543}
544
545//----------------------------------------
546// Stack-based iteration
547
548// iterStack is a stack of (innerNode, childIdx) for traversal.
549// It is ephemeral — built during iteration, discarded after.
550type iterStack []pathEntry
551
552// descendLeft descends to the leftmost leaf, pushing inner nodes onto the stack.
553func descendLeft(n node, stack *iterStack) *leafNode {
554 for !n.isLeaf() {
555 inner := n.(*innerNode)
556 *stack = append(*stack, pathEntry{inner, 0})
557 n = inner.children[0]
558 }
559 return n.(*leafNode)
560}
561
562// descendRight descends to the rightmost leaf, pushing inner nodes onto the stack.
563func descendRight(n node, stack *iterStack) *leafNode {
564 for !n.isLeaf() {
565 inner := n.(*innerNode)
566 last := len(inner.children) - 1
567 *stack = append(*stack, pathEntry{inner, last})
568 n = inner.children[last]
569 }
570 return n.(*leafNode)
571}
572
573// advanceLeaf moves to the next leaf in ascending order via the stack.
574// Returns nil if there is no next leaf.
575func advanceLeaf(stack *iterStack) *leafNode {
576 for len(*stack) > 0 {
577 top := &(*stack)[len(*stack)-1]
578 top.childIdx++
579 if top.childIdx < len(top.inner.children) {
580 n := top.inner.children[top.childIdx]
581 return descendLeft(n, stack)
582 }
583 *stack = (*stack)[:len(*stack)-1]
584 }
585 return nil
586}
587
588// retreatLeaf moves to the previous leaf in descending order via the stack.
589// Returns nil if there is no previous leaf.
590func retreatLeaf(stack *iterStack) *leafNode {
591 for len(*stack) > 0 {
592 top := &(*stack)[len(*stack)-1]
593 top.childIdx--
594 if top.childIdx >= 0 {
595 n := top.inner.children[top.childIdx]
596 return descendRight(n, stack)
597 }
598 *stack = (*stack)[:len(*stack)-1]
599 }
600 return nil
601}
602
603//----------------------------------------
604// Iterate / ReverseIterate
605
606// Iterate calls cb for each key-value pair in [start, end) ascending order.
607// Empty start/end means no bound. Returns true if stopped early by cb.
608// The tree must not be modified during iteration (no Set or Remove from the callback).
609func (t *BPTree) Iterate(start, end string, cb IterCbFn) bool {
610 if t.root == nil {
611 return false
612 }
613
614 var stack iterStack
615 var leaf *leafNode
616 var pos int
617
618 if start == "" {
619 leaf = descendLeft(t.root, &stack)
620 pos = 0
621 } else {
622 leaf, pos, stack = t.descendToGE(start)
623 if leaf == nil {
624 return false
625 }
626 }
627
628 for leaf != nil {
629 for pos < len(leaf.keys) {
630 k := leaf.keys[pos]
631 if end != "" && k >= end {
632 return false
633 }
634 if cb(k, *leaf.values[pos]) {
635 return true
636 }
637 pos++
638 }
639 leaf = advanceLeaf(&stack)
640 pos = 0
641 }
642 return false
643}
644
645// ReverseIterate calls cb for each key-value pair in [start, end] descending order.
646// Empty start/end means no bound. Returns true if stopped early by cb.
647// The tree must not be modified during iteration (no Set or Remove from the callback).
648func (t *BPTree) ReverseIterate(start, end string, cb IterCbFn) bool {
649 if t.root == nil {
650 return false
651 }
652
653 var stack iterStack
654 var leaf *leafNode
655 var pos int
656
657 if end == "" {
658 leaf = descendRight(t.root, &stack)
659 pos = len(leaf.keys) - 1
660 } else {
661 leaf, pos, stack = t.descendToLE(end)
662 if leaf == nil {
663 return false
664 }
665 }
666
667 for leaf != nil {
668 for pos >= 0 {
669 k := leaf.keys[pos]
670 if start != "" && k < start {
671 return false
672 }
673 if cb(k, *leaf.values[pos]) {
674 return true
675 }
676 pos--
677 }
678 leaf = retreatLeaf(&stack)
679 if leaf != nil {
680 pos = len(leaf.keys) - 1
681 }
682 }
683 return false
684}
685
686// IterateByOffset calls cb for count entries starting at the offset-th entry
687// in ascending order. Returns true if stopped early by cb.
688// The tree must not be modified during iteration (no Set or Remove from the callback).
689func (t *BPTree) IterateByOffset(offset int, count int, cb IterCbFn) bool {
690 if t.root == nil || offset >= t.size || count <= 0 {
691 return false
692 }
693 if offset < 0 {
694 offset = 0
695 }
696
697 leaf, pos, stack := t.descendToOffset(offset)
698
699 visited := 0
700 for leaf != nil && visited < count {
701 for pos < len(leaf.keys) && visited < count {
702 if cb(leaf.keys[pos], *leaf.values[pos]) {
703 return true
704 }
705 visited++
706 pos++
707 }
708 leaf = advanceLeaf(&stack)
709 pos = 0
710 }
711 return false
712}
713
714// ReverseIterateByOffset calls cb for count entries starting at the offset-th
715// entry from the end, in descending order. Returns true if stopped early by cb.
716// The tree must not be modified during iteration (no Set or Remove from the callback).
717func (t *BPTree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool {
718 if t.root == nil || offset >= t.size || count <= 0 {
719 return false
720 }
721 if offset < 0 {
722 offset = 0
723 }
724
725 ascIdx := t.size - 1 - offset
726 leaf, pos, stack := t.descendToOffset(ascIdx)
727
728 visited := 0
729 for leaf != nil && visited < count {
730 for pos >= 0 && visited < count {
731 if cb(leaf.keys[pos], *leaf.values[pos]) {
732 return true
733 }
734 visited++
735 pos--
736 }
737 leaf = retreatLeaf(&stack)
738 if leaf != nil {
739 pos = len(leaf.keys) - 1
740 }
741 }
742 return false
743}
744
745//----------------------------------------
746// Descent helpers for iteration
747
748// descendToGE descends to the first key >= key, returning the leaf, position, and stack.
749func (t *BPTree) descendToGE(key string) (*leafNode, int, iterStack) {
750 var stack iterStack
751 n := t.root
752 for !n.isLeaf() {
753 inner := n.(*innerNode)
754 idx := inner.findChild(key)
755 stack = append(stack, pathEntry{inner, idx})
756 n = inner.children[idx]
757 }
758 leaf := n.(*leafNode)
759 pos, _ := leaf.find(key)
760 if pos >= len(leaf.keys) {
761 next := advanceLeaf(&stack)
762 if next == nil {
763 return nil, 0, nil
764 }
765 return next, 0, stack
766 }
767 return leaf, pos, stack
768}
769
770// descendToLE descends to the last key <= key, returning the leaf, position, and stack.
771func (t *BPTree) descendToLE(key string) (*leafNode, int, iterStack) {
772 var stack iterStack
773 n := t.root
774 for !n.isLeaf() {
775 inner := n.(*innerNode)
776 idx := inner.findChild(key)
777 stack = append(stack, pathEntry{inner, idx})
778 n = inner.children[idx]
779 }
780 leaf := n.(*leafNode)
781 pos, found := leaf.find(key)
782 if found {
783 return leaf, pos, stack
784 }
785 if pos > 0 {
786 return leaf, pos - 1, stack
787 }
788 prev := retreatLeaf(&stack)
789 if prev == nil {
790 return nil, 0, nil
791 }
792 return prev, len(prev.keys) - 1, stack
793}
794
795// descendToOffset descends to the offset-th entry using sizes[],
796// returning the leaf, position within leaf, and stack.
797func (t *BPTree) descendToOffset(offset int) (*leafNode, int, iterStack) {
798 var stack iterStack
799 n := t.root
800 rem := offset
801 for !n.isLeaf() {
802 inner := n.(*innerNode)
803 found := false
804 for i, s := range inner.sizes {
805 if rem < s {
806 stack = append(stack, pathEntry{inner, i})
807 n = inner.children[i]
808 found = true
809 break
810 }
811 rem -= s
812 }
813 if !found {
814 panic("descendToOffset: offset out of range")
815 }
816 }
817 return n.(*leafNode), rem, stack
818}
