What happens when you insert into a B-tree index?

A B-tree index is a sorted structure built for the disk's favorite operations: point lookups in ~4 page reads no matter the table size, and sequential scans that follow leaf links. The insert is the interesting part — it's where the tree's shape actually changes, and the trick is doing it without ever holding the whole tree in memory.

Step 1 — the entry: (key, TID)

An INSERT writes the row to the heap first, which returns the row's physical location: TID (block, offset) in Postgres, a clustered key in InnoDB. The index insert's payload is (key, TID) — the key from your indexed columns, the TID as a pointer. Indexes are separate structures from the heap; every index on the table gets its own insert.

Step 2 — descent: find the path

Insert into a B-tree with 100M rows and 8KB pages: fanout is roughly 200-300 entries per page (keys are small; internal pages hold key+child-pointer). Height = log₂₀₀(100M) ≈ 4 levels (root + 3). The descent:

1. Read the root page from the buffer pool (or cache).
2. Binary search the key array to find which child range our key belongs in.
3. Latch crabbing: latch the child, verify the parent still points at it (if the parent split while we were moving, restart the descent), release the parent, continue.

Each level costs one page fetch (~1µs cached, ~100µs-1ms cold) and one binary search (~50-200ns). The whole descent: 3-5 page fetches. This is the invariant that makes B-trees scale: the cost of a lookup doesn't grow with the table size, only with its logarithm.

Step 3 — the leaf insert

The leaf page is fetched and searched: where does the key go? Two cases:

• Key exists: Postgres adds the new TID to the entry's TID list (dedup) — no page movement; InnoDB appends to the clustered record.
• Key is new: the page's entries shift right to make room — the page has a header, an array of item pointers (sorted), and the tuple data area.

Insertion cost per page: memmove of the item-pointer array, ~1-5µs for a full page. Then the page's metadata is updated (free space), the WAL gets an index insert record, and the buffer pool page is marked dirty.

Step 4 — the split

If the leaf is full (Postgres default fill factor is 90% for btree), the insert can't fit. The page splits:

1. Choose a split point (Postgres tries to find a split that keeps the new key in the right page — the "50/50 with right-biased" heuristic, or a left-biased choice for decreasing keys — this matters enormously for append-heavy workloads like monotonic IDs).
2. Allocate a new leaf page; move half the entries to it.
3. Insert a separator key (the first key of the new right page) into the parent along with a pointer to the new page.
4. Latch-wise: this is where crabbing pays off — the splitter must re-latch the parent (upgrade to exclusive), possibly restarting its descent.

Cost: one new page allocation + copy of ~150 entries + a parent insert: ~10-50µs, plus WAL.

Step 5 — the cascade

If the parent is also full, it splits too — moving a separator key into its parent. In the worst case the split propagates to the root. When the root splits, a brand-new root is created with two children: the tree grows by one level from the top. This is rare (root splits happen every ~fanout^h inserts), but it's the only time the tree changes height — and the whole structure stays balanced by construction.

Step 6 — after the split

The split freed space in the original page (it's now ~half full). Postgres marks deleted/reused space; the free space map and visibility machinery handle the rest. Concurrent inserts: with crabbing, other inserters that descended into the other half of the split page proceed without noticing — their path still exists. (If a sibling page moved, the restart logic catches it.)

What it costs

• Descent: 3-5 page fetches + binary searches: ~5-20µs warm, ~300µs-3ms cold.
• Leaf insert: ~1-5µs.
• Split: ~10-50µs — the amortized cost over a page full of inserts is tiny.
• Amortized insert into a warm 4-level tree: ~10-30µs including WAL and lock handling.

EXPLAIN (ANALYZE) INSERT INTO t(key) SELECT i FROM generate_series(1,1000000) i;
  -- 1M inserts into an index: roughly 2.5s => ~2.5µs per index entry

The design takeaway: the index's cost structure is what it is because pages are the unit of everything — fetches, locks, WAL, cache. The B-tree exists to keep each operation touching O(log n) pages, not O(log n) entries — and the page, at 8KB with 250 entries, is what makes that logarithm tiny.