VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

How B-Tree Deletion and Merging Work | Borrowing, Redistribution, Underflow and Root Shrinkage

Three secondary students review open books and notes together in a classroom.

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