B-tree algorithms
Insertion
function btree_insert(btree, record):
key = key(record)
leaf = search(btree, key)
if has_room(leaf, record):
node_insert(record, leaf)
else:
# leaf keeps left half.
# new_leaf gets right half.
new_leaf = split_leaf(leaf)
if key < first_key(new_leaf):
node_insert(record, leaf)
else:
node_insert(record, new_leaf)
promote(first_key(new_leaf), new_leaf, parent_node(leaf))
|