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 Nodes Work | Keys, Children, Minimum Degree, High Fan-Out and Storage Pages

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

B-tree nodes work by packing several sorted separator keys, several child pointers and often storage metadata into one multiway unit. One node therefore represents many key intervals at once. Search does more work inside the node so the tree can make far fewer expensive transitions between nodes.

The node structure is the heart of the B-tree. Its occupancy limits determine fan-out, height, split thresholds, merge thresholds and page utilisation. If keys and child pointers are not kept in exact positional correspondence, the tree may remain locally sorted while routing queries into the wrong subtrees.

This pillar explains node keys, child intervals, minimum degree, maximum and minimum occupancy, root exceptions, leaf versus internal layout, page sizing, variable-length keys, separator compression, binary versus linear search inside a node, child-pointer coupling, high fan-out, storage pages, cache locality, fill factor, validation and the implementation failures that make multiway search trees difficult despite their simple picture.

Master guide: How B-Trees Work · Foundation: How Binary Search Trees Work · How X Works Hub


The Node Is a Sorted Directory of Ranges

Keys Partition the Search Space

Suppose a node stores k1

Child Count Is One More Than Key Count

In a standard internal B-tree node with m keys, there are m+1 child pointers. That arithmetic is not incidental. It is the structural expression of how m separators divide an ordered line into m+1 intervals.


Leaf Nodes and Internal Nodes Have Different Jobs

Leaves Terminate Search Paths

Leaf nodes contain keys but no ordinary child pointers. Under the classical model, records or payloads may be stored with those keys.

Internal Nodes Route Search

Internal nodes combine separator keys with child references. Production systems may also store record references internally, but many B+ tree variants reserve full records for leaves. This pillar stays with the classical B-tree node model.


Minimum Degree t Gives a Clean Occupancy Model

Maximum Keys Are 2t−1

Under the common CLRS-style convention, a node is full when it contains 2t−1 keys.

Non-Root Minimum Is t−1 Keys

Every non-root node keeps at least t−1 keys. An internal node with t−1 keys therefore has at least t children. These lower bounds prevent the tree from becoming too sparse.


The Root Has Special Occupancy Rules

A Non-Leaf Root Needs Fewer Keys Than Other Internal Nodes

The root can have only one key and two children without violating B-tree validity.

A Small Root Lets the Tree Grow and Shrink Naturally

Without a root exception, creating a new tree or shrinking after deletion would require artificial minimum filling. Root flexibility keeps the structure dynamic while all lower levels remain dense.


Fan-Out Is the Performance Lever

More Children Mean Fewer Levels

If one internal node can route among hundreds of children, the tree height grows very slowly even for enormous datasets.

Node Capacity Converts Storage Geometry Into Algorithmic Height

Choosing how many keys fit in a node is therefore not just a representation detail. It directly changes the base of the logarithm governing node accesses.


Why Page Size Often Determines Node Size

Storage Reads Happen in Blocks

Databases and filesystems typically fetch pages or blocks rather than individual keys.

A Good Node Tries to Use Most of One Block

If one node fits a page, reading it once provides many separators and child addresses. Oversized nodes require multiple page reads; undersized nodes waste capacity and increase height.


Node Layout Is More Than an Array of Keys

Headers and Metadata Consume Space

A page may store key count, flags, parent or sibling metadata, checksums, free-space offsets, transaction data or compression information.

Effective Fan-Out Uses Remaining Bytes

Theoretical key capacity based on raw page size can overestimate real occupancy. Systems engineers calculate fan-out from the full physical page format.


Fixed-Length Keys Make Capacity Simple

Each Entry Has Predictable Size

If every separator key and child pointer uses a fixed number of bytes, maximum entries per page can be estimated directly.

Split Points by Count Are Reasonable

A midpoint by key count roughly balances bytes when all entries are similarly sized. The abstract minimum-degree model matches this situation cleanly.


