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 Insertion and Splitting Work | Full Nodes, Median Promotion and Root Growth

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

B-tree insertion and splitting work by inserting keys into sorted leaf positions while preventing any node from exceeding its maximum capacity. When a node is full, the algorithm divides it into two legal nodes and promotes a median separator into the parent. If the root splits, a new root is created and the tree grows by one level.

A standard top-down insertion strategy makes one simplifying promise: never descend into a full child. Before moving down, split that child first. The search then always enters a non-full node, so the eventual leaf has space for the new key.

This pillar explains full-node detection, top-down splitting, median promotion, child-pointer partitioning, root splits, cascading capacity pressure, leaf insertion, variable-length page splits, fill factor, sequential inserts, duplicate policies, page allocation, write amplification, concurrency, copy-on-write versions, testing and the failure modes that break multiway ordering even when every local key array looks sorted.

Master guide: How B-Trees Work · Pillar: How B-Tree Nodes Work · How X Works Hub


Insertion Begins With Ordered Search

Find the Correct Child Interval

Inside each internal node, find where the new key belongs among the sorted separators. If it matches an existing key, apply the container’s duplicate or update policy. Otherwise the insertion position identifies the one child whose key interval can contain the new key.

Eventually Reach a Leaf

Classical insertion stores the new key in a leaf. The hard part is making sure every node on the way has enough room for whatever structural change the insertion might cause.


Why Full Nodes Need Special Handling

A Full Node Has No Slot for Another Key

Under minimum degree t, a full node has 2t−1 keys.

Insertion Cannot Simply Append and Hope to Repair Later Without a Plan

An implementation can use bottom-up overflow repair, but classic algorithms often split proactively because it simplifies control flow and guarantees descent into nodes with spare capacity.


Top-Down Insertion Splits Before Descent

Inspect the Chosen Child

If the child is full, split it before moving into it.

Re-Decide Which Resulting Child to Follow

The promoted median enters the parent and divides the old child’s range into two. Compare the insertion key with that promoted separator and choose left or right result. This extra comparison keeps the descent path correct.


Splitting a Full Leaf

Choose the Median

A full node’s sorted key sequence is divided around the median key.

Create Two Legal Leaves

Keys below the median stay in the left leaf, keys above go to a new right leaf, and the median is promoted to the parent under the classical B-tree model. Both resulting leaves remain at the same depth.


Splitting a Full Internal Node

Keys and Children Must Be Partitioned Together

The median separator moves to the parent. Keys below it stay left, keys above stay right.

Child Pointers Follow Their Key Ranges

If the full node had 2t children, the first t belong with the left result and the last t with the right under the standard minimum-degree model. A key-only split silently destroys routing.


The Parent Gains One Key and One Child

One Child Becomes Two

The parent’s old pointer to the full child is replaced by pointers to the new left and right children.

The Median Becomes the New Separator

It sits between those two pointers, preserving the parent’s sorted range partition. The parent therefore consumes one additional key slot and one additional child slot.


A Full Parent Can Also Need Splitting

Capacity Pressure Can Move Upward

If an insertion strategy repairs overflow after descent, a child split can overfill the parent.

Top-Down Splitting Avoids This During Descent

Classic top-down algorithms ensure the current node is non-full before attempting to insert a promoted median into it. Root handling makes the induction work from the top.


Root Split Is the Height-Growth Event

A Full Root Has No Parent

Create a new empty root and make the old root its child.

Split the Old Root Under the New Root

The median becomes the new root’s first key and the old root becomes two children. Every former leaf is now one level farther from the root, so equal leaf depth is preserved.


Why Height Grows Only One Level at a Time

Only the Root Can Add a New Level

Internal node splits redistribute nodes within the same depth.

A Root Split Creates Exactly One New Top Level

Therefore a single insertion can increase B-tree height by at most one. Most insertions do not change height at all.


Worked Split Example With Minimum Degree 2

A Full Node Has Three Keys

For t=2, legal non-root nodes hold one to three keys. Suppose a leaf contains [10,20,30] and must split before descending or inserting further under the classic algorithm.

Promote 20

Left leaf becomes [10], right leaf becomes [30], and 20 enters the parent. A new key 25 would then descend into the right leaf because it is greater than 20 but less than 30’s upper range.


Worked Internal Split

Suppose Internal Node Holds [20,40,60]

