algorithm-b+tree-insertion.md

• If the bucket is not full, add the record.
• Otherwise, split the bucket.
  • Allocate a new leaf and move half the bucket elements to the new bucket.
  • Insert the new leaf's smallest key and address into the parent.
  • If the parent is full, split it too.
    • Add the middle key to the parent node.
  • Repeat until a parent is found that need not split.
• If the root splits, create a new root that has one key and two pointers. (That is, the value that gets pushed to the new root gets removed from the original node)