Variable-Length Keys Make Capacity a Byte Problem

One Key Can Consume Far More Space Than Another

Text keys, composite indexes and variable-width encodings create uneven entry sizes.

A Half-by-Count Split Can Be Badly Unbalanced by Bytes

Production engines may choose split points based on occupied bytes, target fill factor or key compression. The mathematical B-tree invariant can coexist with byte-aware policies.


Separator Keys Need Not Always Store Full User Keys

Only Enough Information to Separate Adjacent Child Ranges Is Required

In some B+ tree and storage-engine designs, internal separators can be shortened or prefix-compressed.

Smaller Separators Increase Fan-Out

Saving bytes per key can let many more child pointers fit in a page, directly reducing tree height and storage I/O. Compression at the node level becomes an algorithmic performance optimisation.


Search Inside a Node Can Be Linear

Sequential Scan Has Low Overhead

For modest key counts or CPU-cache-resident arrays, walking separators from left to right can be efficient.

Branch Prediction and Locality Matter

A theoretically O(m) scan through one node may outperform a branch-heavy binary search when m is small and the data is contiguous. Node-level algorithms should be benchmarked on realistic hardware.


Search Inside a Node Can Be Binary

Sorted Keys Permit Binary Search

For larger nodes, find the first key not less than the query in O(log m) comparisons.

The Result Is Either a Match or a Child Index

If the key matches, return it under classical semantics. If not, the insertion/search position directly identifies the child interval to descend into.


Branchless and Vectorised Node Search

Modern Hardware Can Compare Several Keys Efficiently

Specialised indexes may use SIMD, branchless comparisons, interpolation or compact key prefixes.

The B-Tree Abstraction Allows This Freedom

The only semantic requirement is to choose the correct separator position. How a node computes that position is an implementation detail that can be optimised independently.


Keys and Children Must Move Together

Separator Positions Define Child Intervals

Changing key order without matching child pointers sends queries into incorrect ranges.

Internal Splits and Merges Are Coupled Transformations

When keys are redistributed, child arrays must be partitioned or concatenated at exactly corresponding boundaries. Many serious B-tree bugs come from updating keys correctly but misaligning one child pointer.


A Node’s Local Invariant Can Be Stated as Ranges

Every Child Has Lower and Upper Bounds

Child 0 is below key 0. Middle child i lies between key i−1 and key i. Final child lies above the last key.

Validation Can Propagate Those Bounds Recursively

A robust checker passes allowable key intervals into each child subtree and verifies that every descendant respects them. Local sorting alone is insufficient because a whole subtree can be attached to the wrong interval.


High Occupancy Protects Height

Sparse Internal Nodes Waste Branching Capacity

If most nodes held only one or two keys, a multiway tree would behave more like a taller binary tree.

Minimum Occupancy Forces Exponential Breadth

Requiring each non-root internal node to have at least t children means node count expands rapidly with depth. That lower-bound branching is the mathematical source of logarithmic height.


Full Nodes Signal Insertion Pressure

At Maximum Key Count, No More Key Fits Under the Model

A new insertion into that node requires structural change.

Splitting Converts One Full Node Into Two Legal Nodes

The median separator moves upward into the parent, creating two child ranges. The insertion pillar owns the mechanics, while this pillar owns what ‘full’ means structurally.


Minimum Nodes Signal Deletion Pressure

A Non-Root Node at t−1 Keys Has No Spare Capacity to Lose Another

Deletion that removes one more key would underflow.

Borrowing or Merging Restores Occupancy

A sibling with extra keys can donate through the parent; otherwise two minimum siblings can merge with their separating parent key. The deletion pillar owns those operations.


Root Capacity Does Not Affect the Height Proof Much

The Root Has Fewer Guaranteed Children

It may begin with only two children when internal.

Below the Root, Minimum Fan-Out Applies Everywhere

The exponential breadth from lower levels dominates. The relaxed root changes constants, not the logarithmic asymptotic bound.