It therefore has four child ranges: below 20, 20–40, 40–60 and above 60.

Promote 40

Left internal node keeps [20] and the first two child pointers. Right keeps [60] and the last two child pointers. Parent receives 40 between pointers to those two new internal nodes.


Why the Median Is the Natural Promotion Key

It Separates Two Legal Halves

Keys below the median belong left and keys above belong right.

It Helps Both Children Meet Minimum Occupancy

Under the standard full size 2t−1, removing one median leaves t−1 keys on each side. The split therefore produces two minimally legal non-root nodes immediately.


The Split Is an Occupancy Transformation

Before: One Node at Maximum Capacity

The node is legal but has no free slot.

After: Two Nodes at Minimum Legal Capacity Plus One Parent Separator

The operation trades local density for future insertion room while preserving total key order. Occupancy constraints drive the geometry.


Leaf Insertion Within a Non-Full Node

Make Space at the Sorted Position

Shift larger keys right or use a slot-array representation to create a gap.

Place the New Key

No structural split is needed because the node had spare capacity. If records are stored with keys, payload movement or slot references follow the key.


Variable-Length Keys Change the Physical Split Point

Median by Key Count May Not Balance Bytes

A few large keys can dominate page occupancy.

Storage Engines Often Split by Byte Utilisation

They choose a separator that leaves both pages within legal and performance targets. The abstract sorted-range invariant remains the same even when the chosen pivot is not the exact count median.


Page Allocation Is Part of a Real Split

A New Right Node Needs Physical Storage

The system allocates a page or block identifier and initialises its header and contents.

Parent Must Store the New Child Reference

A split therefore combines logical sorting with storage allocation. Allocation failure, logging and crash recovery become part of production insertion semantics.


Insertions Can Cause Write Amplification

One Leaf Update May Touch Several Pages

A split writes the old child, new child and parent.

Cascading or Root Splits Touch More

Even though height is logarithmic, durable systems may write logs, copy pages or update checksums. Logical insertion cost and physical write cost are distinct.


Fill Factor Trades Space for Future Splits

Higher Fill Uses Fewer Pages

This improves scan density and may reduce height.

Lower Fill Leaves Growth Room

Random inserts can be absorbed without immediate split. Bulk-load operations often choose a fill factor deliberately based on expected future updates.


Sequential Inserts Concentrate Splits

Ascending Keys Keep Hitting the Right Edge

The newest leaf fills repeatedly.

Right-Biased Split Policies Can Help

Some engines leave more free space on the newly created rightmost page for append workloads. This is a performance policy layered over legal B-tree occupancy.


Random Inserts Spread Pressure

Keys Arrive Across Many Leaves

Free space throughout the tree is consumed more evenly.

Split Frequency Depends on Existing Fill

A tree bulk-loaded nearly full will split sooner than one built with headroom. Workload history influences physical behaviour without changing the abstract insertion algorithm.


Duplicate Keys Need a Total Internal Order

Unique Maps Can Reject or Update Equality

No new structural key is inserted.

Duplicate Indexes Need Tie-Breaking

A hidden record identifier, tuple address or additional key component can distinguish equal user keys. The node comparator must define a stable total ordering so insertion chooses one deterministic slot.


Composite Keys Follow Lexicographic Insertion

Compare the Full Key Tuple

An index on (A,B) sorts first by A, then B under the configured comparator.

Splits Preserve the Same Tuple Order

Promotion and child intervals operate on the combined key space. A split cannot treat only the leading column as the separator semantics.


Top-Down Splitting Simplifies Recursion

Recursive Function Receives a Non-Full Node

Before it descends, it guarantees the chosen child is non-full.

Leaf Case Is Simple

When the function reaches a leaf, it inserts directly because spare capacity is guaranteed. The complexity has been moved into the pre-descent split step.


Bottom-Up Overflow Repair Is an Alternative

Insert First, Then Split Overflowing Nodes Upward

This can be natural in some systems or when page occupancy is byte-based.

Parent Overflow May Cascade

Each split can create a new parent separator that overflows the parent, continuing to the root. Both top-down and bottom-up methods can be correct if invariants are restored consistently.


Choosing Between Top-Down and Bottom-Up

Top-Down Avoids Descending Into Full Nodes

Control flow and memory planning can be simpler.

