B+Tree Deletion: Borrow and Merge

Why this stage exists

In The Core Engine, DELETE removed a cell and stopped. A leaf could end up empty, a separator could name a key that no longer exists, and the tree was still correct: every search found the right rows. What it was not was small. Insert a million rows and delete all but ten, and the tree still has every page it ever had, nearly all of them empty, and a scan reads them all.

Real B+Trees fix this as they go. When a node gets too empty, it either takes cells from a neighbour or merges with it, and a merge gives a page back. Now that the file has a free list, those pages have somewhere to go: the next split takes them before the file grows. This is the half of the B+Tree most tutorials skip, because it has more cases than inserting. Each case is small, though, and they all follow from one rule: every node except the root stays at least a quarter full.

What changes: a minimum fill

A leaf is below minimum when its used bytes, each cell plus its 4-byte slot, are fewer than 1019, a quarter of the 4076 bytes an empty leaf has free. An internal node is below minimum when it has no key left, only one child. The root has no minimum: it may be an empty leaf, or an internal node with a single key.

A quarter, not a half, is on purpose. With a half, a leaf just over the line merges after one delete and splits after the next insert, and a workload that alternates the two keeps doing both. A quarter leaves room between the two thresholds, so a leaf that was just split, about half full, is far from merging again.

When a DELETE leaves a node below minimum, it has to be fixed with one sibling: the node just before it under the same parent, or, for the first child, the node just after it. What happens depends on whether the two fit in one node.

Borrow: the two do not fit

When the two nodes together would not fit in one page, their cells are divided again, exactly as a split divides them: by bytes for leaves, with the separator moving down and one key moving up for internal nodes. Both nodes keep their pages, nothing is freed, and the separator between them becomes the first key of the right leaf.

Take rows of 502 bytes, so each cell uses 510 bytes with its slot: two are the minimum, seven fit in a leaf and eight do not. Rows 1 to 11 make a leaf of four and a leaf of seven. Deleting 1, 2 and 3 leaves the first with one row, 510 bytes, below minimum:

Merge: the two fit

When the two nodes fit in one, they become one. The left node keeps its page and takes the right one's cells; the right node's page goes on the free list; the separator between them, and the right node's entry, leave the parent. The left leaf's link becomes whatever the right leaf's was, so a scan still visits every leaf.

A merge takes a key away from the parent. If that leaves the parent with no key, the parent is below minimum, and it is fixed the same way with its own sibling, one level up: internal nodes merge by pulling the separator down between their keys, or borrow by dividing their keys as an internal split does. This can go on up to the root.

Root collapse: the tree gets shorter

The root has no minimum, but an internal root with no key has only one child, and a level that does nothing. When that happens, the child's contents move into the root's page and the child's page is freed. The root keeps its page, as it does when it splits, so the catalog never changes; it is still the only node marked as root, and the child's children get the root's page as their parent. When the child was a leaf, the root becomes a leaf again.

Splitting is the only way a tree grows taller, and collapsing the only way it gets shorter. Both happen at the root, which is why every leaf is always at the same depth.

What stays the same

A separator is still a bound, not a copy of a key. Deleting a leaf's first key does not change the separator above it, as long as the leaf stays above minimum: every key on its left is still smaller and every key on its right still at least as large. Only a borrow sets a separator, and only a merge removes one.

A DELETE of many rows behaves as if the rows were removed one at a time, in ascending key order, with any node fixed after each. So does an UPDATE: a row that gets smaller can leave its leaf below minimum, and it is fixed the same way. The catalog is a B+Tree like any other, so DROP TABLE removing its row follows the same rules.

Real-world numbers. SQLite rebalances a page after a delete, sharing cells among up to three siblings at once. PostgreSQL's B-Tree indexes never merge leaves that still hold rows: a page is only removed once it is completely empty, and space is otherwise left for later inserts and VACUUM. The quarter used here keeps the cases few and the tests exact.

Output contract for this stage

The full definition is on the output contract page, section 28. No command or message is new: what changes is the tree that btree structure, db freelist and the file show after a DELETE or an UPDATE.

What you should see when done

Rows 1 to 8 of 502 bytes, then three deleted:

Welcome to droid!
>btree structure users
[BTREE] Tree depth: 2
[BTREE] INTERNAL (page=2 keys=[5])
[BTREE]   LEAF (page=3 cells=4 keys=[1,2,3,4])
[BTREE]   LEAF (page=4 cells=4 keys=[5,6,7,8])
>delete from users where id < 4;
Delete statement executed successfully (3 rows)
[EXEC] rows_examined=3
>btree structure users
[BTREE] Tree depth: 1
[BTREE] LEAF (page=2 cells=5 keys=[4,5,6,7,8])
>db freelist
[DB] Free list: pages=2 chain=[3,4]
>catalog list
[CATALOG] Tables: 1
[CATALOG]   users root=2 (id INT, name VARCHAR(1000), email VARCHAR(1000))
>.exit
exiting.. good bye!

Things to notice. Deleting 1 and 2 changed nothing but leaf 3: two rows are still the minimum. Deleting 3 left one row, so leaf 3 merged with leaf 4, and then the root had a single child and collapsed. The two freed pages are on the list, and the table's root is still page 2.

Common bugs in this stage

• Fixing only at the end of the statement. A DELETE of many rows must fix nodes after each row, in key order; fixing once at the end gives a different tree.
• Losing the leaf chain. After a merge the left leaf must link to whatever the right leaf linked to. Forget it and a scan stops early, or walks into a free page.
• Merging into the right node. The left node of the pair keeps its page and the right one is freed, whichever of the two was below minimum.
• Moving the root. Collapsing by making the child the new root changes the root's page, and the catalog no longer finds the table. Copy the child into the root's page instead.
• Forgetting the parents. Children that move during an internal merge, a borrow or a collapse need their parent field rewritten, or the next split up the tree updates the wrong node.
• Reading a page after freeing it. Freeing zeroes the page. Read everything you need from the right node before it goes on the list.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: decode both siblings into plain arrays of cells, combine or divide them, and write each node back whole; patching a slotted page in place for a merge is where bugs hide.
• C++: the same, with a std::vector of cells per node; reuse the split's dividing code for a borrow.
• Rust: keep the path from the root as a Vec of (page, child index) while descending, then walk it backwards to fix parents; no parent pointers need to be trusted.
• Zig: the same path as a fixed-size array is enough, as the tree is never more than a few levels deep.