Page Fill Factor Is a Performance Policy

High Fill Maximises Fan-Out

More keys per page generally means fewer pages and lower height.

Free Space Reduces Immediate Split Frequency

Leaving headroom can make random insert workloads cheaper. Systems balance read efficiency, write amplification and future growth rather than filling every page to the theoretical maximum.


Sequential Insert Workloads Stress One Edge

Ascending Keys Keep Targeting the Rightmost Leaf

That page fills and splits repeatedly while older pages remain stable.

Some Systems Tune Edge Splits Differently

An append-heavy index can benefit from leaving different free-space proportions on the right edge. This is a workload optimisation layered on the same node-capacity semantics.


Page Identifiers Replace Raw Pointers on Disk

A Child Reference May Be a Page Number or Block Address

The conceptual pointer is an identifier that the buffer manager resolves into memory.

Node Access Cost Includes the Buffer Layer

If the child page is cached, descent is cheap; if not, it may trigger storage I/O. The same logical B-tree can behave very differently under different cache hit rates.


Buffer Pools Make Hot Upper Levels Cheap

Root and Upper Internal Nodes Are Frequently Reused

They often stay resident in memory.

Most Storage Cost Then Occurs Near Leaves

A B-tree’s small height and hot upper pages mean many searches need only one or two actual storage misses. This is one reason high fan-out works so well in databases.


Node Compression Can Increase CPU Cost While Reducing I/O

Prefix and Delta Encoding Save Space

More separators fit per page.

Decoding Adds Local Work

The trade is usually favourable when storage movement is expensive. B-tree design repeatedly exchanges extra in-node computation for fewer node transfers.


Cache-Line-Aware In-Memory B-Trees

B-Trees Are Not Only for Disks

Even in RAM, pointer chasing across many binary nodes can miss CPU caches.

Packing Multiple Keys Into Compact Nodes Improves Locality

In-memory B-tree variants exploit cache lines and SIMD while preserving multiway ordered search. The same high-level idea scales down from disks to processor caches.


Internal Keys as Records Versus Separators

Classical B-Trees Can Store Data With Internal Keys

A search can terminate before reaching a leaf.

B+ Trees Usually Store Payload at Leaves

Internal keys are routing separators, and leaf links support range scans. Keeping this distinction explicit avoids claiming that every production ‘B-tree index’ follows the same node semantics.


Leaf Links Are Not a Classical B-Tree Requirement

A Pure B-Tree Can Traverse by Tree Navigation

Sorted enumeration follows recursive child/key order.

B+ Trees Commonly Link Leaves

This makes long range scans sequential across leaf pages. Leaf linking is important enough to deserve the separate B+ tree cluster rather than being silently treated as universal B-tree structure.


Node Splitting Changes Parent Capacity

A Split Removes One Full Child Entry and Adds Two

The parent gains one separator key and one extra child pointer.

Parent Can Become Full Too

Cascading split pressure moves upward. The node model explains why one child split consumes capacity in the parent and why root split is the height-growth event.


Merging Changes Parent Capacity in the Opposite Direction

Two Children Become One

Their separating parent key moves down into the merged node.

Parent Loses One Key and One Child

If the parent was at minimum occupancy, it may underflow and require repair above. Insertion and deletion are structural duals around node occupancy.


Node Search and Duplicate Keys

Unique Indexes Have Simple Separator Semantics

Each key maps to one logical entry.

Duplicate-Capable Indexes Need Tie-Breaking

Production indexes can include record IDs or hidden tuple identifiers so multiple equal user keys still have a total internal order. The comparator must define a stable ordering across all entries.


Composite Keys Create Lexicographic Intervals

An Index on (A,B) Sorts by A Then B

Node separators divide the combined key space according to the full comparator.

Prefix Queries Can Use Ordered Ranges

