CSE Roadmap

Core tier · about 3 hours · 5 parts

Part 4 of 5 · 2 min read

Inserts and splits

A full leaf splits into two, and the split can propagate upward, keeping the tree balanced.

Inserts and splits

Think of a filing drawer that holds a fixed number of folders. Once it is full, a new folder does not get crammed in; instead, half the folders move into a brand-new drawer, and the cabinet's own index of drawers gets one more entry.

In plain words: inserting a new key into a B+-tree walks down to the correct leaf node, the same way a lookup would, and inserts the key there in sorted order. If that leaf is already full, it splits into two leaf nodes, each holding about half the original entries, and a new key is added to the parent internal node pointing at the new leaf. If the parent internal node is itself now full, the split propagates one level higher, and so on. This splitting behavior is exactly why a B+-tree stays balanced: every leaf stays at the same depth from the root, no matter how many inserts happen over time.

A worked example. Inserting a new order with placed_on = '2026-01-15' into a full leaf splits that leaf into two, moving roughly half its dates into a new leaf, and adds one new key to the parent node pointing at it.

The key lines. No new SQL; a split happens automatically inside the storage engine whenever an INSERT lands on a full leaf.

Leaf split

A leaf split divides a full leaf node's entries roughly in half across two leaf nodes when a new key needs to be inserted, adding a new key to the parent node and keeping the tree balanced.

Example: a full filing drawer splitting its folders across two drawers, with the cabinet's own index gaining one more entry, mirrors a B+-tree leaf split.

Remember this

A B+-tree's sorted leaves and linked leaf chain are what make range queries fast, not just exact matches. Splits keep every leaf at the same depth, so lookups stay fast even as the table grows over years of inserts.

Quick notes

  • A B+-tree keeps keys sorted across its leaf nodes, supporting both exact-match and range queries.
  • Internal nodes route the search; leaf nodes hold the actual entries and are linked in sorted order.
  • The leaf chain lets a range scan move forward leaf to leaf without retraversing the tree.
  • A full leaf splits into two on insert, propagating upward if the parent is also full, keeping the tree balanced.
  • Hash indexes, covered next, trade this ordering away for faster exact-match lookups alone.