B+ tree internal nodes work as compact routing pages. They store ordered separator keys and child page identifiers, but they do not normally hold the final record-bearing entries that exact lookup returns. Their job is to narrow the search range quickly and send the query toward the correct lower-level page.
This separation lets internal pages devote more space to routing. More separators fit per page, fan-out rises, tree height falls, and upper levels often remain memory-resident. Correctness depends on the relationship between separator convention and child routing: equality must go to the side whose leaf range actually contains the record.
This pillar explains separator copies, child intervals, first-key-of-right-child conventions, high fan-out, prefix truncation, child-page identifiers, internal page search, page-level locality, split propagation, root semantics, duplicate keys, composite keys, fence keys, concurrency, validation and the boundary between internal B+ tree routing and leaf-level record storage.
Master guide: How B+ Trees Work · Foundation: How B-Trees Work · How X Works Hub
The Direct Answer: Internal Pages Are Routing Tables
They Partition Key Space
An internal B+ tree page contains sorted separator keys. Those separators divide the ordered key universe into child ranges.
They Point Down, Not to Final Records
The child references lead to lower internal pages or leaf pages. A lookup that matches an internal separator still continues to the appropriate child because the final searchable entry lives at the leaf layer.
Why Routing-Only Pages Increase Fan-Out
Internal Entries Are Smaller
If internal pages omit row pointers or large payload fields, each routing entry can be compact.
Smaller Entries Mean More Children Per Page
More child pointers lower the number of tree levels. For storage systems, one fewer level can remove an entire page fetch from every lookup.
One Common Separator Convention
Separator Equals the First Key of the Right Child
Many B+ tree implementations use a boundary key copied from the smallest key in the right subtree or page.
Equality Must Route Right
If the separator means ‘keys greater than or equal to this value belong in the right child’, lookup must use that same rule consistently. A separator convention is inseparable from comparison logic.
Other Separator Conventions Are Possible
Boundary Can Be a Shortened Distinguishing Key
The separator may contain only enough bytes to distinguish adjacent ranges.
The Search Rule Must Match the Representation
Whether equality routes left or right depends on the chosen semantics. There is no universal bit pattern; there is a universal need for consistency.
Child Count Still Follows the Multiway Rule
m Separators Describe m+1 Child Ranges
The internal page generalises the same interval geometry as a B-tree node.
Position Matters
Child i belongs between separator i−1 and separator i under the page’s convention. Swapping two child references can break search while leaving the key array perfectly sorted.
Internal Search Can Be Binary or Linear
Binary Search Reduces Comparisons
Wide pages can locate the routing slot in logarithmic comparisons.
Linear or Branchless Search Can Be Faster in Practice
Compact in-cache separators, SIMD and branch-prediction effects can favour other strategies. The internal page abstraction requires only that the correct child interval is selected.
CMU-Style Internal Pages Illustrate the Structure
Ordered Keys Plus Page IDs
CMU’s database-systems B+ tree project describes an internal page as storing ordered keys and child page identifiers.
Representation Details Can Include an Invalid First Key Slot
Specific implementations can encode m+1 child pointers in arrays differently. Those details belong to the concrete page format; the logical mapping remains separators to child ranges.
PostgreSQL Shows the Production Page Perspective
Internal Pages Point to the Next Level Down
PostgreSQL’s B-tree implementation documents internal tuples whose downlinks reference lower pages.
Levels Can Also Be Horizontally Linked
Production designs often add sibling links and high keys for concurrency and structural maintenance. The textbook vertical tree is only one dimension of the real page graph.
The Root Is an Internal Routing Page Once the Tree Grows
Small Trees Can Have a Leaf Root
When the whole index fits in one leaf, there is no internal layer.
A Root Split Creates the First Routing Level
After growth, the root contains separators and child pointers. From then on, every exact record lookup eventually descends from routing-only pages to a leaf.
Internal Height Is the Main Lookup Multiplier
Each Internal Level Usually Means Another Page Access
If not cached, that can dominate latency.
High Fan-Out Keeps Levels Few
This is the core reason internal pages are designed for density. The B+ tree trades within-page search work for fewer inter-page transfers.
Upper Internal Pages Tend to Stay Hot
They Are Touched by Many Queries
The root is involved in every lookup, and its children cover huge key ranges.
Caching Changes the Practical Cost Model
If the top two levels remain memory-resident, many lookups pay storage I/O only near the leaf level. Internal-page density helps the cache keep those levels small.
Separator Copies Are Not Duplicate Logical Records
The Leaf Entry Is the Record-Bearing Copy
It carries the row pointer or associated payload reference.
The Internal Copy Is Metadata
It exists only to route search. Deleting or updating a leaf boundary can therefore require changing a parent separator even though the logical record set has not gained or lost a duplicate.
Boundary Changes Can Propagate Upward
A Leaf’s First Key Can Change
Deletion, redistribution or split can alter the smallest key in a child page.
Ancestors May Need Separator Repair
If a parent separator is defined from that boundary, update it. In some designs, only the immediate parent changes; other representations can require further propagation. Boundary metadata must match the actual child ranges.
Internal Splits Move a Separator Up
Full Internal Page Must Divide
Keys and child pointers are partitioned.
One Separator Becomes Parent Routing Metadata
Unlike a common leaf split where the boundary key remains in the right leaf and is copied upward, an internal split often removes the promoted separator from the split pages. Leaf and internal split semantics must be kept distinct.
Internal Merges Pull a Parent Separator Down
Two Underfull Siblings Can Combine
Their parent boundary joins them.
The Parent Loses One Route
One separator and one child pointer disappear from the parent. If the parent becomes too sparse, underflow repair can continue upward.
Borrowing Changes Internal Boundaries
A Sibling Can Donate a Boundary Child
The parent separator rotates through the pages.
The Parent Key Must Change
The new boundary reflects the redistributed child ranges. Borrowing is both an occupancy change and a routing-map rewrite.
Fence Keys Make Page Ranges Explicit
A High Key Can Describe the Page’s Upper Limit
Some B-tree-family implementations store page range metadata beyond the ordinary separator array.
This Helps Concurrent Navigation
A reader can detect that its target has moved right after a split. Fence keys make local range ownership inspectable.
Right-Sibling Links Support Split Recovery
A Parent May Lag Behind a Concurrent Split Briefly
The child page can know about its new right sibling before every ancestor route is visible.
A Search Can Move Right if the Key Exceeds the Page Range
This B-link-style idea lets concurrent systems tolerate carefully controlled transient states while preserving eventual B+ tree routing.
Composite Keys Need One Total Comparator
Internal Separators Use the Full Tuple Order
For index (A,B,C), routing follows lexicographic order.
No Field Is Independently Special to the Tree
The page compares opaque logical keys under the configured operator class or comparator. Application field semantics are compiled into that order.
Collation Changes Can Invalidate Routing
Text Order Is Part of the Index Definition
Locale and collation rules determine separator meaning.
Changing the Comparator Can Require Rebuild
If the same stored bytes now compare differently, child ranges no longer match the search algorithm. Logical ordering semantics are structural metadata.
Null Ordering and Descending Components Matter
Database Indexes Can Use Nontrivial Orders
Nulls first or last, ascending or descending per component, custom operator classes and type semantics all affect the comparator.
Internal Pages Only Need Consistency
Once a total order is defined, the B+ tree machinery is unchanged. Separator correctness follows that order.
Separator Truncation Can Save Significant Space
Full Keys May Be Unnecessary Internally
If adjacent child ranges differ early, a short prefix can distinguish them.
Fan-Out Improves
Shorter separators let more routing entries fit per page. The height benefit can be substantial for long text or composite keys.
Truncated Separators Need Careful Comparison Semantics
A Prefix Is Not Necessarily a Full Search Key
Search code must interpret the separator representation correctly.
Database Engines Encapsulate This in Operator and Page Logic
Users see one ordered index, while the engine may use compact routing forms internally. Correctness depends on proving that every query is sent to a child that can contain the key.
Internal Page Formats Can Use Slot Arrays
Logical Key Order Can Be Separate From Physical Byte Order
A slot directory can keep pointers to variable-length separators.
Compaction Need Not Change Routing
The page can move bytes internally while preserving slot order. Logical page semantics survive physical maintenance.
Page IDs Decouple Tree Structure From Memory Addresses
Child References Can Be Stable Block Numbers
The buffer manager loads them into arbitrary memory frames.
This Suits Persistent Storage
Pages can be evicted and reloaded without rewriting parent links. The tree is defined in page-identifier space rather than process-address space.
Root Metadata Must Be Durable
The Root Page ID Is the Entry Point
Lose it and the rest of the index can become unreachable.
Root Split or Shrink Needs Safe Publication
Write-ahead logging, copy-on-write or catalog metadata updates ensure the new root becomes visible atomically or recoverably.
Internal Pages Rarely Contain the Majority of Pages
Leaves Hold the Data Population
For large indexes, most pages are at the leaf level.
Internal Density Pays Off Disproportionately
A relatively small number of compact routing pages can index a vast leaf layer. PostgreSQL notes that typically more than 99% of its B-tree pages are leaves, illustrating this asymmetry.
Internal Page Cache Locality Matters
Compact Separators Fit More Per Cache Line
CPU-level locality improves.
Branching Structure Also Affects Prediction
Binary search, interpolation, SIMD and learned routing experiments all target the same bottleneck: choose the child quickly once the page is resident.
Internal Search Is Not a Range Scan
Its Job Ends After One Child Is Chosen
It does not enumerate neighbouring values.
Range Continuation Belongs to Leaves
This ownership boundary keeps the B+ tree cluster coherent: internal pages position the search; linked leaves execute the sequential ordered walk.
A Common Failure: Internal Equality Stops the Lookup
Symptom
Search returns an internal separator as though it were the record.
Repair
In a B+ tree, separator equality normally still routes to a child. The final record-bearing entry must be located at the leaf level.
A Common Failure: Wrong Equality Direction
Symptom
Keys equal to a separator become invisible.
Repair
Match the child-selection operator to the separator convention. If separator is first key of right child, equality must enter the right range.
A Common Failure: Parent Separator Becomes Stale After Leaf Redistribution
Symptom
Exact keys exist at leaves but searches route to adjacent pages.
Repair
Any boundary-changing leaf operation must refresh the internal separator. Validate keys immediately around every changed boundary.
A Common Failure: Internal Split Copies Instead of Moves the Promoted Key
Symptom
Routing ranges overlap or duplicate unexpectedly under the chosen design.
Repair
Keep internal split semantics distinct from leaf split semantics. Many B+ tree designs move the promoted internal separator upward while leaf splits copy a boundary upward.
A Common Failure: Child Pointers Shift Out of Sync
Symptom
Separator array looks sorted but queries enter the wrong pages.
Repair
Treat keys and child slots as one interleaved routing sequence. Validate every child’s lower and upper bounds recursively.
Testing Internal Pages
Boundary Queries
For each separator, test less-than, equal and greater-than-nearby keys.
Structural Cases
Test root routing, internal split, internal merge, borrowing from both sides and separator updates after leaf changes. Internal-page tests should prove routing, not only key-array sorting.
Property-Based Routing Validation
Generate Sorted Leaf Ranges
Build many leaves with known min/max keys.
Check Every Search Path
Random queries should always descend through pages whose declared/fence ranges contain the key. Cross-check the reached leaf against a trusted sorted reference. This catches stale or misindexed separators.
Observability for Internal Routing
Track Height and Internal Cache Hit Rate
These reveal the cost of vertical descent.
Track Separator Search Cost
If CPU dominates even with hot pages, node-local search strategy or key compression deserves attention. Internal-page performance is a combination of fan-out, memory locality and comparison cost.
Rainbolt and CivDJ Views
Rainbolt View: Internal Pages Are Airport Departure Boards
They do not contain the destination itself. They tell you which gate leads to the region containing it. Equality with a board label does not mean you have arrived.
CivDJ View: Routing Pages Are Infrastructure
A database engineer sees page IDs, a query engine sees ordered boundaries, a storage engineer sees cacheable metadata, and a concurrency engineer sees fence keys and sibling links. One compact page coordinates many lower pages.
How to Teach Internal B+ Tree Pages
Start With a B-Tree Node
Then remove record payload from internal entries.
Ask What the Freed Space Buys
More separators, more children, fewer levels. Then show why a search matching a separator must still descend. That one contrast explains most of the B+ tree internal-page identity.
Frequently Asked Questions
Can an Internal Separator Also Exist at a Leaf?
Yes, often by design. The internal copy routes; the leaf copy is the real searchable entry.
Do Internal Pages Need Leaf Links?
Not for the basic B+ tree abstraction. Production implementations can link pages at multiple levels for concurrency and maintenance.
More Frequently Asked Questions
Why Not Store Full Records Internally Too?
That would reduce routing density and complicate the uniform leaf scan model. Classical B-trees can do it, but B+ trees deliberately separate roles.
Can Internal Keys Be Shorter Than Leaf Keys?
Yes, if the shortened representation still distinguishes adjacent child ranges correctly under the comparator.
The Pillar Boundary and Sources
What This Article Owns
This pillar owns B+ tree internal routing: separator semantics, child selection, fan-out, page identifiers, truncated separators, internal splits and routing validation. Leaf payloads and range scanning have a separate owner.
Sources and Further Reading
For internal-page structure, see CMU 15-445/645: B+Tree Project. For a production page-level B-tree implementation with internal downlinks and linked levels, see PostgreSQL Documentation: B-Tree Indexes.
Final Synthesis: Internal Pages Are Compressed Search Decisions
The Mechanism
Pack many ordered boundaries and child page IDs into each internal page, choose one child per lookup, and update separators whenever child ranges change.
Why It Matters
Internal pages make the tree shallow because they spend nearly all their space on routing. Their entire value comes from one promise: every search key is sent toward the leaf range that can contain it.
Worked Internal Routing Example With Equality Boundaries
Suppose the Page Holds Separators [20,40,60]
Assume the convention says each separator is the first key of the child to its right. Then keys below 20 follow child 0; keys from 20 up to but not including 40 follow child 1; keys from 40 to below 60 follow child 2; keys 60 and above follow child 3. A query equal to 40 must therefore go right of separator 40, not left. The comparison operator used by the page search must encode that exact convention.
Why This Boundary Test Belongs in Unit Tests
Random queries often miss equality bugs because most values fall between separators. Directed tests should query each separator exactly, one value just below it and one just above it. If a page uses a truncated separator or composite key, test the logical boundary rather than only byte equality. Routing correctness lives at boundaries.
Worked Internal Split: The Promoted Key Changes Parent Geometry
One Old Child Route Becomes Two
Before the split, parent P has one child pointer C covering a broad interval. C overflows. Internal split creates left page L and right page R and promotes boundary K into P. Afterward, P has two adjacent child pointers L and R with K between them. Every key formerly routed to C must now route to exactly one of L or R. No unrelated parent interval should change.
The Promoted Internal Separator Is Usually Routing-Only
Under common B+ tree semantics, the promoted internal separator is removed from the child pages. This differs from a leaf split where the boundary key remains as a real leaf entry and a copy is placed in the parent. Keeping those cases distinct is essential to preserve both record count and routing geometry.
Routing With Truncated Separators
Only Enough Key Material to Distinguish Adjacent Children Is Needed
If every key in left child begins below a certain prefix boundary and every key in right child begins above it, an internal separator can sometimes be shortened. This reduces page entry size and increases fan-out. The savings are especially valuable for long text and composite indexes because internal levels are traversed by nearly every lookup.
Truncation Must Preserve All Possible Search Decisions
A truncated separator is not merely a compressed copy. It is a proof obligation: for every legal search key, comparing against the truncated boundary must route to a child that could contain that key. Locale rules, variable encodings and duplicate prefixes can make this subtle. Production engines encapsulate separator truncation inside well-tested operator semantics rather than improvising prefixes during page writes.
Internal Pages and Composite-Key Prefixes
Lexicographic Order Converts Multiple Columns Into One Search Line
An index on (country, city, id) has a total order: compare country first, then city, then id. Internal pages do not need separate routing rules for each column. They store separators in the combined order and choose children by the full comparator. This is why one B+ tree can support exact tuple lookup and useful left-prefix ranges.
Prefix Queries Still Depend on Full Boundaries
A query for all entries where country=’SG’ can be translated into a lower and upper tuple boundary. Internal routing positions the scan at the first leaf in that tuple range. Separator semantics remain full-key semantics even when the application predicate mentions only a prefix.
Internal Fan-Out Worked Example
Why Saving Bytes Matters Multiplicatively
Suppose an internal page can hold 100 child routes. Two internal levels beneath the root can address on the order of a million leaf regions in the rough branching sense. Increase fan-out to 150 through separator compression and those same levels cover far more leaves. The exact counts depend on root occupancy and implementation, but the lesson is durable: small per-entry savings multiply at every internal level.
The Height Benefit Can Remove a Page Read From Every Query
If better density keeps the tree at three levels instead of four for a large dataset, every cold lookup can avoid one storage-page transition. This is why internal page formats receive intense optimisation attention even though they contain no user-visible records.
Fence Keys and High Keys as Local Ownership Proofs
A Page Can State the Range It Currently Owns
A high key gives an upper boundary for the page. If a search key is beyond that boundary, the page knows it should not answer locally even if the parent path that brought the search there is temporarily stale due to a concurrent split. The reader can move right under the concurrency protocol.
This Turns Range Metadata Into a Safety Mechanism
Fence keys are not part of the simplest B+ tree definition, yet they illustrate an important production principle: make ownership explicit so local pages can validate navigation. A page that can say “your key is beyond my range” is more robust under structural change than one that trusts the parent route blindly.
Internal Pages Under Concurrent Splits
Parent Installation Can Lag Behind Child Creation
A splitter can create a right sibling and establish sibling/fence relationships before the parent receives the new separator. During that window, a search can arrive at the old child even though its target moved right. Concurrency-safe variants allow the page to redirect the search horizontally rather than requiring the whole split to appear atomic to all readers.
Eventual Parent Repair Restores the Fast Path
Once the parent separator is installed, future searches choose the new child directly. Horizontal correction remains a safety net rather than the normal route. This distinction between stable routing and transient recovery is central to understanding production B+ tree algorithms.
Internal Merge and Separator Removal
Two Routing Pages Become One Range
When underfull internal siblings merge, the parent boundary separating them is consumed by the merge under the implementation’s rules. Parent child count falls by one. The resulting page must cover the full union of both old ranges without overlap or gaps.
Root Shrink Is the Top-Level Version of the Same Contraction
If repeated merges leave the root with no routing key and one child, the child becomes the new root. The internal routing layer loses one level while every leaf remains aligned. This keeps the tree minimal in height as data volume shrinks.
Internal Page Failure Modes in Persistent Storage
A Torn Separator Update Can Misroute an Entire Subtree
Unlike a corrupt leaf entry that can affect one key, a wrong internal separator can redirect a whole interval. Checksums, WAL, copy-on-write and page-version validation exist partly because routing pages have disproportionate blast radius. Recovery systems must restore coherent separators and downlinks, not just parseable bytes.
Root Page Corruption Has Maximum Blast Radius
The root is the entry point for every lookup. Systems commonly protect root metadata and metapages carefully. A root pointer update during split or shrink should be atomic or recoverable because an otherwise intact lower tree is useless if the new entry point is lost.
Internal Routing Postcondition Checklist
Per-Page Checks
Separators sorted; child count consistent with page format; equality direction matches separator convention; every child page ID valid; fence/high-key metadata coherent; occupancy legal; compressed separators decode or compare correctly; local search returns the expected child index for directed boundary tests.
Whole-Tree Checks
Every leaf range reachable through exactly one vertical route in the stable structure; all leaves at one depth; parent separators consistent with child minima/maxima; no internal page orphaned; root metadata points to the current version; random search paths agree with a trusted sorted reference for exact and lower-bound queries.
Internal Pages Are a Performance Amplifier
Good Internal Density Benefits Every Query
Leaf compression helps only queries that reach those leaves. Internal compression and fan-out reduce height for nearly every lookup and range start. This gives internal-page engineering an unusually broad payoff across workloads.
But Routing Correctness Comes Before Density
A separator that is one byte shorter but routes one boundary incorrectly is catastrophic. Optimise representation only after the logical child-range contract is explicit and independently validated. B+ tree performance is built on correct routing, not in place of it.
Routing Review: Internal Pages Encode Decisions, Not Records
A useful final distinction is to imagine deleting every record pointer from the leaves while leaving internal pages intact. The tree would still know how to route key ranges but would no longer contain the actual index entries. Now imagine keeping leaves but deleting internal pages: the data would remain sorted but exact positioning would require scanning from an edge. B+ tree performance comes from combining these two specialised layers.
This separation also explains why internal-page corruption has a large blast radius. One bad separator can misroute an entire interval even though every affected leaf is individually correct. Routing validation therefore deserves independent tooling and boundary-focused tests.
Internal Page Search Cost With Expensive Keys
High fan-out reduces page levels, but each separator comparison can still be expensive when keys are long strings, locale-aware text or composite values. Systems may store abbreviated keys, cached comparison prefixes or truncated separators to reduce CPU work. Those optimisations are safe only when they preserve the exact child-selection result that the full comparator would produce.
The practical cost of one internal page is therefore a product of entry width, number of comparisons, cache locality and comparator complexity. A theoretically wider node is not automatically faster if its search algorithm or key representation becomes too expensive.
Internal Page Observability for Production Indexes
Track internal-page occupancy, tree height, upper-level cache hit rate and average number of separator comparisons per descent. If height grows unexpectedly, fan-out or fill may have fallen. If height is stable but CPU rises, separator search or comparator cost may be the bottleneck. These metrics separate structural problems from local page-search problems.
Also sample boundary correctness after structural maintenance. A page that becomes sparse or receives a new child after split can have valid occupancy but stale separators. Periodic consistency checks that compare parent boundaries with child minima/maxima are especially valuable in long-lived indexes.
Internal Pages in a Copy-on-Write Tree
When a leaf changes in an immutable or snapshotting B+ tree, every ancestor on the path to the root may need a new version because one child pointer now refers to a new page. If a split changes boundaries, the copied parent also receives the new separator. Untouched siblings can be shared safely because their ranges and page identities did not change.
The small height of a high-fan-out tree makes this path copying feasible. The trade-off shifts from in-place latch complexity toward extra page allocation and later garbage collection. Internal routing semantics remain unchanged: each new parent version must still map every key to exactly one valid child range.
Internal Routing Postcondition in One Sentence
For every possible search key, the page must choose a child whose subtree could contain that key under the index comparator. That statement is stronger and more useful than “the keys are sorted.” Sorted separators are necessary, but correct range ownership, equality direction, truncated-boundary semantics and child-pointer alignment are what actually make the page a routing structure.
Whenever a split, merge, redistribution, collation change or page-format migration occurs, re-prove that one sentence. It is the invariant beneath all internal B+ tree engineering.
Internal Routing Review: The Separator Is a Promise About a Subtree
An internal separator is useful only because it summarises a much larger descendant range. When a separator says “keys from here onward belong to the right child,” the implementation is making a promise about every leaf beneath that child. Structural maintenance, separator truncation and collation semantics must all preserve that promise. The page is therefore not just a sorted list of keys; it is a compact certificate of how lower-level key space has been partitioned.
This perspective helps debugging. If an exact lookup misses a present key, inspect the first ancestor whose separator promise is false. The leaf may be perfectly correct. The failure can originate several levels above where a stale or miscompared boundary sends the search down the wrong subtree. Tracing the violated range promise is often faster than inspecting every descendant page.
Internal Page Integrity Under Rebuilds and Migrations
Index rebuilds, page-format upgrades and collation-aware migrations can rewrite every internal page without changing the logical record set. A strong verification process samples or exhaustively checks that each rebuilt parent boundary agrees with the minima and maxima of its children and that lower-bound searches reach the same leaf positions as a trusted sorted reference. Physical representation can change completely while routing semantics remain stable.
The final test is end-to-end: generate keys around every separator, descend from the root using the production comparator and confirm the reached leaf range could legally contain each key. That is the internal B+ tree contract in executable form.
Internal Routing Closing Note
Internal B+ tree pages should be judged by the accuracy and density of the decisions they encode. They do not need to know how a row is stored, whether a range scan will be long, or how MVCC will filter leaf entries. They need one reliable capability: given a key under the index comparator, choose a child whose descendant range can contain it. Everything else—separator truncation, SIMD search, fence keys, page IDs, cache layout and concurrency metadata—exists to make that decision cheaper or safer without changing its meaning.
That narrow responsibility is what allows the rest of the B+ tree to scale. Dense routing keeps height low, while leaf pages remain free to optimise record storage and scans. The split between routing and records is therefore not merely a layout preference; it is the architectural boundary that gives the B+ tree its characteristic shape.
Next pillar: How B+ Tree Leaf Nodes and Range Scans Work · Next pillar: How B+ Tree Splits and Merges Work
For production review, boundary-directed search tests should be repeated after every separator-changing operation, not only after initial construction. A B+ tree can remain globally balanced while one stale internal boundary quietly misroutes a narrow key interval.