Queries fixing A and ranging B naturally map to contiguous intervals, one reason B-tree-family indexes are powerful for database predicates.


Nulls, Collations and Custom Orders Matter

Database Comparators Define the Index Order

Text collation, null placement, descending components and type-specific operator classes influence separator meaning.

Physical Tree Correctness Depends on Comparator Stability

If ordering semantics change without rebuilding the index, node ranges may no longer match query comparison rules. Index metadata and comparator versions matter operationally.


A Common Failure: Wrong Child Count

Symptom

An internal node with m keys stores m children or m+2 children.

Consequence

One interval has no route or two pointers claim the same boundary position. Assert childCount=keyCount+1 for every ordinary internal node.


A Common Failure: Key Array Sorted Locally but Subtree Bounds Wrong

Symptom

Node keys look perfect, yet search misses entries.

Cause

A child pointer was moved to the wrong slot during split, merge or borrow. Validate descendant bounds, not only the key array.


A Common Failure: Apply Non-Root Minimum to Root

Symptom

Small valid trees are rejected or root is force-filled unnecessarily.

Repair

Root has explicit exceptions. Treat root occupancy separately in validation and update logic.


A Common Failure: Capacity Counts Ignore Metadata Bytes

Symptom

A page thought to hold N entries overflows after headers, slot directories or variable-length key data are added.

Repair

Compute physical capacity from the actual page format. The abstract maximum-key model must be mapped carefully to bytes.


A Common Failure: Variable-Length Split by Count Only

Symptom

One new page is nearly empty while the other remains close to full.

Repair

For page-based systems, choose split positions with byte utilisation and future workload in mind while preserving legal occupancy and separator semantics.


A Common Failure: Comparator Changes After Index Build

Symptom

Search routing no longer matches stored ranges.

Repair

Ordering semantics are part of the index definition. Rebuild when collation or comparison rules change in a way that affects order.


Testing Node Invariants

Check Local Structure

Keys sorted, legal key count, correct leaf/internal flag, internal child count one greater than key count.

Check Global Structure

Propagate separator bounds into children, require all leaves at one depth, verify root exceptions, count all logical entries once and compare with the container’s stored size.


Page-Level Testing

Fill Nodes to Exact Boundaries

Test one key below full, exactly full, and split-triggering insertion.

Test Minimum Occupancy Boundaries

Delete down to exactly minimum, then trigger borrow and merge. Boundary tests catch off-by-one convention mistakes better than large random workloads alone.


Two Practical Perspectives on a B-Tree Node

A Node Is a Local Map of Several Streets

Instead of one sign saying left or right, the node has many ordered signposts. Read them once, then choose the one district that can still contain the destination.

The Node Is Where Algorithm Meets Hardware

A theorist sees m separators and m+1 intervals. A database engineer sees a page. A hardware engineer sees cache lines. A storage engineer sees checksums and free space. The node’s capacity is where mathematical fan-out becomes physical performance.


How to Teach B-Tree Nodes

Begin With a BST Node and Add One More Separator

A two-key node divides the world into three ranges. Add another key and get four ranges. The multiway concept becomes obvious before occupancy formulas appear.

Then Introduce the Page Cost Model

Once students understand that one node may arrive in one expensive I/O, high fan-out stops looking arbitrary. The node is deliberately wide because movement is expensive.


Frequently Asked Questions

Does Every B-Tree Node Have the Same Number of Keys?

No. Nodes vary within legal occupancy bounds. Only maximum and minimum counts are constrained.

Why Does an Internal Node Have One More Child Than Keys?

Because m ordered separator keys divide key space into m+1 intervals.


More Frequently Asked Questions

Does a B-Tree Node Have to Fill a Disk Page?

No. That is a common systems design, not a mathematical requirement. In-memory B-trees can choose node size for cache behaviour.

Can Keys Have Different Lengths?

Yes, but physical page capacity and split policy become byte-oriented rather than simple key-count arithmetic.


