B+ tree splits and merges work by repairing page capacity without breaking either of the structure’s two navigation systems: vertical routing through internal separators and horizontal ordered traversal through linked leaves. Leaf splits keep record entries at the bottom and copy or derive a new boundary upward. Internal splits redistribute routing entries and promote a separator. Deletion can reverse that pressure through redistribution and merging.
The subtlety is that B+ trees do not use identical split semantics at leaves and internal pages. A leaf boundary often remains as a real leaf key while a separator copy enters the parent. An internal promoted separator may move out of the child pages. Treating those two operations as the same is one of the most common conceptual errors.
This pillar explains leaf overflow, leaf splitting, internal splitting, parent separator insertion, root growth, linked-leaf repair, borrowing, redistribution, merge, parent boundary refresh, root shrinkage, variable-length pages, fill factor, write amplification, concurrency, crash recovery, copy-on-write maintenance and the invariant checks that prove both vertical and horizontal structure remain coherent.
Master guide: How B+ Trees Work · Pillar: How B+ Tree Internal Nodes Work · Pillar: How B+ Tree Leaf Nodes and Range Scans Work
There Are Two Different Split Types
Leaf Split Preserves Record Entries at the Bottom
Leaf data entries are divided between two leaves. A boundary key is copied or derived upward for routing.
Internal Split Reorganises Routing Entries
Internal keys and child pointers are partitioned, and one separator is promoted into the parent. The promoted internal separator is typically no longer stored in either resulting child under common designs.
Why Leaf and Internal Splits Differ
Leaves Own Logical Entries
Removing the boundary entry from the leaf would remove or relocate the actual searchable record entry in the wrong way.
Internal Pages Own Only Routing
Their separators can move upward because they are metadata rather than final record-bearing entries. Distinct roles create distinct split semantics.
Leaf Overflow Triggers a Page Split
A New Entry No Longer Fits
Fullness can be defined by key count in textbooks or by bytes in real page formats.
Allocate a New Leaf
Partition the sorted entries across old and new pages so both satisfy legal occupancy and retain global key order.
The New Right Leaf Must Enter the Leaf Chain
Vertical Split Is Not Enough
Parent routing can be correct while range scans remain broken.
Repair Horizontal Links
Old leaf.next becomes new leaf; new leaf.next becomes old next; if previous links exist, set new.prev=old and old-next.prev=new. The new leaf must become the exact ordered neighbour.
Parent Receives a New Leaf Boundary
Common Convention Uses the First Key of the Right Leaf
That key remains in the right leaf.
The Parent Stores a Routing Copy
Future equality and interval routing must be consistent with the convention. The copied boundary is metadata, not a second logical row.
A Leaf Split Can Cause Parent Overflow
Parent Gains One Separator and One Child Pointer
Its routing capacity is consumed.
If Parent Is Full, Split the Internal Page
This pressure can propagate upward. Eventually, a root split may create a new top level.
Internal Split Partitions Child Ranges
Keys and Children Form One Ordered Routing Sequence
The split point divides both arrays consistently.
Promote the Separator Between the Two Results
The parent gains the boundary that distinguishes the left and right internal pages. Descendant leaves remain at the same depth.
Root Split Grows Height
No Parent Exists Above a Full Root
Create a new root.
Install Two Children and One or More Boundaries According to the Design
Every existing leaf becomes one level farther from the root together. Balanced leaf depth is preserved.
Worked Leaf Split Example
Leaf Contains [10,20,30,40] and Must Accept 35
After inserting in logical order, entries become [10,20,30,35,40].
Split Into [10,20] and [30,35,40] Under One Legal Policy
Copy boundary 30 into the parent. The right leaf still contains 30 as a real entry. Link left.next to right and right into the previous chain.
Worked Internal Split Example
Internal Page Routes Around [20,40,60]
Suppose it overflows after a child split adds another separator.
Partition Routing Entries and Promote a Middle Boundary
The exact promoted key depends on page convention. Child pointers are divided so every lower range remains covered once and only once. The parent receives a separator that is routing-only.
Why Separator Equality Must Be Retested After a Split
The Parent Search Map Changed
One old child route became two.
The Inserting Key May Belong Right of the New Boundary
Top-down algorithms compare again after splitting. Bottom-up algorithms already know the child that overflowed, but parent placement must still preserve boundary semantics.
Fill Factor Influences Split Frequency
Dense Pages Minimise Index Size
Read-heavy static trees benefit.
Headroom Delays Future Splits
Update-heavy trees can reduce write amplification by leaving free space. The best fill level depends on workload, key size and storage cost.
Variable-Length Entries Need Byte-Aware Splits
Half the Keys May Not Mean Half the Bytes
One large key or included payload can dominate a page.
Choose a Split Point That Produces Legal Usable Pages
Systems may target byte balance, future headroom or right-edge growth. The ordered boundary invariant remains the non-negotiable part.
Sequential Inserts Create Repeated Rightmost Splits
Monotonic Keys Always Target the End
The rightmost leaf becomes a hot page.
Systems Can Bias Split Space
The new right leaf can receive extra free space for expected future appends. This changes utilisation policy without changing logical key order.
Random Inserts Spread Split Pressure
Many Leaves Receive New Entries
Hot spots are less concentrated.
Split Frequency Reflects Prior Fill
A tightly bulk-loaded tree splits sooner than one built with reserve space. Physical maintenance remembers workload history.
Deletion Can Avoid Immediate Merge
A Leaf Can Lose Entries and Remain Legal
No structural change is needed.
Systems May Tolerate Spare Space
Aggressive merging saves pages but causes more writes and possible split/merge oscillation. Production engines often use policies more nuanced than a strict textbook threshold.
Redistribution Repairs an Underfull Leaf Without Removing a Page
Borrow From a Rich Sibling
Move one or more boundary entries.
Refresh Parent Routing
If the right leaf’s first key changes or the chosen separator convention changes, update the parent. Horizontal links remain unchanged because both pages still exist.
Redistribution Between Internal Pages Moves Routing Boundaries
A Child Pointer and Separator Relationship Crosses the Parent
Like B-tree borrowing, the parent participates.
The New Parent Separator Reflects the New Division
Internal routing and occupancy are repaired together. Leaf-chain links are irrelevant at this level.
Leaf Merge Combines Ordered Entries
Choose Adjacent Leaves
Their ranges already touch.
Move Entries Into the Survivor
Then remove the retired leaf from the horizontal chain. Parent loses the separator and child pointer that distinguished the two pages.
Internal Merge Pulls a Parent Boundary Down
Two Routing Pages Become One
Their child pointers and separators combine around the parent boundary under the implementation’s internal-page semantics.
Parent Shrinks
This can propagate underflow upward and eventually trigger root shrinkage.
Root Shrink Reduces Height
Empty Root With One Child Is Redundant
Promote the child to root.
All Leaves Move One Level Closer Together
The B+ tree remains balanced. This is the deletion mirror of root growth.
Leaf-Chain Repair During Merge Is Mandatory
Survivor.next Skips the Retired Leaf
Forward scans remain continuous.
Previous Link of the Following Leaf Must Change When Present
Range navigation must never reach freed or repurposed pages. Reclamation occurs only after link safety is established.
Parent Boundary Repair After Leaf Merge
The Old Separator Disappears
Two leaf ranges are now one.
Neighbouring Separators May Also Need Recalculation
Depending on exact convention, the survivor’s first key or surrounding boundaries can change. Parent routing must be recomputed from the actual child ranges, not patched by intuition.
Copy-Up Versus Move-Up Is the Core Split Distinction
Leaf Split Usually Copies a Boundary Up
The real key stays at the leaf.
Internal Split Commonly Moves a Boundary Up
The promoted separator becomes parent metadata and is omitted from the two child internal pages. Learning this difference prevents many implementation errors.
A Common Failure: Use Internal Split Logic on a Leaf
Symptom
The promoted leaf boundary disappears from leaf data.
Repair
Keep the record-bearing key in the leaf and copy/derive routing metadata upward according to the B+ tree convention.
A Common Failure: Use Leaf Copy-Up Logic on an Internal Split
Symptom
The promoted internal separator remains duplicated in a child when the implementation assumes move-up semantics, causing range ambiguity.
Repair
Define internal-page split rules separately and test child intervals around the promoted boundary.
A Common Failure: Leaf Chain Updated Before the New Page Is Valid
Symptom
Concurrent scans can enter a half-initialised page.
Repair
Concurrency protocol must control publication order. Initialise the new page and its bounds before making it reachable through links, or use latches/versioning that prevent readers from treating the transient state as stable.
A Common Failure: Parent Route Published Before Leaf Link Repair
Symptom
Exact lookup reaches the new page but a concurrent range scanner following the old leaf chain can miss it.
Repair
Multi-page split needs an atomicity/ordering protocol covering both vertical and horizontal visibility. Textbook final state is not enough for concurrent systems.
A Common Failure: Merge Reclaims a Leaf Too Early
Symptom
A scanner holds the retired page ID and later finds unrelated reused data.
Repair
Use latches, epochs, transaction visibility or page-reuse delay. Logical unlinking and physical reuse are distinct phases.
A Common Failure: Separator Not Updated After Borrow
Symptom
Boundary searches enter the wrong leaf after redistribution.
Repair
Recalculate routing separators from the post-borrow child ranges. Test equality and near-boundary queries immediately.
A Common Failure: Parent Child Array Misindexed After Split
Symptom
New sibling exists and separator is sorted but one pointer is inserted at the wrong slot.
Repair
Model parent routing as interleaved child,separator,child order. Verify the two new children straddle the new separator exactly.
Write Amplification of Splits
One Logical Insert Touches Several Pages
Leaf, new sibling and parent at minimum, plus logging and neighbour links.
Cascades Touch More Levels
Internal splits can reach the root. Storage write cost can therefore exceed the logical O(log n) comparison cost by a large constant.
Write Amplification of Merges
Two Children, Parent and Leaf Neighbours Can Change
Retired page metadata and free-space structures also participate.
Aggressive Merging Can Be Expensive
Systems often balance space reclamation against write cost and contention rather than merging at the earliest legal opportunity.
Split/Merge Thrashing
A Page Near Threshold Can Alternate Between Full and Sparse
Repeated inserts and deletes around the same boundary can split then merge repeatedly.
Use Hysteresis-Like Policies
Different thresholds for split, redistribution and merge can reduce structural churn. Correctness rules define legal ranges; performance policy chooses when within those ranges to reorganise.
Concurrency: Latch Coupling
Hold Parent/Child Protection Across Critical Structural Steps
This can make split or merge visibility safe.
Release as Soon as Safe
Fine-grained locking tries to preserve concurrency while ensuring no reader observes an impossible routing state. Exact protocols vary widely across database systems.
Concurrency: B-Link Style Recovery
Horizontal Sibling Links and High Keys Help Readers
A reader that lands on a page whose range no longer contains its target can move right.
Parent Updates Can Lag Within Controlled Bounds
This reduces the need to lock the whole root-to-leaf path. The final stable structure is still a B+ tree; the extra metadata supports concurrent transitions.
Crash Recovery for a Leaf Split
Several Pages Must Agree After Restart
Old leaf, new leaf, parent and leaf neighbour links.
Write-Ahead Logging or Copy-on-Write Defines the Atomic Story
The recovery system reconstructs either the pre-split valid tree or the post-split valid tree, not a hybrid with an orphan page or broken scan chain.
Crash Recovery for a Merge
Retiring a Page Must Be Durable
Parent route removal, leaf-chain splice and free-page metadata interact.
Reusing the Page ID Too Early Is Dangerous
Recovery or stale readers could confuse old and new contents. Storage lifecycle is part of structural correctness.
Copy-on-Write Split
Create New Leaf Versions Instead of Mutating Shared Pages
Parent versions point to the new pages.
Horizontal Links Need Snapshot Consistency
The implementation may copy neighbours, use indirection or manage version-aware leaf traversal. Persistence complicates the simple doubly linked picture.
Copy-on-Write Merge
Survivor Is a New Page Version
Parent path is rebuilt.
Old Pages Remain for Old Snapshots
Space is reclaimed only after versions are no longer reachable. Deletion can temporarily allocate more storage even though logical entry count falls.
Separator Compression During Structural Change
A New Boundary Can Often Be Shortened
Only enough bytes to distinguish adjacent child ranges are required internally.
Recompute Rather Than Blindly Copy Full Leaf Key
Production systems can improve fan-out by deriving a minimal legal separator after split or redistribution. The comparator contract determines what is safe.
Duplicate Keys During Split
A Run of Equal User Keys Can Span Leaves
The physical tie-breaker preserves total order.
Boundary Separator Must Include Enough Information
If internal routing uses only the user-visible duplicate key, equality rules and scan logic must still route to the correct first/last occurrence semantics. Engines often include hidden identifiers or special duplicate representations.
Range Scans During Split
A Scanner Can Cross the Structural Change
Depending on isolation rules, it should see a consistent key sequence without gaps or unintended duplicates.
Leaf Links and Version/Latch Protocols Provide Continuity
The tree’s horizontal structure is as important as its vertical search path for concurrent range correctness.
Range Scans During Merge
The Next Page Can Disappear
A scanner may already have read its ID.
Safe Retirement Is Required
The merge protocol coordinates neighbour links and page lifetime so the scan can continue under the database’s visibility contract.
Bulk Load Uses Split-Like Construction More Efficiently
Sorted Data Can Fill Leaves Directly
No repeated leaf splits are needed.
Build Internal Levels From Leaf Boundaries
The result is a dense B+ tree with planned fill factor. Incremental split logic remains necessary for later updates, but initial construction can exploit global knowledge.
Rebuild Can Repair Long-Term Fragmentation
Delete-Heavy History Can Leave Sparse Leaves
Even if each page remains legal.
Offline or Online Rebuild Packs Entries Densely
This can reduce leaf count, height, cache footprint and range-scan I/O. Fine-grained merge policy is not always the best answer for large-scale compaction.
Testing Split Semantics
Leaf Directed Tests
Split leftmost, middle and rightmost leaves; verify parent boundary and next/prev chain.
Internal Directed Tests
Force split at multiple levels including root. Verify promoted separator, child intervals and leaf depth. Distinguish copy-up leaf tests from move-up internal tests explicitly.
Testing Merge and Redistribution
Leaf Cases
Borrow left/right, merge left/right, update separators, validate chain.
Internal Cases
Borrow and merge routing pages, force parent underflow and root shrink. Compare every query path against a trusted sorted reference.
Full Structural Validation
Vertical Invariants
Internal ranges correct, occupancy legal, all leaves at one depth, every leaf reachable from root exactly once.
Horizontal Invariants
Leaf next chain contains exactly the same leaves in key order; previous links mirror next where present; total leaf entries equal logical contents. A B+ tree needs both dimensions to be trustworthy.
Operational Metrics
Split and Merge Rates
Reveal structural churn.
Leaf Fill, Internal Fill and Range Pages Read
Show whether page utilisation is healthy. Also measure root height changes, page allocations, write amplification and hot-page contention. Maintenance policy should be tuned to observed workload.
Rainbolt and CivDJ Views
Rainbolt View: Splits Add a New Address to the Map and a New House to the Street
Vertical routing and horizontal order must both be updated.
CivDJ View: Structural Maintenance Coordinates Two Infrastructures
The query router sees separators, the scan engine sees leaf links, the storage engine sees page allocation, and the concurrency layer sees publication order. A correct B+ split satisfies all four.
How to Teach B+ Tree Splits and Merges
Teach Leaf Split First
Show that the promoted boundary remains in the leaf.
Then Contrast Internal Split
Show that routing-only separators behave differently. Finally add the leaf chain. The conceptual distinction becomes clear before introducing concurrency and storage details.
Frequently Asked Questions
Why Is a Leaf Separator Copied Rather Than Removed?
Because the leaf owns the actual searchable entry. The parent needs only a routing copy or derived boundary.
Can a Split Increase Height?
Only when split pressure reaches the root and a new root is created.
More Frequently Asked Questions
Can a Merge Decrease Height?
Only when the root becomes empty with one child and that child is promoted.
Why Update Parent Separators After Redistribution?
Because child boundary keys changed. Routing metadata must describe the new ranges, not the old ones.
The Pillar Boundary and Sources
What This Article Owns
This pillar owns B+ tree structural maintenance: leaf versus internal split semantics, boundary propagation, leaf-chain repair, redistribution, merge, root growth/shrinkage and multi-page correctness.
Sources and Further Reading
For B+ tree page types and split-oriented implementation work, see CMU 15-445/645: B+Tree Project. For production page splits, linked levels and B-tree implementation details, see PostgreSQL Documentation: B-Tree Indexes.
Final Synthesis: B+ Tree Maintenance Repairs Two Maps at Once
The Mechanism
When capacity changes, update the vertical separator map and the horizontal leaf map together.
Why It Matters
Exact lookup depends on parent routing. Range scans depend on leaf continuity. A split or merge is complete only when both navigation systems describe the same ordered key space.
Worked Leaf Split With Vertical and Horizontal Postconditions
Before the Split
Suppose leaf L owns keys from 100 through 199 and is full. Its parent has one child pointer to L covering that interval. L.next points to leaf N beginning at 200. A new key 150 arrives. The logical insert belongs inside L, but the page has no physical capacity. The repair must create space without changing the sorted sequence or losing the relationship between L and N.
After the Split
Allocate right leaf R, divide entries so L contains the lower portion and R the upper portion, keep the first key of R as a real leaf entry, and copy or derive a boundary into the parent. Set L.next=R and R.next=N; if previous links exist, set R.prev=L and N.prev=R. The postcondition is two coherent structures at once: parent routing distinguishes L/R vertically, and the leaf chain orders L/R/N horizontally.
Worked Internal Split With Parent Propagation
The Full Page Contains Only Routing State
An internal page I overflows after receiving a new child boundary. Partition I’s separator/child sequence into left page A and right page B. Select one separator K to move upward. Unlike a leaf boundary, K is not a final record entry that must remain in a child. It becomes routing metadata in the parent, while A and B retain the child ranges on either side.
If the Parent Overflows, the Same Routing Repair Climbs
The parent gains K and one additional child pointer. If it no longer fits, split the parent. The cascade can continue to the root, where a new root is created. The tree grows only at the top even though the original overflow began at a leaf or lower internal page.
Separator Copy-Up Versus Move-Up in One Table
Leaf Split
The boundary entry remains at the leaf because leaves own the searchable key entries. The parent receives a copy or a routing derivative. Record count across leaves does not decrease.
Internal Split
The promoted routing separator commonly leaves the child pages and becomes the parent’s boundary. No logical record is lost because internal separators are not the record-bearing copies. This distinction should be explicit in code APIs: splitLeaf and splitInternal are semantically different operations even if they share allocation utilities.
Redistribution Is Often Cheaper Than Merge
Borrowing Preserves Page Count
If an underfull page has a sibling with spare entries, move a boundary entry or group of entries across. The parent remains with the same number of child routes. Only the separator describing the changed boundary may need refresh. This avoids page deallocation and can reduce structural churn.
Merge Contracts the Parent
When neither sibling can donate under the chosen occupancy policy, combine pages and remove one parent child pointer and separator. The parent can then become underfull. Merge therefore has a larger blast radius than redistribution and can propagate toward the root.
Worked Leaf Redistribution and Parent Refresh
Borrow From the Right
Suppose left leaf L is sparse and right leaf R begins with key 500. Move R’s smallest entry, 500, into L. R now begins with 510. If the parent separator was defined as the first key of R, the separator must change from 500 to 510. Failing to update the parent leaves a stale route even though both leaf pages remain locally sorted.
The Leaf Chain Does Not Change
L and R remain adjacent, so next/previous pointers stay intact. This separates the two maintenance dimensions neatly: redistribution changes vertical boundary metadata but not horizontal page membership, whereas split and merge change both.
Worked Leaf Merge and Page Retirement
Combine Adjacent Entries
Move all entries from R into L, preserving key order. Parent removes the separator and child pointer that distinguished R. L.next becomes R.next, and the following leaf’s prev becomes L if backward links are maintained.
Retire R Only After It Is Unreachable Safely
In a single-threaded in-memory implementation, R can be freed once no tree or leaf link references it. In a database, readers may still hold page pins or snapshots. Reclamation can require latches, epochs, WAL rules or delayed reuse. Structural unlinking and storage reuse are distinct stages.
Root Growth and Root Shrink Are Symmetric Boundary Events
Growth Wraps the Entire Existing Tree
A root split creates a new root above two children. No leaf moves relative to another leaf; all leaves simply become one level deeper from the new entry point. Horizontal leaf links are unchanged by the mere fact of adding the root level.
Shrink Removes a Redundant Top Level
If deletion leaves the root with no separator and one child, promote that child. All leaves become one level closer simultaneously. Root metadata must be updated durably because every future search begins from the new root page.
Split Policy and Fill Factor Interact
Even Splits Maximise Immediate Symmetry
Dividing a page approximately in half leaves similar free space on both sides and works well for random insert distributions. This is the standard teaching model.
Biased Splits Can Fit Predictable Growth
For monotonically increasing keys, leaving more free space on the new right page can reduce the frequency of immediate follow-up splits. Production systems can choose such policies while maintaining legal occupancy and routing. Correctness defines allowed shapes; workload policy chooses among them.
Split/Merge Hysteresis Reduces Churn
One Threshold for Both Directions Can Oscillate
A page near the boundary could split after one insert and merge after one delete, repeatedly rewriting several pages. That behaviour is correct but wasteful.
Separate Reorganisation Policies Can Create a Neutral Zone
Systems may tolerate some underutilisation before merging or prefer redistribution. The objective is to avoid structural thrashing while keeping page density healthy. B+ tree maintenance is therefore a control problem around occupancy, not just a list of hard cases.
Copy-on-Write Maintenance Changes Publication Order
Build the New Path Off to the Side
Split or merge by creating new page versions and new ancestor versions. Old readers continue to use the old root and old path. Once the new tree version is complete, publish a new root reference.
Horizontal Links Need Version Awareness
A new leaf should not blindly point into an incompatible old-version chain if snapshots require isolated versions. Persistent B+ tree implementations solve this through copying neighbours, indirection, version-aware links or other designs. The simple linked-list mental model needs extra machinery under persistence.
Write-Ahead Logging for Structural Maintenance
Log Enough to Reconstruct the Multi-Page Transition
A leaf split can involve moved entries, new page initialisation, parent insertion and sibling-link changes. WAL records or physiological logging must let recovery redo or complete these changes in a safe order.
Page LSNs or Equivalent Version Markers Prevent Confusion
Recovery needs to know which updates already reached each page. The exact mechanism is database-specific, but the principle is general: structural changes spanning pages need an ordered durability story, not just durable individual writes.
Concurrent Split Publication
Readers Need a Safe Path During the Transition
If the new right page becomes visible before the parent separator, the old page’s high key and sibling link can redirect searches. If the parent route becomes visible first, the new page must already be initialised. Concurrency protocols define an order in which every observable intermediate state remains navigable.
Final Stable State Is Still Simple
Once the split completes, the parent route directly distinguishes the pages and the leaf chain places them adjacently. Concurrency complexity exists to bridge stable states safely, not to change the fundamental B+ tree invariant.
Concurrent Merge Publication
Removal Is Harder Than Addition
A split adds a new reachable page. A merge removes one that readers may already know about. The system must prevent new readers from entering the retired page while allowing old readers to finish or redirect safely.
Page Reuse Must Wait for Safety
Reusing the same page identifier too soon can make a stale scan interpret unrelated new contents as part of its old range. Delayed reclamation, buffer pins, epochs or other lifecycle mechanisms protect the horizontal chain from use-after-retire errors.
Structural Maintenance With Duplicates
Split Boundaries Can Fall Inside an Equal-Key Run
If physical ordering includes a hidden row ID, the split remains well-defined even when visible keys are identical. The separator may need enough tie-breaker information to route exact physical tuples correctly.
Logical Equality Scans Still Span the Boundary
A query for the user key follows lower-bound semantics to the first matching physical entry and then walks the leaf chain through the rest of the duplicate run. Split placement must not change logical grouping semantics.
Structural Maintenance With Composite Keys
Promoted Boundaries Use the Full Comparator
A separator between two pages of (A,B,C) tuples may be represented compactly, but it must distinguish the full lexicographic ranges. Splits and redistributions that look correct on the leading component can still misroute tuples that differ later.
Boundary Tests Should Use Neighbouring Tuples
After any page operation, search for the maximum tuple in the left page, minimum tuple in the right page and artificial tuples between or equal to relevant prefixes. Directed comparator tests catch subtle composite-boundary mistakes.
Structural Maintenance Postcondition Checklist
After Split or Redistribution
Pages individually sorted; occupancy legal; parent separators match new ranges; internal child counts coherent; leaf chain includes all leaves once; next/prev links repaired; root metadata valid; all entries preserved exactly once; no child interval overlap or gap.
After Merge or Root Shrink
Retired page absent from vertical and horizontal navigation; survivor contains all logical entries; parent lost the correct separator/child; any parent underflow repaired; new root published if needed; page reclamation safe; random exact and range queries match a trusted sorted reference.
Why Maintenance Is the Hardest B+ Tree Layer
Search Uses Existing Structure
Lookup reads separators and leaf links that already agree.
Maintenance Must Rewrite Agreement
Splits, merges and redistribution change page boundaries while preserving the logical ordered set. They must keep parent routes, child ranges, leaf links, storage lifetime, concurrency state and recovery metadata coherent. The difficulty comes from coordinating several representations of the same key-space partition at once.
Maintenance Review: Capacity Repair Must Preserve Two Navigation Graphs
A final audit for any B+ split, borrow or merge is to ask two independent questions. Can an exact search descend from the root to every affected key? Can a range scan walk horizontally through the same affected keys in order? Passing only one test is not enough. Vertical separators and horizontal leaf links are two representations of the same ordered partition.
This is the defining maintenance discipline of the B+ tree. Page occupancy motivates the transformation, but navigation coherence is the postcondition.
A useful final distinction is that page capacity is only the trigger for structural maintenance. The real objective is to restore one coherent ordered partition across parent separators, child ranges and leaf links. Split, redistribution and merge are different tools for preserving that shared partition under changing occupancy.
Maintenance Closing Note
A B+ tree maintenance routine should leave no ambiguity about page ownership. Every key belongs to one ordered leaf position, every leaf belongs to one vertical route in the stable tree, and every adjacent leaf relationship is represented consistently in the horizontal chain. If split, redistribution or merge changes a boundary, every representation of that boundary must change together.
In maintenance testing, verify exact search, lower-bound search and a cross-boundary range scan immediately after every structural change.
Both paths must agree.
Continue the B+ Tree Series
How B+ Trees Work · How B+ Tree Internal Nodes Work · How B+ Tree Leaf Nodes and Range Scans Work · How X Works Hub