B-tree deletion and merging work by removing a key while preventing any non-root node from falling below its minimum occupancy. If the target node has spare keys, deletion can be local. If a child is at minimum capacity, the algorithm must either borrow a boundary key through the parent from a richer sibling or merge two minimum siblings with their separating parent key.
Deletion is therefore the occupancy mirror of insertion. Insertion repairs overflow by splitting one full node into two and pushing a separator upward. Deletion repairs underflow by redistributing through a parent or merging two nodes and pulling a separator downward. The tree can shrink in height only when the root loses its final key and its only child becomes the new root.
This pillar explains leaf deletion, internal-key deletion, predecessor and successor replacement, proactive top-down deletion, borrowing from left and right siblings, redistribution, merging, parent underflow, root shrinkage, variable-length pages, page reclamation, write amplification, concurrency, copy-on-write deletion, validation and the failure modes that lose subtrees even when the visible keys remain sorted.
Master guide: How B-Trees Work · Pillar: How B-Tree Nodes Work · Pillar: How B-Tree Insertion and Splitting Work · How X Works Hub
Deletion Is an Occupancy Problem as Much as a Key Problem
Removing the Key Is Only Half the Work
A key can disappear from a node while leaving the node below its legal minimum.
The Tree Must Restore Density
Borrowing or merging repairs occupancy so the high fan-out and low height guarantees remain intact. Ordered correctness and occupancy correctness are separate postconditions.
Minimum Occupancy Creates the Underflow Threshold
Under Minimum Degree t, Non-Root Nodes Need at Least t−1 Keys
A node sitting exactly at t−1 has no spare key to lose.
Root Is Again the Exception
The root can contain fewer keys. If it becomes empty with one child, that child replaces it and height falls by one.
Top-Down Deletion Can Repair Before Descending
Never Descend Into a Minimum Child
One classical strategy ensures the chosen child has at least t keys before descent.
Borrow or Merge First
If the child has only t−1 keys, use a sibling with spare capacity or merge with a sibling. Then descend into a child that can safely lose a key without immediate underflow.
Why Proactive Repair Simplifies Recursion
The Recursive Call Receives a Safe Child
The child can delete one key and remain legal, unless the key is replaced through a deeper internal case handled by the same logic.
No Need to Bubble Underflow Up After Every Return
The complexity is paid before descent, making the recursive invariant easier to state. Bottom-up repair is possible, but top-down is a clean textbook strategy.
Deleting From a Leaf With Spare Capacity
Find the Key Position
The leaf key array is sorted, so locate the exact key.
Remove and Compact
Shift later keys left or update a slot directory. If the leaf remains at or above minimum occupancy, deletion is complete with no structural change.
Deleting From a Minimum Leaf Requires Preparation
Direct Removal Would Underflow
A non-root leaf at t−1 keys cannot lose another key.
Repair Its Capacity Before Entering
Borrow from a sibling with at least t keys or merge with a minimum sibling plus parent separator. Then continue deletion in the enlarged or redistributed child.
Deleting a Key From an Internal Node
The Key Separates Two Adjacent Child Ranges
Call the left child y and right child z around the target separator k.
Three Main Options Exist
If y has at least t keys, replace k by predecessor and delete predecessor from y. Else if z has at least t, use successor. Otherwise both are minimum: merge y, k and z, then delete k from the merged node.
Predecessor Replacement
Use the Largest Key in the Left Child Subtree
Descend to the rightmost leaf within the left adjacent subtree.
Why It Preserves Order
The predecessor is smaller than the target but at least as large as every other key in the left side. Replacing the separator with it preserves the boundary, then deletion continues where the predecessor was physically stored.
Successor Replacement
Use the Smallest Key in the Right Child Subtree
Descend along leftmost children in the right adjacent subtree.
Mirror Correctness
The successor is greater than the target but no greater key lies between them. It can replace the separator while preserving all adjacent ranges.
Why the Chosen Replacement Child Must Have Spare Capacity
Deleting the Predecessor or Successor Removes a Real Key Deeper Down
If that child path were already at minimum throughout, replacement could trigger underflow complexity.
The t-Key Condition Provides Slack
Top-down deletion chooses predecessor or successor only from an adjacent child with at least t keys, ensuring the first descent has room to absorb the removal.
Merging Around an Internal Target
Both Adjacent Children Are Minimum
Neither can donate a replacement key safely.
Pull the Target Separator Down
Combine left child keys, target key and right child keys into one node. Under the 2t−1 maximum, two t−1 children plus one separator produce exactly 2t−1 keys—a full but legal merged node. Then delete the target from within that node.
Borrowing From the Left Sibling
A Rich Left Sibling Has at Least t Keys
It can spare its largest key without falling below minimum.
Rotate Through the Parent
Move the parent separator down to the front of the target child, move the left sibling’s largest key up into the parent’s separator position, and if internal, transfer the sibling’s rightmost child pointer to become the target’s leftmost child.
Borrowing From the Right Sibling
A Rich Right Sibling Can Spare Its Smallest Key
The right sibling remains legal after donation.
Mirror Redistribution
Move the parent separator down to the end of the target child, move the sibling’s smallest key up into the parent, and transfer the sibling’s leftmost child pointer when internal. Sorted order and child intervals remain continuous.
Borrowing Is a Three-Node Boundary Rotation
Sibling, Parent and Child All Change
One boundary key moves up, one parent separator moves down.
It Resembles Rotation at a Wider Scale
Unlike a binary-tree rotation, B-tree redistribution moves key ownership and possibly child pointers across page boundaries while preserving the same global ordered sequence.
Why Borrowing Is Better Than Merging When Possible
It Preserves Parent Occupancy
The parent keeps the same number of keys and children.
It Avoids Reducing Fan-Out
Merging removes one child from the parent and can propagate underflow upward. Borrowing is the smaller repair when a sibling has spare capacity.
Merging Two Minimum Siblings
Take Left Keys, Parent Separator and Right Keys
Concatenate them in sorted order.
Combine Child Pointers If Internal
All left child pointers come first, then right child pointers after the separator boundary. The resulting node is full or nearly full under the standard count model.
The Parent Shrinks After a Merge
One Separator Disappears From the Parent
It moved down into the merged child.
Two Child Pointers Become One
The parent therefore loses one key and one child. If it was a non-root minimum node, it can now underflow and require repair above in bottom-up variants, or top-down logic arranges the descent to manage this safely.
Root Shrink Is the Deletion Height Event
An Empty Internal Root With One Child Is Unnecessary
The only child already spans the full key range.
Promote That Child
The tree height decreases by one and all leaves move one level closer equally. This is the exact deletion mirror of insertion’s root split.
Height Cannot Shrink Elsewhere
Merging Internal Nodes Does Not Change Leaf Depth Locally
It reduces parent fan-out but does not pull one branch up independently.
Only Removing an Empty Root Removes a Whole Level
That preserves the B-tree guarantee that all leaves share one depth.
Worked Example With Minimum Degree 2: Borrow
Target Leaf Has [20] and Right Sibling Has [40,50] With Parent Separator 30
The target is minimum and needs to delete 20 under a proactive strategy.
Borrow From Right
Move 30 down into target so it becomes [20,30], move 40 up into parent as the new separator, and sibling becomes [50]. Now target has spare capacity and can delete 20, leaving [30] legally occupied.
Worked Example With Minimum Degree 2: Merge
Target [20], Sibling [40], Parent Separator 30
Both children are minimum.
Merge to [20,30,40]
Parent loses 30 and one child pointer. Deletion can now remove 20, leaving [30,40]. If the parent was root and became empty, the merged node becomes the new root.
Worked Internal Deletion With Predecessor
Target Separator Is 50
Left adjacent child has more than minimum keys.
Replace 50 With Its Predecessor 45
Then delete 45 from the left subtree using the same safe-descent logic. The parent separator remains a correct boundary because 45 is the largest key from the left side.
Worked Internal Deletion With Merge
Both Adjacent Children Are Minimum
No predecessor or successor can be removed without risking immediate underflow.
Merge Around the Separator
The target key becomes an internal key of the merged child. Deletion continues there, converting a difficult internal deletion into an ordinary recursive deletion within a larger safe node.
Variable-Length Pages Complicate Minimum Occupancy
Textbook Minimums Count Keys
Real pages often care about bytes.
Borrowing and Merging May Be Byte-Aware
A sibling with one ‘extra key’ may not have enough free byte geometry to donate cleanly if keys vary widely. Engines define practical occupancy rules in terms of page space, item slots or target utilisation rather than pure t counts.
Page Reclamation After Merge
One Physical Page Becomes Unused
The merged sibling’s old page can be returned to a free list or allocator.
Durability and Concurrency Affect When Reuse Is Safe
A transactional system may need logging, epoch delays or reference tracking before reusing the page identifier. Logical deletion and physical reclamation are separate layers.
Deletion Causes Write Amplification Too
Borrowing Touches Child, Sibling and Parent
Three pages may need updates.
Merging Touches At Least Two Children and Parent
Copy-on-write or logging can multiply physical writes. A logarithmic algorithm can still have meaningful storage write cost.
Underflow Repair Can Propagate Upward
Bottom-Up Algorithms Repair Parent After Child Merge
Parent key count may drop below minimum.
The Same Borrow-or-Merge Logic Repeats
The structural problem climbs toward the root until a node absorbs it or root shrinks. This mirrors AVL deletion’s upward maintenance, but the invariant is occupancy rather than height difference.
Top-Down Deletion Moves Complexity Before the Recursive Call
Child Is Enlarged Before Descent
Borrowing or merging ensures the chosen child has at least t keys.
Deletion Then Cannot Leave That Child Immediately Underfull
The recursive invariant reduces post-return repair. This is why top-down B-tree deletion is often taught despite its case-heavy appearance.
Choosing the Correct Sibling
Prefer a Sibling With Spare Keys
Borrowing is less structurally disruptive than merging.
If Both Sides Can Donate, Policy Can Choose
Implementations may select based on locality, occupancy, byte balance or simplicity. Any choice must preserve separator order and legal child ranges.
Borrowing Child Pointers Correctly
From Left Sibling
Its rightmost child moves to the target’s leftmost child position because it covers the boundary range below the old parent separator.
From Right Sibling
Its leftmost child moves to the target’s rightmost position. Internal deletion bugs often come from moving the key boundary but forgetting this subtree transfer.
Deleting Duplicate Keys
Unique Maps Have One Logical Match
Deletion removes or reports absence.
Duplicate Indexes Need a Specific Occurrence Policy
The internal total order may include record IDs or tuple identifiers. Deleting one user-key occurrence must target the full internal key so the correct leaf entry and separator paths are updated.
Deleting Composite Keys
Comparison Uses the Full Tuple
Predecessor and successor are defined in lexicographic composite order.
Separator Correctness Uses the Same Comparator
Borrow, merge and replacement remain valid only if every page uses identical comparison semantics, including collation and null rules.
Copy-on-Write Deletion
Changed Pages Are Rebuilt Rather Than Mutated
The path to the target, borrowed siblings or merged nodes and affected parents receive new versions.
Old Snapshots Retain Old Pages
Root reference changes make the new version visible atomically. Height remains small, but merging can enlarge the set of pages copied during one deletion.
Concurrent Deletion and Structural Movement
Readers May Navigate While Pages Borrow or Merge
A page can lose or gain key ranges.
Production Variants Need Coordination
Latches, version checks, sibling links or B-link techniques prevent searches from following stale separators into missing ranges. Sequential deletion remains the logical substrate.
Crash Recovery for Merges
A Merge Is a Multi-Page Transaction
Parent separator removal, target-page growth and sibling-page retirement must become durable coherently.
Logging or Copy-on-Write Provides Recoverability
After a crash, the system must not expose both old and new routes inconsistently. Storage correctness extends beyond the mathematical B-tree invariant.
Deletion and Range Scan Stability
Merging Changes Page Boundaries
A scan cursor may be sitting on a page that is merged or reclaimed.
Systems Need Cursor or Lock Protocols
B+ tree leaf links often help range scans, but classical B-tree traversal still needs defined iterator semantics. Structural deletion affects navigation state even when logical key order remains.
A Common Failure: Delete From Minimum Child Without Preparing It
Symptom
Child falls below legal occupancy and code lacks a correct repair path.
Repair
Use proactive top-down repair or a deliberate bottom-up underflow mechanism. The algorithm must guarantee how minimum violations are handled.
A Common Failure: Borrow Key but Keep Old Parent Separator
Symptom
The same boundary value exists in both parent and child or a range gap appears.
Repair
Borrowing rotates keys through the parent: sibling boundary goes up, old parent separator goes down. Both moves are required.
A Common Failure: Merge Siblings Without Parent Key
Symptom
Keys around the boundary lose their separator or sorted continuity.
Repair
Merged contents are left sibling + separating parent key + right sibling. The parent separator is part of the merged key set.
A Common Failure: Forget Internal Child Transfer During Borrow
Symptom
Leaf tests pass but internal deletion loses descendants.
Repair
Move the boundary child pointer with the borrowed side. Assert internal child count always equals key count plus one.
A Common Failure: Merge Child Arrays in Wrong Order
Symptom
Keys are sorted but child intervals are crossed.
Repair
Preserve the exact left-to-right order of child ranges around the parent separator. Validate descendant bounds after every directed merge test.
A Common Failure: Root Becomes Empty but Is Not Replaced
Symptom
Tree has an unnecessary zero-key internal root and extra height.
Repair
If root has no keys and a single child, promote that child. If the root is an empty leaf, the tree is empty.
Deletion Testing: Force Every Repair
Borrow Left and Borrow Right
Use directed trees where only one sibling has spare keys.
Merge Left and Merge Right
Force both siblings to minimum occupancy. Also test internal-key predecessor, successor and merge cases, and root shrinkage after a final parent separator disappears.
Randomised Deletion Testing
Build Large Trees, Then Delete in Different Orders
Ascending, descending, random and alternating-extreme removals create different occupancy pressure.
Validate After Every Step
Compare logical sorted contents with a trusted map, verify every node’s occupancy, child count, separator bounds and leaf depth, and ensure reclaimed nodes are no longer reachable.
Deletion Performance Metrics
Borrow Rate Versus Merge Rate
Frequent merges can indicate low fill or delete-heavy workload.
Page Reclamation and Height
Track average fill after deletions, number of pages freed, root shrink events and write amplification. A valid B-tree can still be poorly utilised physically.
Bulk Delete Versus Rebuild
Deleting Most Entries One by One Can Cause Many Merges
The tree repeatedly redistributes or frees pages.
A Rebuild Can Be Better for Large Purges
If the application already knows the survivor set, bulk reconstruction may produce a denser tree with fewer writes. Fine-grained deletion is designed for incremental updates, not every bulk transformation.
Two Practical Perspectives on Deletion
Keep Every Room Above Minimum Occupancy
If a room becomes too empty, borrow an item through the hallway from a richer neighbour. If no neighbour can spare one, knock down the wall and merge the rooms, pulling the hallway sign inside.
Deletion Is Capacity Maintenance
A theorist sees occupancy invariants. A database engineer sees page redistribution. A storage engineer sees free-page reclamation. A concurrency engineer sees moving ranges. One key removal activates several system layers because density is part of performance.
How to Teach B-Tree Deletion
Teach Borrow Before Merge
Borrowing shows how parent separators rotate through siblings without changing height.
Then Show Merge as the Underflow Dual of Split
Insertion splits one full node and pushes a key up; deletion merges two minimum nodes and pulls a key down. Seeing the duality reduces the apparent case explosion.
Frequently Asked Questions
Why Is B-Tree Deletion Harder Than Search?
Search only follows separator intervals. Deletion must preserve both order and minimum occupancy, so it may need sibling redistribution or merging.
Can Deletion Reduce Tree Height?
Yes, but only when the root becomes empty and has one child, which is promoted to root.
More Frequently Asked Questions
Why Borrow Through the Parent Instead of Directly From Sibling?
The parent separator is the boundary between their key ranges. Rotating through the parent preserves sorted order while changing occupancy.
Why Merge When Both Siblings Are Minimum?
Neither can donate without becoming illegal. Combining both with the parent separator produces a node at the legal maximum under the standard t model.
The Pillar Boundary and Sources
What This Article Owns
This pillar owns B-tree deletion-specific mechanics: minimum occupancy, predecessor/successor replacement, borrowing, redistribution, merging, underflow propagation, page reclamation and root shrinkage.
Sources and Further Reading
For B-tree deletion concepts, see Open Data Structures: B-Trees. For production ordered-index context, see PostgreSQL Documentation: B-Tree Indexes.
Final Synthesis: Deletion Preserves Density by Borrowing or Collapsing Boundaries
The Flow
Remove safely from leaves or replace internal keys with predecessor/successor, make sure the descent child has spare capacity, borrow through the parent when a sibling is rich, merge when both are minimum, and shrink the root when its final separator disappears.
Why It Works
Occupancy repair keeps fan-out high, sorted separators keep routing correct and root shrinkage preserves equal leaf depth. Deletion therefore maintains the same low-height storage geometry that makes B-trees useful in the first place.
Worked Underflow Trace: Borrow From the Left Before Merging
The Parent Separator Is the Rotating Boundary
Suppose target child c contains the minimum number of keys and its left sibling s has one spare key. The parent key between s and c moves down into the front of c. The largest key in s moves up to replace that parent separator. If the nodes are internal, s’s rightmost child pointer transfers to become c’s leftmost child. The operation preserves every ordered interval while increasing c’s capacity before deletion continues.
Why Borrowing Preserves Parent Width
The parent keeps the same number of separators and children. Only one boundary rotates through it. This avoids the structural contraction caused by merging and therefore avoids creating new occupancy pressure at the parent. Borrow whenever a legal sibling can donate; merge only when local redistribution is impossible.
Worked Underflow Trace: Borrow From the Right
Mirror the Boundary Movement
When the right sibling has spare capacity, the parent separator moves down to the end of the target child. The sibling’s smallest key rises into the parent. For internal nodes, the sibling’s leftmost child pointer moves to the target’s rightmost child position. Every moved component sits exactly at the boundary between the two sibling ranges, which is why sorted order survives.
Near-Sibling Choice Can Be a Policy Decision
If both siblings can donate, either side can be correct. A production engine may prefer the side that yields better byte utilisation, lower logging cost or less page movement. The abstract algorithm needs only a legal redistribution; the systems layer can choose among legal options.
Worked Merge Trace: Two Minimum Children and One Parent Separator
The Arithmetic Fits Exactly Under the Standard t Model
Each minimum child has t−1 keys. Pull down one parent separator and combine both children: (t−1)+1+(t−1)=2t−1 keys, exactly the maximum legal size. This identity explains why merging two minimum siblings is structurally safe. The resulting node is full but valid and has enough capacity to continue the deletion inside it.
The Parent Pays for the Merge
The parent loses the separator and one child pointer. If the parent is non-root and was itself at minimum occupancy, that contraction can create an underflow in bottom-up algorithms. Top-down deletion tries to organise descent so the repair happens predictably. Either way, merging moves occupancy pressure upward while keeping the target path legal.
Worked Internal-Key Deletion With Predecessor Replacement
Replacement Comes From a Rich Adjacent Child
Suppose separator 50 must be deleted from an internal node and the child immediately to its left has more than minimum occupancy. Find the largest key in that left subtree, perhaps 47, and move 47 into the separator position. Then delete the original 47 from the left subtree. Because that child had spare capacity before descent, the recursive deletion begins from a structurally safer region.
Why the Predecessor Is the Exact Legal Replacement
Every key in the left subtree is below 50, and 47 is the greatest among them. Every key in the right adjacent subtree is above 50 and therefore above 47. Replacing 50 with 47 preserves the ordering boundary. The logical deletion has moved from the internal separator to a deeper predecessor occurrence where ordinary deletion continues.
Worked Internal-Key Deletion With Merge
Neither Adjacent Child Can Donate
If both children around target separator 50 are minimum, choosing predecessor or successor would immediately risk underflow. Instead merge left child, 50 and right child. The target key becomes an ordinary key inside one full child node. The parent loses one key and child pointer, and deletion resumes within the merged node.
The Hard Internal Case Becomes a Simpler Recursive Case
This transformation is elegant because it converts “delete a separator that owns two subtrees” into “delete a key from one enlarged subtree.” The occupancy invariant guides the transformation; the recursive deletion logic then handles the resulting leaf or internal path normally.
Root Shrink Worked Example
A One-Key Root Can Lose Its Last Separator Through Merge
Suppose the root contains [40] and has two minimum children. A deletion requires those children to merge with 40. The root becomes empty, while the merged child now contains all keys from both sides plus 40. Keeping the empty root would add a useless level.
Promote the Merged Child
Set the merged child as the new root and decrement tree height by one. Every leaf was beneath one of the old root’s children, so every leaf moves upward equally. This is why B-tree deletion can shrink height without violating the equal-leaf-depth invariant.
Bottom-Up Underflow Repair Versus Top-Down Prevention
Bottom-Up Mirrors Overflow Repair Naturally
Delete from a leaf, detect that it became underfull, then borrow or merge and propagate any parent underflow upward. This style matches the conceptual sequence “mutate first, repair after” and can fit systems that discover physical occupancy only after the deletion.
Top-Down Guarantees Safe Capacity Before Descent
Before entering a child at minimum occupancy, the algorithm enlarges it by borrowing or merging. The recursive call therefore works inside a node with at least t keys. This reduces post-return repair complexity. Both approaches are valid; the implementation should state which invariant each recursive call assumes.
Deletion With Variable-Length Pages
“Minimum Keys” May Not Match “Minimum Bytes”
Real storage engines may allow page occupancy below a simple half-full key-count rule because entries vary in size. A page with few large keys can be physically dense. Borrow and merge decisions may therefore consider free bytes, item sizes and target utilisation rather than only key count.
Merge Must Still Fit the Destination Page
Two logically sparse pages can contain records whose combined bytes plus separator do not fit in one physical page. Production algorithms need a page-format-specific redistribution strategy. The classical t model provides the clean invariant; the actual engine maps that invariant onto byte capacity carefully.
Page Reclamation and Free-Space Management
A Merged-Away Page Becomes Storage Debt to Reclaim
Once its entries and children have moved, the old sibling page is no longer reachable from the root. The allocator can eventually return it to a free list. Durable systems may log that change; concurrent systems may delay reuse until no reader can still reference the old page.
Logical Deletion and Physical Space Return Need Not Coincide
Some databases leave dead entries or underfull pages temporarily and reclaim space during vacuum, compaction or background maintenance. This can reduce immediate write cost. A production “B-tree deletion” may therefore separate logical visibility from eventual physical page merging while preserving search correctness through version metadata.
Deletion Under Copy-on-Write
Borrow and Merge Create New Page Versions
Instead of mutating sibling, target and parent pages, copy-on-write systems create new versions with redistributed keys and new parent references. Old snapshots continue to point to old pages. The final committed root selects the new consistent version.
Merges Can Increase Temporary Space Use
Even though deletion reduces logical content, copy-on-write may allocate new merged pages and new ancestors before old pages become reclaimable. Space can rise temporarily. This is another example of logical complexity and physical resource behaviour diverging.
Deletion Under Concurrency
Borrowing Changes Boundaries Seen by Readers
A key moves from sibling to parent while an old parent separator moves into the target. Readers traversing the same pages must not observe a combination that routes a key into neither child or both. Latches or version checks protect the multi-page transformation.
Merging Removes a Route Entirely
The parent drops one child pointer and the sibling page may be retired. B-link-style right-sibling links, fence keys or optimistic validation can help searches recover if they encounter structural movement. The final state remains the ordinary B-tree merge; concurrency protocols control intermediate visibility.
Deletion Under Crash Recovery
Borrowing and Merging Are Multi-Page Atomicity Problems
A crash after updating the child but before updating the parent can leave duplicate or missing separators. Write-ahead logs record enough information to replay the intended transformation, while copy-on-write designs publish the new root only after new pages are durable.
Recovery Must Restore Reachability as Well as Sorted Keys
A page full of perfectly ordered keys is useless if no parent points to it. Likewise, a retired page still reachable from two paths can duplicate results. Recovery validation should include page graph reachability and parent separator consistency, not just individual page format checks.
Deletion Metrics and Long-Term Tree Health
Watch Average Fill After Delete-Heavy Periods
A tree can remain valid while many pages sit near minimum occupancy. Height may increase relative to the same logical dataset stored densely, and scans touch more pages. Merge policy, delayed cleanup and workload history all affect physical utilisation.
Track Merge, Borrow and Root-Shrink Rates
These metrics reveal whether the workload is steadily contracting the index or merely churning local keys. Frequent merge-then-split cycles can indicate thresholds or fill policies that cause structural thrashing. Systems may use hysteresis-like policies or background compaction to reduce unnecessary churn.
Deletion Postcondition Checklist
Logical and Structural Checks
The requested occurrence is absent under duplicate semantics; all remaining keys are reachable exactly once; each node is sorted; internal child count equals key count plus one; child ranges respect parent separators; all non-root nodes meet occupancy rules; the root follows its exception; every leaf remains at one depth.
Physical and Operational Checks
Freed pages are no longer reachable; live child IDs point to valid pages; page free-space metadata is correct; recovery metadata covers multi-page changes; iterators or concurrent readers obey the container’s invalidation protocol. Deletion is complete only when both the ordered tree and its storage representation agree.
Deletion Review: Underflow Repair Is Also a Routing Repair
Borrowing and merging are often described as ways to satisfy minimum key counts, but they also rewrite the parent’s routing boundaries. A borrowed key changes which separator distinguishes two siblings. A merge removes that separator entirely because the two ranges have become one. Occupancy and routing are repaired by the same transformation, which is why parent keys cannot be treated as independent metadata.
A strong deletion audit therefore checks three things together: legal page density, correct separator values and complete child-range reachability. Fixing only the count can leave a structurally legal-looking page that sends future searches to the wrong place.
A final deletion check is simple but powerful: compare the sorted logical contents before and after, excluding only the requested removed binding. Borrowing and merging may move many keys and page boundaries, but they must not change the relative order or identity of any surviving entry.
Continue the B-Tree Series
How B-Trees Work · How B-Tree Nodes Work · How B-Tree Insertion and Splitting Work · How X Works Hub