The Pillar Boundary and Sources

What This Article Owns

This pillar owns B-tree node structure: sorted multi-key arrays, m+1 child intervals, occupancy, minimum degree, root exceptions, page sizing, local search and physical node layout. Splitting and deletion repair have separate owners.

Sources and Further Reading

For the structural B-tree model, see Open Data Structures: B-Trees. For a production indexing perspective, see PostgreSQL Documentation: B-Tree Indexes.


Final Synthesis: A B-Tree Node Is a Page-Sized Ordered Decision Table

The Mechanism

Store several sorted separators, keep one child interval around each gap, respect occupancy bounds and search locally before descending.

Why It Matters

The node converts one expensive access into many useful comparisons. Its width creates fan-out; fan-out creates low height; low height is what makes B-tree families effective across storage systems.


Worked Node Layout: Keys and Children as One Coupled Array

A Three-Key Internal Node Has Four Child Intervals

Take keys [15, 30, 50]. Child 0 contains keys below 15. Child 1 contains keys from 15 up to 30 under the chosen strict/non-strict boundary policy. Child 2 covers 30 to 50. Child 3 covers values above 50. The important point is positional coupling: child 2 is meaningful only because keys 30 and 50 sit on either side of it. Moving one key without the corresponding child interval corrupts routing even when every local array remains sorted.

Validation Should Treat the Node as an Interleaved Sequence

A useful mental model is child0, key0, child1, key1, child2, key2, child3. Splitting, borrowing and merging all transform that interleaved ordered sequence. This viewpoint makes child-pointer bugs easier to detect because every structural edit can be checked against the same left-to-right range order rather than against two separate arrays maintained by intuition.

Node Capacity Worked Example in Bytes

A Page Has More Than Key Payload

Imagine a 4 KiB page with a header, slot directory, checksums and child references. If one separator entry averages 24 bytes after including pointer or record metadata, the theoretical raw 4096/24 estimate is too optimistic because the page header and alignment consume space. Variable-length entries reduce predictability further. Real fan-out is therefore a physical-layout calculation, not simply a mathematical order parameter.

Small Per-Entry Savings Multiply Into Height Savings

If prefix compression or shorter child identifiers save even a handful of bytes per separator, a page may hold many additional entries. Across every internal level, that raises fan-out and can reduce the number of levels required for large indexes. Systems engineers care about these seemingly small layout details because one fewer page level can remove an entire I/O from many operations.

Slot Directories Separate Logical Order From Physical Placement

Variable-Length Records Need Not Be Physically Sorted Byte-for-Byte

A page can store record bodies in convenient free-space locations while a compact slot array keeps pointers to them in key order. Inserting a new key may shift only slot entries rather than moving every large payload. The B-tree sees one logically sorted node even though the bytes inside the page use an indirection layer.

Compaction Becomes a Page-Maintenance Operation

Deletes can leave fragmented free space. A storage engine may compact record bodies while preserving the ordered slot array. This is a reminder that B-tree node correctness is about logical separators and child ranges, not one specific byte layout. Physical page housekeeping can change without altering the abstract node.

Internal Separators Can Be Shorter Than Full User Keys

Only the Boundary Distinction May Be Needed

If the greatest key in the left child is “greenland-00042” and the smallest key in the right child is “greenland-09103,” an internal separator may need only enough prefix bytes to distinguish the ranges under the comparator. Exact techniques depend on the engine and collation rules, but the principle is stable: internal routing information can sometimes be represented more compactly than leaf data.

Compression Must Preserve Comparator Semantics

A shortened separator is correct only if every valid search key is routed to the same child it would choose under the full logical boundary. Locale-aware text, variable encodings and composite keys make this subtle. Page compression is therefore not merely storage optimisation; it is part of ordered-search correctness.

Node Search Strategy Should Match Fan-Out

Linear Search Can Win in Tiny Nodes

