After a DELETE, or an UPDATE that makes rows smaller, keep every node other than the root at least a quarter full. A node below that borrows from a sibling when the two do not fit in one node, and merges with it when they do; a merge frees a page and takes a key from the parent, which may need fixing in turn. A root left with one child takes that child's place, and the tree gets shorter.
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.
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.
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:
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.
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.
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.
The rule every DELETE and every shrinking UPDATE checks after each row.
Pick a sibling, then merge if the two fit in one node and borrow if they do not.
The only step that makes the tree shorter.
A DELETE or UPDATE that touches several rows behaves as if it touched them one at a time.
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.
| Rule | Value |
|---|---|
| Leaf below minimum | used bytes (cells plus 4 per slot) below 1019 |
| Internal node below minimum | no key |
| Two leaves merge | when their used bytes together are at most 4076 |
| Two internal nodes merge | when their keys and the separator make at most 3 keys |
| Sibling | the node before; for a first child, the node after |
| Merge | the left keeps its page; the right's page is freed |
| Borrow | divides as a split does; no page allocated or freed |
| Root with one child | takes the child's contents; the child's page is freed; the root never moves |
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))>.exitexiting.. 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.
The page above is the same for every language. These are the only language-specific hints.
std::vector of cells per node; reuse the split's dividing code for a borrow.Vec of (page, child index) while descending, then walk it backwards to fix parents; no parent pointers need to be trusted.