Insert and split — the tree grows — Build a B-tree storage engine (SQLite-style)

Build a B-tree storage engine (SQLite-style) (11 scenes)

Scene 05 · Insert and split — the tree grows

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.

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

Diagram

Top: the 3-level tree from earlier scenes in miniature, with the affected descent path glowing. Bottom: ONE leaf page (p17) drawn at full size — the cell-pointer array (small slots growing down from the top), the cell content area (cells growing up from the bottom), and the unallocated free space in the middle. A fill meter on the side reads the leaf's % full. When a split happens, a new sibling leaf appears and a separator key animates up into the parent.

Sources

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

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

PreviousSearching — a cursor descends the tree NextDelete and VACUUM — the file doesn't shrink