If a node has only a handful of keys, sequential comparisons may minimise branches and exploit contiguous memory. Binary search’s asymptotic advantage has little room to appear. This is especially true when one page is already hot in cache and comparisons are cheap integers or short prefixes.

Binary or Vector Search Becomes Attractive in Wide Nodes

As fan-out grows, searching dozens or hundreds of separators linearly adds CPU work. Binary search, branchless search or SIMD-assisted comparison can reduce that cost. The B-tree abstraction allows the node-local search algorithm to evolve independently as long as it returns the same exact match or child interval.

Node Occupancy Is Both a Correctness Bound and a Utilisation Metric

Minimum Occupancy Protects Height

The lower bound ensures each internal level retains enough branching to keep the tree shallow. A valid tree with chronically half-empty or minimally filled pages may still meet the asymptotic guarantee, but it uses more pages and more memory than a denser tree.

Average Occupancy Describes Physical Health

Track not only whether every node is legal but how full pages actually are. Split policy, delete-heavy workloads and key-size variation can produce a valid yet poorly utilised index. Periodic rebuild or vacuum-like maintenance may improve density without changing the logical key set.

Node Boundaries Under Composite Indexes

One Separator Can Represent a Lexicographic Tuple

For an index on (surname, given_name, id), the separator order uses the full tuple. Child ranges are therefore multidimensional in application meaning but one-dimensional under the comparator. Search and split logic do not need to understand the fields individually; they need one stable total ordering.

Prefix Predicates Work Because Tuple Order Is Structured

All keys sharing a fixed leading component occupy a contiguous ordered range. That is why database B-tree-family indexes can support many left-prefix query patterns efficiently. The power comes from comparator semantics embedded in node ranges, not from any special awareness of SQL columns inside the tree algorithm.

Page Identity and Buffer-Manager Interaction

Child References Often Name Pages, Not Memory Addresses

An internal node can store page IDs. The buffer manager resolves a page ID into an in-memory frame, loading from storage only if necessary. This indirection allows pages to move between memory and disk while the logical tree continues to use stable identifiers.

Upper Nodes Often Stay Hot

The root and upper internal pages participate in nearly every lookup, so they are likely to remain cached. Practical search cost then concentrates in lower levels. Node design that maximises upper-level fan-out can therefore have disproportionate value: one compact internal page can route huge portions of the entire dataset.

Node-Level Failure Atomicity

Partial Page Writes Can Break More Than One Key

A torn or incomplete update can corrupt key count, slot offsets and child references together. Storage engines use checksums, write-ahead logging, shadow paging or copy-on-write strategies so a node is either recovered to the old valid state or completed to the new one after a crash.

The Abstract Node Needs a Durable Representation Contract

Textbook invariants assume writes happen atomically. Real pages need format versions, recovery rules and validation on read. The multiway node is where algorithmic correctness meets persistent-data correctness most directly.

A Node Postcondition Checklist

Logical Checks

Keys sorted; legal duplicate semantics; internal child count exactly key count plus one; each child subtree falls inside its separator bounds; leaf flag agrees with presence or absence of child references; occupancy respects root and non-root rules.

Physical Checks

Page header sane; offsets within bounds; no overlapping live records; free-space accounting correct; child page identifiers valid; checksum or page integrity metadata valid where used. A B-tree node is trustworthy only when both logical order and physical page representation agree.

Node Engineering Review: Fan-Out Is Bought With Local Complexity

Wider Nodes Reduce Height but Increase Local Work

A node with hundreds of separators dramatically reduces tree height, but one visit now involves searching a larger local array, maintaining more offsets, moving more bytes during split or merge and validating more child boundaries. B-tree design is therefore an optimisation problem rather than a command to maximise fan-out blindly. The best node width balances page size, key width, cache behaviour and update cost.

Fan-Out Is Effective Only When Pages Stay Dense

