Insert and split — the tree grows — separator keys promoted to the parent page

An INSERT writes one cell when there's room; when the leaf is full it splits and a separator key is promoted to the parent — splits cascade upward, and only a root split adds a level.

Previously

Scene 4 left the cursor finding any leaf in 3 page reads. Now we actually run the INSERT — and watch what the leaf does when it has, and doesn't have, room.

Scene 05

Insert and split — the tree grows

Watch
Try it
Predict
Capture

What to watch for

Watch INSERT rowid=42 land in the leaf. Each tick adds one row: a new cell goes into the cell content area (bottom), a new pointer goes into the cell-pointer array (top), and the fill meter climbs.

Implementation

Highlighted lines are the ones running in the diagram right now.

Leaf.insert

the in-place case — a cell + a pointer, no structural change

1def insert(leaf, cell):
2    if leaf.free_bytes >= cell.size:
3        offset = leaf.alloc_in_content_area(cell.size)
4        leaf.write_cell(offset, cell)
5        leaf.cell_pointer_array.insert_sorted(offset, cell.key)
6        return
7    split_leaf(leaf, cell)   # no room → split

split_leaf

allocate sibling, redistribute cells, promote a separator

1def split_leaf(leaf, new_cell):
2    sibling = pager.allocate_page(kind='leaf')
3    median  = redistribute(leaf, sibling, new_cell)
4    sep_key = median.key
5    promote_to_parent(leaf.parent, sep_key, sibling)

promote_to_parent

cascade upward; root split is the only way depth grows

1def promote_to_parent(parent, sep_key, new_child):
2    if parent is None:                 # we were the root
3        new_root = pager.allocate_page(kind='root')
4        new_root.add_child(old_root)
5        new_root.add_separator(sep_key, new_child)
6        tree.depth += 1                # the only path that gains depth
7        return
8    if parent.has_room_for(sep_key):
9        parent.insert_separator(sep_key, new_child)
10        return
11    split_interior(parent, sep_key, new_child)   # cascade

Sources

Where this sits in Build a B-tree storage engine (SQLite-style)

Scene 05 of 11, in the Mutations act — Insert, split, delete — and why the file doesn't shrink.. An INSERT writes one cell when there's room; when full, the leaf splits and a separator promotes to the parent — cascades grow the tree.

Up next. Inserts grow the tree neatly. Deletes — surprisingly — don't undo that growth. The next half-step shows why your file stays huge after a big DELETE and what VACUUM is for.

All 11 scenes in Build a B-tree storage engine (SQLite-style) · Every curriculum

Built with Arqly

Every scene in Build a B-tree storage engine (SQLite-style) builds on the one before it.All 11 Build a B-tree storage engine (SQLite-style) scenes