Bottom-Up May Fit Transactional Page Designs

The exact record size and final page state may be known only after insertion. Production systems choose algorithms around page format, concurrency and logging as well as textbook elegance.


Parent Pointers Are Optional

A Search Stack Can Remember Ancestors

The insertion path contains every parent needed for bottom-up split propagation.

Disk Pages Often Avoid Direct Memory Parent Pointers

Parent relationships may be rediscovered from traversal context or maintained separately. Persistent page identifiers and buffer managers change the representation.


Root Splits and Stable Root Handles

In-Memory Containers Can Replace a Root Pointer

The new root object simply becomes the entry point.

Persistent Storage May Need a Stable Metadata Location

A database file can store the current root page ID in a fixed header or catalog record. Root split then allocates a new page and atomically updates that metadata under the storage engine’s durability rules.


Copy-on-Write Insertion

Do Not Modify Shared Pages In Place

Create new versions along the changed root-to-leaf path.

Splits Create Additional New Pages

Parent versions point to the new children. Snapshots can continue referencing old pages. The B-tree’s small height limits the number of copied ancestors, making this approach practical in many filesystems and databases.


Concurrent Splits Need Navigation Safety

Another Search May Reach a Page While It Splits

Without coordination, it can follow stale separators.

Latch Coupling or B-Link Techniques Address This

Sequential split mechanics remain the core transformation, while concurrency metadata lets readers recognise or recover from structural movement. Production insertion is algorithm plus coordination protocol.


Split Logging and Crash Recovery

A Split Is Multi-Page State Change

Crashing after writing one child but before the parent separator can leave the tree unreachable or inconsistent.

Write-Ahead Logging or Copy-on-Write Makes the Transformation Recoverable

Durable systems record enough intent or use atomic root/reference updates so the tree can be reconstructed to a valid state after failure.


A Common Failure: Descend Into a Full Child Without a Repair Plan

Symptom

Leaf insertion discovers no room and code lacks parent context.

Repair

Use top-down pre-splitting or preserve a complete ancestor path for bottom-up propagation. Capacity strategy must be explicit.


A Common Failure: Promote a Median but Leave It in the Child Too

Symptom

Classical B-tree search can encounter duplicate separator copies unexpectedly.

Repair

Under classical B-tree split semantics, the median moves into the parent and is removed from both child key arrays. B+ tree semantics differ and belong to a separate design.


A Common Failure: Split Child Keys but Misplace the Parent Pointer Index

Symptom

The parent key array is sorted, but the two new child pointers are inserted on the wrong sides of the promoted median.

Repair

Treat separator insertion and child-pointer replacement as one coupled operation. Validate each child’s key range against adjacent parent separators.


A Common Failure: Internal Split Drops One Child

Symptom

Node count or key count seems correct, but a whole subtree disappears.

Repair

Remember m keys imply m+1 child pointers. When splitting, partition all child pointers and assert total children across left and right equal the original count.


A Common Failure: Root Split Leaves Old Root Marked as Root

Symptom

Two nodes believe they are root or parent metadata becomes inconsistent.

Repair

Update root ownership, parent metadata if stored and persistent root-page metadata atomically according to the container’s design.


A Common Failure: Variable-Byte Split Violates Minimum Occupancy Convention

Symptom

Byte balance looks good but one side falls below a logical minimum needed by the implementation.

Repair

Define occupancy in the terms the actual system guarantees. Some engines use byte-oriented thresholds rather than textbook key counts; the validator must match the real contract.


Testing Insertion and Splitting

Directed Cases

Fill a leaf exactly, split it, split an internal node, split a child whose parent has one free slot, and split the root. Repeat at several heights.

Random Cases

Insert shuffled keys and monotonic keys, validate after every operation, compare sorted contents with a trusted map and verify all leaves have equal depth.


Split Invariant Checklist

Local Order

Both child key arrays sorted; all left keys below promoted separator; all right keys above.

Structural Coupling

Parent separator inserted at correct index, child pointers aligned, legal occupancy on both results, parent not overfull under the chosen algorithm, and all descendants remain reachable exactly once.


Performance Metrics Worth Measuring

Page Split Rate

How many insertions trigger page allocation and parent updates?

Tree Height and Average Fill

Low height with healthy occupancy is the goal. Also measure write amplification, cache misses and right-edge hot spots. Big-O alone does not reveal whether physical insertion behaviour is efficient.


