(tree *BTree[T], key T)
| 147 | } |
| 148 | |
| 149 | func (node *BTreeNode[T]) InsertNonFull(tree *BTree[T], key T) { |
| 150 | node.Verify(tree) |
| 151 | if node.IsFull(tree.maxKeys) { |
| 152 | panic("Called InsertNonFull() with a full node") |
| 153 | } |
| 154 | |
| 155 | if node.isLeaf { |
| 156 | // Node is a leaf. Directly insert the key. |
| 157 | node.InsertKeyChild(key, nil) |
| 158 | return |
| 159 | } |
| 160 | |
| 161 | // Find the child node to insert into |
| 162 | i := 0 |
| 163 | for ; i < node.numKeys; i++ { |
| 164 | if key < node.keys[i] { |
| 165 | break |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | if node.children[i].IsFull(tree.maxKeys) { |
| 170 | node.Split(i, tree.maxKeys) |
| 171 | if key > node.keys[i] { |
| 172 | i++ |
| 173 | } |
| 174 | } |
| 175 | node.children[i].InsertNonFull(tree, key) |
| 176 | } |
| 177 | |
| 178 | func (tree *BTree[T]) Insert(key T) { |
| 179 | if tree.root == nil { |
no test coverage detected