A theoretical page capacity of 200 children is not the same as an average live fan-out of 200. Delete-heavy workloads, variable key sizes and conservative fill factors can lower effective branching. Tree-height planning should use realistic occupancy distributions, not only the maximum. This is why average fill is an operational metric as important as the abstract order parameter.

Fence Keys, High Keys and Page Range Ownership

A Page Can Carry Explicit Range Metadata

Some B-tree-family implementations store lower or upper fence keys describing the page’s permitted key interval. These values make page ownership explicit and help validation, concurrent navigation and recovery after splits. A search arriving at a page can detect that its target lies beyond the page’s current range and follow a sibling or restart path under the implementation’s protocol.

Range Metadata Must Move With Splits and Merges

When one page splits into two, the old range is divided. When siblings merge, their adjacent ranges recombine. Fence-key maintenance is therefore another derived invariant layered onto separator order. Production B-tree nodes often carry more structural information than the textbook key-and-child picture, but each field should still be explainable as part of routing or recovery.

Node Format Versioning and Long-Lived Indexes

Persistent Nodes Outlive One Process

An on-disk B-tree can survive software upgrades. Page headers may therefore include format versions or feature flags so new code can interpret old layouts safely. Changing key encoding, compression or child-reference width is not merely an in-memory refactor when millions of persisted pages already exist.

Migration Must Preserve Ordered Meaning

A page-format migration can rewrite physical representation while leaving logical separator order unchanged. Validators should compare the rebuilt node against the same comparator and child-range invariants. The B-tree abstraction is useful precisely because physical format can evolve beneath a stable ordered-tree contract.

Node-Level Observability in Production

Inspect Occupancy Histograms, Not Only Averages

An average fill of 70% can hide a mixture of almost-empty and almost-full pages. Histograms reveal whether the tree contains pathological sparse regions, hot full edges or healthy density. Pair occupancy with key-size distributions to understand whether page utilisation comes from workload history or variable entry widths.

Sample Search Position Inside Nodes

If most searches land near one edge of a node, a linear scan direction or branch strategy may be suboptimal. If separator comparisons dominate CPU despite low I/O, node-local search deserves tuning. Observability turns node design from static theory into measurable systems engineering.

Node Design Review: One Abstraction, Several Physical Realities

A classroom B-tree node is usually drawn as a box containing keys and arrows. A production node may instead be a slotted page with compressed separators, page identifiers, transaction metadata, fence keys and free-space accounting. These representations can all implement the same logical node if they preserve sorted separators, correct child intervals, legal occupancy and stable comparison semantics. This separation between logical node and physical page lets systems evolve storage formats without changing the search algorithm.

The safest engineering approach is therefore to define the logical invariants first and make page-format code prove that it implements them. When debugging a page split or merge, reconstruct the logical ordered node from the bytes and validate ranges independently. A physically well-formed page whose child intervals are wrong is still a broken B-tree node.

Node Postcondition Review: What a Search Page Must Guarantee

After any split, merge, borrow or compaction, a node must still answer one simple question correctly: given a search key, which exact child interval owns it? That requires sorted separators, stable comparator semantics, correct child count and correct positional pairing between separators and child pointers. Every other page optimisation—compression, slot indirection, checksums, fence keys or fill policy—sits around that core routing promise.

A useful review technique is to sample boundary keys immediately below, equal to and immediately above every separator, then verify the chosen child matches the expected range. This catches off-by-one duplicate rules and misplaced child pointers that random exact-key tests can miss. Multiway search structures are safest when boundaries are tested as deliberately as stored keys.

Next pillar: How B-Tree Insertion and Splitting Work · Next pillar: How B-Tree Deletion and Merging Work

The final node-design principle is simple: every physical optimisation should make the page cheaper to read, store or update without weakening the logical promise that one ordered comparison sequence selects exactly one correct child range. That promise is the irreducible core of a B-tree node.

Continue the B-Tree Series

How B-Trees Work · How X Works Hub