B-tree algorithms
Insertion
# Insert (key, child) to parent
function promote(key, child, parent):
if parent is null:
# New root
root = (root, key, child)
else if has_room(parent, key):
insert (key, child) to parent
else:
(sibling, separator_key) = split_interior(parent)
promote(separator_key, sibling, parent_node(parent)
|