Visual Analogies and System Connections of Splitting

Visual Analogy: Split the Overcrowded Room and Move the Door Sign Up

One full room becomes two legal rooms. The median is not lost; it becomes the sign in the hallway telling future visitors which room to enter.

How the Parts Work Together: Splitting Is Local Growth Management

An algorithms student sees median promotion. A database engineer sees page allocation. A storage engineer sees logging and crash recovery. A concurrency engineer sees latches and sibling links. One structural event sits at the intersection of all those concerns.


How to Teach B-Tree Insertion

Use Tiny Degree First

With t=2, nodes hold at most three keys, so splits happen frequently and can be drawn by hand.

Then Change the Cost Model

Once learners see that one split creates two page-sized search regions, scale the node capacity mentally to hundreds of keys. The same local operation explains why enormous indexes stay only a few pages tall.


Frequently Asked Questions

Does Every Insertion Cause a Split?

No. Most simply insert into a non-full leaf. Splits occur only when capacity is exhausted under the chosen strategy.

Can One Insertion Increase Height by More Than One?

No. Only a root split adds a level, and one insertion can create at most one new root level.


More Frequently Asked Questions

Why Promote the Median Instead of Copying It?

In a classical B-tree, promotion cleanly separates left and right child ranges and leaves both children within legal occupancy. B+ tree designs commonly copy separators differently.

Why Split Before Descending?

It guarantees the algorithm never enters a full child, simplifying the leaf insertion and preventing upward overflow during the recursive descent.


The Pillar Boundary and Sources

What This Article Owns

This pillar owns B-tree insertion-specific mechanics: non-full descent, node splitting, median promotion, parent updates, root growth, page allocation and insertion workload effects. Node structure and deletion repair have separate owners.

Sources and Further Reading

For B-tree insertion and splitting, see Open Data Structures: B-Trees. For database-index context, see PostgreSQL Documentation: B-Tree Indexes.


Final Synthesis: Split Before Overcrowding Breaks the Search Structure

The Flow

Navigate by separators, ensure the chosen child has room, split full nodes around a median, promote that median to the parent, and insert into a non-full leaf.

Why It Works

Splitting preserves sorted intervals while restoring spare capacity. Because only a root split adds a level, insertion maintains equal leaf depth and low height through local page-sized transformations.


Worked Top-Down Insertion Trace Across Two Splits

Split Before Entering the Full Child

Suppose the root is non-full, but the child interval that should contain key 55 is already full. The top-down algorithm does not descend yet. It splits that child around its median, inserts the median into the root and creates two child ranges. Only then does it compare 55 with the promoted median and select the correct resulting child. The descent invariant is restored before moving one level lower.

A Lower Full Child Can Be Split the Same Way

Inside the selected child, another descendant may be full. The same pre-descent repair repeats. The algorithm can therefore encounter several splits during one insertion without ever allowing the current recursive target to overflow. This is the elegance of top-down insertion: each level locally guarantees that the next level has enough room for the eventual leaf insertion.

Root Split Worked Example With Minimum Degree 2

Start With Root [10,20,30]

For t=2, three keys means the root is full. Before inserting another distinct key under the top-down method, allocate a new empty root. Make the old root its child and split that child. Promote 20. The new root becomes [20], with children [10] and [30]. The tree height has increased by one, but both old leaf groups moved together to the new depth.

Then Continue With the Original New Key

If the incoming key is 25, compare it with root separator 20 and descend right. The right child [30] is non-full, so insert 25 in sorted position to obtain [25,30]. Root splitting is therefore not a separate insertion; it is a preparation step that creates space and a new routing level before ordinary descent resumes.

Internal Split With Child Arrays

Keys and Children Must Be Partitioned at Matching Boundaries

Imagine a full internal node with keys [20,40,60] and child ranges c0,c1,c2,c3. Promote 40. The left result keeps key 20 and children c0,c1. The right result keeps key 60 and children c2,c3. If c2 were accidentally left on the left page, queries between 40 and 60 would descend into the wrong range even though both key arrays remain sorted.

Use Interleaved Order as the Proof

Read the full node as c0,20,c1,40,c2,60,c3. Splitting around 40 produces c0,20,c1 on the left, separator 40 in the parent and c2,60,c3 on the right. This representation makes the child partition obvious and scales to larger nodes.

