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