Transform: A B | a b c d Into: A c B / \ a b d
(idx int, maxKeys int)
| 126 | // |
| 127 | // a b d |
| 128 | func (parent *BTreeNode[T]) Split(idx int, maxKeys int) { |
| 129 | child := parent.children[idx] |
| 130 | midKeyIndex := maxKeys / 2 |
| 131 | rightChild := NewBTreeNode[T](maxKeys, child.isLeaf) |
| 132 | rightChild.Concat(child, midKeyIndex+1) |
| 133 | rightChild.children[0] = child.children[midKeyIndex+1] |
| 134 | |
| 135 | // Reuse child as the left node |
| 136 | child.numKeys = midKeyIndex |
| 137 | |
| 138 | // Insert the child's mid index to the parent |
| 139 | for i := parent.numKeys; i > idx; i-- { |
| 140 | parent.keys[i] = parent.keys[i-1] |
| 141 | parent.children[i+1] = parent.children[i] |
| 142 | } |
| 143 | parent.keys[idx] = child.keys[midKeyIndex] |
| 144 | parent.children[idx] = child |
| 145 | parent.children[idx+1] = rightChild |
| 146 | parent.numKeys += 1 |
| 147 | } |
| 148 | |
| 149 | func (node *BTreeNode[T]) InsertNonFull(tree *BTree[T], key T) { |
| 150 | node.Verify(tree) |
no test coverage detected