Insertion With Variable-Length Keys

Physical Fullness Can Arrive Before Key-Count Fullness

A page may have room for twenty short separators but only ten unusually long ones. Production engines therefore often decide fullness by free bytes rather than a fixed number of keys. The logical split still divides ordered ranges, but the chosen pivot may target balanced byte occupancy instead of equal key counts.

The Promoted Separator Can Be Chosen With Physical Layout in Mind

If entries vary widely, a count median can leave one page nearly full and the other half empty. A byte-aware split can choose a boundary that gives both pages usable headroom while respecting minimum occupancy and comparator order. The abstraction remains a B-tree because the split preserves legal ranges and balanced leaf depth, not because every page contains the same number of keys.

Split Cascades in Bottom-Up Insertion

Overflow Can Climb the Ancestor Path

A bottom-up algorithm may insert into a leaf first, detect overflow, split that page and promote a separator. If the parent overflows, split the parent and promote again. This can repeat to the root. The eventual root split adds one level. The same local split rule therefore supports both leaf and internal overflow repair.

Ancestor Context Must Be Preserved

Because a promotion may continue upward, the implementation needs the parent path. It can store parent page IDs, retain a traversal stack or use recursive return values. Without that context, a full leaf can be divided physically but the new sibling and promoted boundary cannot be integrated into the larger tree.

Bulk Loading Is Not Repeated Random Insertion

Sorted Input Can Build Dense Leaves Directly

If millions of keys are already sorted, inserting them one by one causes repeated right-edge splits and extra writes. Bulk-loading algorithms can pack leaf pages to a target fill factor, then build parent levels from their separators. The result is often faster to construct and denser than incremental insertion.

Leave Planned Headroom for Future Updates

A bulk-built index intended to remain read-only can be packed very tightly. One expected to receive random inserts may deliberately leave free space. Construction policy therefore reflects future workload. B-tree occupancy is not merely a static theorem; it is a capacity budget across time.

Insertion Under Write-Ahead Logging

A Split Must Be Recoverable Across Several Page Writes

Creating a sibling, moving half the entries and adding a parent separator cannot be assumed to reach storage atomically. A write-ahead log can describe the transformation before data pages are flushed. After a crash, recovery replays or rolls forward the operation so the parent and children agree.

Logical Correctness and Durability Correctness Are Different Layers

A split algorithm can be perfectly ordered in memory yet unsafe on disk if power loss leaves an orphan sibling or a parent pointing to an incompletely initialised page. Production B-tree insertion therefore needs both a structural proof and a recovery protocol.

Insertion Under Copy-on-Write

Old Pages Remain Immutable

The insertion creates new versions of pages along the changed path. If a split occurs, both resulting pages are new versions and the parent version points to them. Once the new root reference is committed, readers of the new snapshot see the updated tree while older snapshots still see the old pages.

Small Height Keeps Path Copying Manageable

Because fan-out is high, only a handful of internal pages lie between root and leaf in many practical trees. Copy-on-write therefore duplicates relatively few ancestors per update. The cost is additional page allocation and later garbage collection, traded for simple snapshot semantics and strong crash consistency.

Concurrency: Splits Change the Search Map While Readers Are Using It

A Search Can Arrive at a Page Whose Range Has Just Been Divided

Without coordination, a reader can miss the new sibling or follow a parent separator that has not yet been updated. Latch coupling serialises parts of the path; optimistic schemes validate versions; B-link style designs add high keys and sibling links so a reader can move right if a concurrent split shifted the target range.

Sequential Split Logic Remains the Core Transformation

Concurrency protocols do not change what a correct final split means: two ordered legal pages, one promoted boundary and a parent route to both. They define how intermediate visibility is controlled while that transformation happens.

Insertion and Hot-Page Contention

Monotonic Keys Can Turn the Rightmost Leaf Into a Bottleneck

Timestamp or sequence-number indexes funnel concurrent inserts toward the same edge page. Even with low tree height, contention can dominate performance. Systems may use larger right-edge free space, partitioned indexes, buffered insertion techniques or alternative key designs to reduce the hotspot.

Balanced Height Does Not Guarantee Balanced Write Traffic

The tree can be structurally perfect while one leaf receives nearly all new writes. This distinction matters operationally: B-tree balance is about search depth and occupancy, not about uniform temporal access. Workload distribution is a separate performance dimension.

Insertion Metrics and Postconditions

Measure More Than Operation Count

Track split rate, root split frequency, average leaf fill, internal fill, pages allocated per insert, bytes written and buffer-cache misses. These metrics reveal whether the insertion policy matches the workload and page format.

Verify the Whole Structural Contract

After insertion, logical contents match the expected ordered map, all node key arrays are sorted, internal child counts equal keys plus one, descendant ranges respect separators, occupancy is legal, every leaf has the same depth, all new pages are reachable exactly once and the root metadata points to the current tree. Search success alone does not prove a split was correct.

Insertion Review: Why Splitting Is Local but Capacity Planning Is Global

One Split Repairs One Full Region

The median promotion cleanly separates one overcrowded node into two legal ranges. The transformation is local and easy to verify with key bounds.

The Frequency of Splits Depends on the Whole Workload

Fill factor, key-size distribution, insertion order, page size and concurrency determine how often that local repair occurs. A good B-tree implementation therefore combines a simple invariant-preserving split with workload-aware capacity policy.

Insertion Boundary Cases Worth Testing Explicitly

Insert Into Empty Tree, One-Key Root and Full Root

These three cases exercise root creation, ordinary in-node insertion and root split. The tests should verify height, root page ownership, leaf status, separator order and exact contents after each transition. Root bugs are disproportionately damaging because every future search begins there.

Split the Leftmost, Middle and Rightmost Child

A parent insertion index can be wrong only for some child positions. Directed tests should therefore split children at every edge of the parent’s child array, with non-empty internal subtrees where applicable. After each split, validate that the promoted separator sits between the two new pointers and every unaffected sibling remains in its original range.

Insertion Review: Promotion Is Routing Information Moving Upward

The Median Does More Than Free Space

Promoting the median creates a new routing boundary in the parent. Future searches need no knowledge that one child used to be a single page; they simply compare against the new separator and choose the left or right result. Splitting therefore rewrites the search map while preserving the logical ordered set.

Root Growth Is the Same Idea at the Top Level

When the old root splits, its median becomes the first routing key in a new root. No special search algorithm is introduced. The same separator semantics simply gain one new level above the previous tree. This is why the structure can grow indefinitely while keeping one uniform search procedure.

Insertion Postcondition Review for Persistent Systems

After a durable insertion, every newly allocated page must either be reachable from the committed root or safely reclaimable as aborted work. Parent separators must match child ranges, root metadata must point to the new version, and recovery logs or copy-on-write references must make the operation replayable or atomic. A logically correct in-memory split is only half of a storage-engine insertion contract.

Insertion Review: The Search Path and the Capacity Path Are the Same Path

Every node visited during insertion has two roles. Its separators choose the next key range, and its occupancy determines whether that next step is structurally safe. Top-down insertion merges those questions into one loop: find the child interval, inspect whether that child is full, split if necessary, then re-evaluate the separator position before descending. This prevents routing decisions from becoming stale after a structural change.

That re-evaluation step is easy to overlook. Splitting introduces a new parent separator, so the incoming key may belong to the new right sibling rather than the left half of the original child. Correct insertion therefore treats every split as a change to the local search map, not merely a capacity repair.

Insertion Postcondition Review: A Split Must Change Routing Exactly Once

Before a split, the parent has one child pointer covering the full range of the full node. After the split, that one route becomes two routes separated by exactly one promoted key. No other parent interval should change. This local before-and-after model is a strong debugging tool because it isolates the intended search-map change from unrelated siblings.

After insertion completes, re-run searches for the promoted separator, the greatest key remaining in the left result, the smallest key in the right result and keys just outside those boundaries. If all route correctly and every page remains within occupancy limits, the split has preserved both capacity and ordered navigation.

Next pillar: How B-Tree Deletion and Merging Work

The final insertion principle is equally compact: whenever capacity changes the local shape, recompute routing before continuing. A split is not merely extra space; it creates a new separator and therefore a new search decision. Capacity repair and navigation repair are the same operation viewed from two different layers.

A final implementation check is to confirm that every promoted separator changes exactly one parent interval boundary and that the two resulting child pages cover the original key range completely, without overlap or gaps.

Continue the B-Tree Series

How B-Trees Work · How B-Tree Nodes Work · How X Works Hub