B+ tree leaf nodes and range scans work by concentrating the searchable entries at one balanced bottom level and linking those leaf pages in sorted order. Internal pages find the starting leaf. The leaves then carry the actual ordered key entries and provide a horizontal path for scanning neighbouring keys without repeatedly climbing back through the tree.
This design is especially powerful for database ranges. An exact lookup still benefits from logarithmic routing. A range query adds only one logarithmic positioning step, then scans forward page by page until the upper bound is passed. The amount of work after positioning is closely related to the number of qualifying leaf entries and pages actually visited.
This pillar explains leaf entry structure, record pointers, clustered versus secondary indexes, next and previous links, lower-bound positioning, BETWEEN scans, prefix ranges, duplicates, composite keys, reverse scans, index-only scans, fill factor, leaf compression, prefetch, MVCC visibility, leaf splitting, merging, concurrent scans, validation and the failure modes that exact point lookups can miss.
Master guide: How B+ Trees Work · Pillar: How B+ Tree Internal Nodes Work · How X Works Hub
The Leaf Layer Is the Record-Bearing Layer
All Searchable Entries Reach the Bottom
In the standard B+ tree model, exact record lookup continues until a leaf even if an internal separator equals the query key. Internal equality is routing information; leaf equality is the actual stored entry.
Leaves Hold Keys Plus Values or Row References
Depending on the system, a leaf value can be a row identifier, a pointer to a heap tuple, a primary key, a record payload or another locator. The B+ tree only requires that leaf entries are ordered by the index comparator.
All Leaves Share One Depth
Every Record Lookup Reaches the Same Structural Level
That uniformity makes leaf pages a coherent ordered frontier.
The Leaf Chain Has One Global Sort Order
Following next links walks through the entire logical index in key order, regardless of which internal path led to the starting page.
Next-Leaf Links Enable Forward Range Scans
One Pointer Connects Adjacent Key Ranges
The last entry of one leaf is followed logically by the first entry of the next leaf.
No Root Re-Search Is Needed
After consuming a leaf, the scanner follows the next page directly. This is the mechanism that turns one logarithmic search into a long sequential ordered traversal.
Previous-Leaf Links Enable Reverse Scans
Doubly Linked Leaves Support DESC Traversal
A scanner can find the upper bound and move leftward.
Not Every Abstract Definition Requires Both Directions
But many production indexes maintain bidirectional page links or equivalent level links because reverse scans, concurrency and maintenance benefit from them.
Lower-Bound Search Finds the Range Start
Route to the Candidate Leaf
Internal separators narrow the search to one leaf range.
Search Within the Leaf for the First Key Not Less Than x
That offset becomes the range iterator’s starting position. If the position is at the end of the leaf, move to the next leaf.
Upper Bound Defines the Stop Condition
Compare Each Candidate Against the Query’s High Endpoint
Stop when the key exceeds the inclusive upper bound or reaches the exclusive upper bound according to query semantics.
The Scanner Does Not Need Internal Pages Again
The ordered leaf chain guarantees that once one key is too large, every later leaf key is also too large.
A BETWEEN Query Is Position Plus Sequential Scan
Find the First Key at or Above Low
This costs logarithmic tree descent plus leaf search.
Emit Until High Is Passed
The rest is sequential leaf traversal. Complexity is naturally described as positioning cost plus output/scan cost, rather than one opaque O(log n) statement.
Range Complexity Reflects Output Size
Reporting k Entries Must Cost at Least O(k)
The algorithm cannot return k records without touching them.
B+ Trees Add Only Small Navigation Overhead
The attractive bound is roughly logarithmic positioning plus work proportional to visited leaf entries/pages. The structure avoids repeated logarithmic searches for each neighbour.
Prefix Ranges on Composite Keys
A Composite Index Orders Tuples Lexicographically
All entries sharing a chosen prefix occupy a contiguous leaf span.
Find the Prefix Start, Then Scan
For an index on (surname,given_name,id), a query fixing surname can position at the first tuple with that surname and continue until the surname changes.
Duplicate Keys Form Contiguous Runs
Equal User Keys Cluster Together in the Physical Order
A hidden tie-breaker can distinguish individual entries.
Range and Equality Scans Can Traverse the Run
The tree locates the first relevant duplicate, then the scanner walks until the user-key component changes. This is more natural than storing all duplicates in an unordered bucket.
Secondary Index Leaves Usually Point Elsewhere
The Index Entry Stores a Locator
That can be a tuple ID, row ID or primary key depending on engine design.
Fetching the Base Row Can Add Random I/O
An index range may be sequential at the leaf layer while table-row access is scattered. Query planners consider this when deciding whether an index scan is cheaper than a table scan.
Clustered Index Leaves Can Carry the Rows Themselves
Physical Record Order Follows the Leaf Key Order
Range scans can access records with strong locality.
The Trade-Off Is Wider Leaf Entries
Wider leaves reduce fan-out and can increase page count. The exact clustered/secondary distinction is engine-specific, but leaf payload width always affects B+ tree geometry.
Index-Only Scans Avoid Base-Table Fetches
If Every Needed Column Is Available in the Index
The executor may answer directly from leaf entries, subject to database visibility rules.
Included Columns Increase Leaf Width
Designers trade more covered queries against fewer entries per leaf. B+ tree leaf layout therefore affects both search geometry and query execution strategy.
Leaf Fill Factor Matters
High Fill Maximises Density
Static indexes use fewer pages.
Free Space Absorbs Future Inserts
Update-heavy indexes often leave headroom. PostgreSQL documents a configurable B-tree fillfactor and explains the trade between compact size and avoiding immediate splits.
Leaf Splits Insert a New Horizontal Neighbour
Entries Are Divided Into Left and Right Leaves
Both remain sorted.
The New Right Leaf Is Spliced Into the Chain
Old next becomes new next; old leaf points to new leaf; backward links are repaired if present. The parent receives a new boundary route as a separate vertical update.
A Leaf Split Has Two Independent Correctness Dimensions
Vertical Correctness
The parent separator must route future lookups to the proper left or right leaf.
Horizontal Correctness
Next/previous links must preserve the global leaf order. Point searches can pass while range scans fail if only the vertical dimension is repaired.
Leaf Merges Remove a Horizontal Page
Two Adjacent Leaves Combine Entries
Sorted order is preserved.
The Retired Leaf Must Be Spliced Out
Neighbours point around it, and the parent removes the corresponding child route. Page reclamation is safe only after no reader can follow stale links.
Leaf Borrowing Changes Boundaries
A Sibling Donates One or More Edge Entries
This repairs occupancy without merging pages.
The Parent Separator May Need Updating
If the smallest key in the right page or another represented boundary changes, vertical routing metadata must follow the new leaf contents.
Exact Point Search Can Miss Leaf-Link Bugs
Tree Routing Does Not Use Next Links for Ordinary Equality
A broken chain can remain hidden.
Dedicated Range Tests Are Essential
Scan across every page boundary after splits, merges and redistributions. Validate the entire ordered chain, not only independent leaves.
Forward Leaf-Chain Validation
Start at the Leftmost Leaf
Follow next pointers until the end.
Assert Strict Global Order Under the Full Tie-Broken Key
Every page boundary must continue the ordering, every leaf should appear exactly once and total entry count should match the logical reference set.
Reverse Leaf-Chain Validation
Start at the Rightmost Leaf if Previous Links Exist
Walk backward.
Check Symmetry
For adjacent leaves A and B, A.next should be B and B.prev should be A. Bidirectional inconsistency is a common split/merge bookkeeping failure.
Leaf Compression Can Reduce Page Count
Prefix Compression Exploits Nearby Key Similarity
Adjacent sorted keys often share prefixes.
More Entries Fit in a Page
Range scans then touch fewer pages. The trade is extra decoding work and more complex insertion or redistribution.
Posting Lists Can Compress Duplicates
Many Equal Keys Can Share One Logical Key Representation
A leaf entry can store multiple row identifiers.
This Changes Leaf Density Without Changing Order
PostgreSQL, for example, documents B-tree deduplication and posting-list tuples. Production leaf formats can be richer than one key–one row pointer.
Leaf Page Fragmentation Matters
Variable-Length Deletes Leave Holes
Logical free space may be scattered.
Compaction Restores Usable Contiguous Space
A slotted page can move physical record bodies while keeping logical slot order. Leaf correctness is about ordered entries, not fixed byte addresses.
Range Scans Benefit From Prefetch
Next Leaf Is Known Before Current Leaf Is Exhausted
The engine can request it asynchronously.
Sequential Work Hides Storage Latency
Read-ahead is especially effective for long ranges because the access pattern is predictable. Linked leaves expose future page demand directly.
Not Every Leaf Page Is Physically Adjacent on Disk
Logical Next Does Not Imply Consecutive Block Number
Splits can allocate pages elsewhere.
The Link Still Preserves Ordered Navigation
Filesystem and storage layout can optimise physical locality separately through allocation policy or rebuilds. Logical leaf order survives fragmentation.
Range Scan Selectivity Determines Whether the Index Helps
Small Ranges Benefit Strongly
Only a few leaves and row lookups are needed.
Very Large Ranges Can Resemble a Full Scan
Query planners may choose a sequential table scan if following the index and fetching many scattered rows costs more. A B+ tree enables the access path; the optimizer decides whether to use it.
MVCC Visibility Is Not the Same as Leaf Membership
A Leaf Entry Can Exist but Be Invisible to One Transaction
Database versioning rules decide which row versions count.
The Scanner Applies Visibility Semantics Above the Index
The B+ tree preserves order among index entries. Transaction machinery decides which results are returned.
Deletions May Be Logical Before Physical
A Database Can Mark Entries Dead or Delay Cleanup
Immediate page merge is not always desirable.
Background Maintenance Can Reclaim Space Later
This reduces foreground write cost and coordinates with snapshots. The abstract leaf-delete operation can therefore be split into logical invisibility and eventual physical removal.
Concurrent Range Scans Need Stable Navigation
A Leaf Can Split While the Scanner Is Reading It
Some entries move to a new right sibling.
High Keys, Sibling Links and Latches/Versions Help
The scanner must avoid missing moved entries or visiting them twice under its isolation semantics. Production concurrency protocols define how leaf-link traversal interacts with structural change.
Concurrent Merge Is Even More Delicate
A Page Can Be Retired From the Chain
Readers might still hold a reference to it.
Reclamation Must Be Delayed or Coordinated
Epochs, latches, reference counts or database-specific protocols ensure a reader does not follow memory or page identifiers that have already been reused.
Crash Recovery Must Preserve the Chain
A Leaf Split Updates Multiple Pointers
Old leaf, new leaf, neighbour and parent can all be involved.
Logging or Copy-on-Write Makes the Change Recoverable
After a crash, the tree must not expose an orphan leaf, a broken next link or a parent route to an uninitialised page. Horizontal invariants deserve recovery coverage.
Copy-on-Write and Leaf Links
Versioned Pages Complicate Horizontal Pointers
A new leaf version may not safely link into old-version neighbours.
Persistent Designs Need Version-Coherent Traversal
Some systems rebuild neighbouring links, use indirection or derive iteration differently. Snapshot consistency places additional constraints on the simple linked-leaf idea.
Reverse Scans Need Correct Boundary Semantics
Find the Last Key At or Below High
This is the mirror of lower-bound positioning.
Then Walk Left
Within each leaf scan entries backward; follow previous links when the beginning is reached. Duplicate and composite-key ordering rules must be identical to forward scans.
Pagination and Seek Methods
Keyset Pagination Uses Ordered Continuation
A client can request entries after the last seen key rather than using large offsets.
B+ Tree Order Supports Efficient Continuation
The next query lower-bounds the continuation key and resumes near the correct leaf. Stable tie-breakers are essential when user keys are not unique.
Nearest-Value Queries Use Leaf Neighbours
Predecessor and Successor Live Nearby
After lower-bound search, the preceding leaf entry and current entry often provide the nearest candidates.
Leaf Links Cross Page Boundaries
If the predecessor lies before the first slot, follow prev; if successor lies after the last, follow next. Ordered horizontal structure makes neighbour queries natural.
A Common Failure: Leaf Entries Not Globally Sorted Across Pages
Symptom
Each leaf passes its local sort check but a later leaf starts below the previous leaf’s maximum.
Repair
Validate boundary order between every adjacent pair and compare the full leaf chain against a globally sorted reference.
A Common Failure: Next Link Skips a New Split Page
Symptom
Exact search finds entries in the new page, but forward range scans jump over them.
Repair
Update the old leaf’s next pointer and the new leaf’s next pointer as part of one split transformation. Repair neighbour.prev when bidirectional.
A Common Failure: Merge Leaves a Dangling Link
Symptom
A scan reaches a retired page after deletion.
Repair
Splice the removed page out before reuse, and coordinate concurrent readers. Horizontal removal is part of merge correctness.
A Common Failure: Duplicate Tie-Breaker Is Missing
Symptom
Pagination skips or repeats equal user-key entries.
Repair
Define a total physical order, such as (user_key,row_id), and use it consistently in leaf sorting, separators and continuation tokens.
A Common Failure: Range Scan Restarts at Root for Every Leaf
Symptom
A range of k pages performs k logarithmic descents.
Repair
Use leaf links. The whole purpose of the B+ leaf layer is to turn continuation into horizontal traversal.
Testing Range Semantics
Empty, One-Entry and Multi-Leaf Ranges
Test inclusive/exclusive endpoints and keys absent at either boundary.
Duplicate and Composite Ranges
Test equal-key runs, prefix ranges and ranges whose endpoints fall exactly on page separators. Compare returned sequence with a trusted sorted reference.
Range-Scan Observability
Pages Visited per Returned Row
High ratios can indicate sparse leaves or poor clustering.
Prefetch Hit Rate and Base-Table Fetch Locality
These metrics reveal whether the leaf chain’s ordered access is translating into physical efficiency for the actual query workload.
Rainbolt and CivDJ Views
Rainbolt View: Leaves Are a Continuous Street of Records
The tree gets you to the correct block. After that, you walk house by house in order instead of returning to the city map after each address.
CivDJ View: Leaves Are the Interface Between Index and Data
The query engine sees ordered tuples, the buffer manager sees pages, the storage engine sees compression and free space, and the transaction manager sees visibility. The linked leaf layer connects them all.
How to Teach Leaf Scans
Draw the Internal Tree Above a Row of Linked Leaves
Then compare exact search with range search.
Make One Query Cross a Page Boundary
Students see immediately why the next-leaf pointer matters. A tree without linked leaves can still search; a B+ tree’s leaf chain makes ordered scanning a first-class operation.
Frequently Asked Questions
Do Leaves Store the Same Separators as Internal Pages?
They store full searchable entries. Some of their boundary keys can be copied upward as routing separators.
Can a Range Scan Start Without Searching the Root?
If the caller already has a valid leaf cursor or continuation position under the system’s rules, yes. Otherwise the tree is used to locate the starting leaf.
More Frequently Asked Questions
Why Are Leaf Links Better Than Repeated Successor Search Through Parents?
They turn page-to-page continuation into O(1) local navigation and improve prefetchability.
Do Leaf Links Guarantee Physical Sequential Disk Layout?
No. They guarantee logical order. Physical allocation can be fragmented, though systems may try to improve locality.
The Pillar Boundary and Sources
What This Article Owns
This pillar owns B+ tree leaf entries, leaf links, lower/upper-bound positioning, forward/reverse range scans, duplicate runs, record locators, leaf-level storage and horizontal validation.
Sources and Further Reading
For B+ tree leaf-page structure, see CMU 15-445/645: B+Tree Project. For linked page levels and leaf tuples in a production B-tree-family index, see PostgreSQL Documentation: B-Tree Indexes.
Final Synthesis: The Leaf Chain Turns Ordered Search Into Ordered Traversal
The Mechanism
Route once to the correct bottom page, locate the first qualifying key, then walk linked leaves in sorted order.
Why It Matters
Exact lookup remains logarithmic, but ranges avoid repeated tree descent. That combination—fast positioning plus sequential continuation—is the defining strength of the B+ tree leaf layer.
Worked Multi-Leaf Range Scan With Duplicates
Locate the First Physical Entry in the Duplicate Run
Suppose many rows share user key 500 and the physical order is (500,row_id). A query asking for all key=500 should not stop at the first matching row it happens to find. It lower-bounds the tuple range for user key 500, reaches the first physical occurrence, and then scans forward through every leaf entry whose user-key component remains 500. The hidden tie-breaker preserves one total physical order while the query groups entries by the visible component.
The Duplicate Run Can Cross Several Leaves
If hundreds or thousands of rows share the same value, the run may span multiple pages. Leaf links let the scan continue without repeated root searches. The upper stopping condition is the first key whose visible component differs. This example shows why duplicate handling and range scanning are naturally aligned in a B+ tree: equal values are stored contiguously under a total tie-broken order.
Worked Composite Prefix Scan
Index (country, city, id)
To find all Singapore rows, construct a lower key representing the smallest tuple beginning with country=’SG’ and an upper boundary representing the first tuple beyond that prefix. The tree routes to the starting leaf using the full tuple comparator. The scanner then walks leaves until country changes. Internal pages never need to understand the semantic idea of “country prefix”; they only implement total tuple ordering.
The Same Pattern Handles Prefix Plus Range
A query for country=’SG’ and city between ‘Bedok’ and ‘Yishun’ translates into tuple boundaries over the same lexicographic order. One lower-bound descent positions the scan. This is why leftmost index prefixes are so important in relational query planning: the corresponding predicates map cleanly to contiguous B+ tree leaf intervals.
Leaf Entries and Heap Fetch Locality
Ordered Index Access Does Not Guarantee Ordered Table Access
A secondary index can produce row identifiers in perfect key order while the referenced table rows are scattered across storage. The scan then alternates cheap sequential leaf reads with potentially random table fetches. This distinction explains why a range index can be structurally efficient yet still lose to a table scan for low-selectivity queries.
Clustering Changes the Trade
If table rows are physically organised near the same key order, row fetches have better locality. Clustered indexes or periodic table reorganisation can therefore amplify the value of the B+ leaf sequence. The tree’s ordered output is only one half of end-to-end access locality.
Index-Only Scans and Leaf Payload Design
Including More Columns Can Eliminate Heap Visits
If a query needs key, date and status and all are present in the leaf entry, the executor may avoid fetching the base row depending on engine visibility rules. This can turn a scattered secondary-index workload into a pure leaf-page scan.
Wider Leaves Reduce Density
Every included column consumes page space. Fewer leaf entries fit per page, splits occur sooner and long ranges touch more pages. Covering-index design is therefore a direct B+ tree geometry trade-off: wider entries buy query coverage while reducing leaf fan-out and cache density.
Leaf Compression and Scan Throughput
Sorted Neighbours Often Share Prefixes
Strings such as URLs, paths, names or composite keys can have substantial common prefixes within one leaf. Prefix compression can store shared context once or encode differences compactly. More entries fit per page, so a range query reads fewer pages for the same number of logical rows.
Compression Changes the CPU/I/O Balance
The engine must decode entries for comparison and output. On storage-bound workloads, reduced page traffic usually justifies extra CPU. On memory-resident workloads with very cheap keys, decoding overhead can matter more. Leaf format optimisation depends on the actual hardware and query mix.
Posting Lists and Duplicate Compression
One Key Can Refer to Many Rows
Instead of repeating the same key for every duplicate row, a leaf representation can keep one key with a compact list of row identifiers. PostgreSQL documents posting-list tuples as one implementation technique for B-tree deduplication. The B+ tree’s logical order is unchanged: all rows for that key still occupy one contiguous logical position.
Updates Must Manage the Posting Structure
Adding or removing one duplicate may modify a posting list without changing page separators. If the list grows too large, the engine may split or represent it differently. Duplicate compression is therefore a leaf-local optimisation layered on top of the same ordered-key semantics.
Forward and Reverse Scan Cursors
A Cursor Needs Page and Slot State
After positioning, a scan cursor typically remembers the current leaf page and entry offset. Advancing increments the slot until the page ends, then follows the next link and starts at the first slot of the new page. Reverse traversal mirrors this with previous links and decreasing offsets.
Concurrent Changes Can Invalidate Simple Cursors
A split can move later entries into a new sibling; a merge can retire the current neighbour. Database implementations use latches, stable page identifiers, restart logic, high keys or transaction-aware cursors so a scan can continue without silently skipping or duplicating rows beyond its isolation semantics.
Keyset Pagination Is a Leaf-Order Application
Resume After the Last Seen Composite Key
Instead of OFFSET 100000, a client can request rows greater than the last returned (sort_key,id). The B+ tree lower-bounds that continuation tuple and resumes near the exact leaf position. Work depends on page navigation and requested result count rather than on discarding a huge prefix of earlier rows.
Stable Tie-Breaking Prevents Repeats
If sort_key is not unique, the pagination cursor must include a unique or total-order tie-breaker. Otherwise equal keys can be skipped or repeated between pages. The physical ordering rule used by the leaf layer should match the continuation token semantics.
Leaf Splits Under Active Range Scans
Entries Can Move Right While a Scanner Holds the Old Leaf
A concurrency-safe implementation must define whether the scanner follows the newly installed right sibling, restarts from a boundary or relies on page high keys. The final linked-leaf structure is easy; the challenge is making intermediate states navigable without omissions or duplicate visibility.
Isolation Semantics Decide What the Scan Should See
A snapshot transaction may intentionally ignore rows inserted after its snapshot even if they appear on a newly split leaf. A read-committed scan may see different behaviour. The B+ tree supplies ordered physical navigation; MVCC or locking determines logical visibility.
Leaf Merges Under Active Scans
Retiring a Page Requires Safe Lifetime Management
A scanner can still reference the leaf even after the tree has removed its parent route. Reusing the page immediately for unrelated contents can corrupt the scan. Engines coordinate latches, epochs, pins or buffer references so logical unlinking precedes safe physical reuse.
The Chain Must Have a Continuous Successor Path
Whether the scanner is on the surviving leaf or the retired one, the concurrency protocol must provide a way to continue under its visibility rules. This is another reason linked-leaf maintenance belongs to correctness, not merely optimisation.
Leaf-Level Crash Recovery Checks
A Page Can Be Vertically Reachable but Horizontally Missing
After a failed split recovery, parent separators might correctly reach a new leaf while the old leaf’s next pointer still skips it. Exact point tests pass; range scans fail. Recovery validation should therefore traverse both the tree and the leaf chain and compare their leaf sets.
The Chain Can Also Contain an Orphan Not Reachable From the Root
A horizontally linked page without a vertical parent route can appear in scans but not exact lookups. This split-brain index is especially dangerous. A full audit requires the same leaf population in both navigation dimensions.
Leaf Fragmentation and Rebuild Decisions
Legal Occupancy Can Still Be Physically Inefficient
After many updates, leaves can remain above minimum occupancy while average fill falls and physical allocation becomes scattered. Long range scans then touch more pages and experience worse locality. Correctness alone does not guarantee efficient scan geometry.
Rebuild Packs the Ordered Frontier Again
Bulk reconstruction can rewrite dense leaf pages, choose a new fill factor and rebuild internal levels from fresh boundaries. This may cost a large one-time operation but improve subsequent range and cache behaviour substantially.
Leaf Scan Postcondition Checklist
Ordering Checks
Each leaf sorted; adjacent leaf boundary ordered; duplicate tie-breakers total and stable; lower/upper-bound positioning correct; forward and reverse scans mirror each other; composite-prefix ranges end exactly when the comparator leaves the requested interval.
Structural Checks
Every leaf in the vertical tree appears exactly once in the horizontal chain; no extra chain-only leaf exists; next/prev links reciprocal where promised; total leaf entry count matches logical index contents; retired pages unreachable; split and merge boundaries reflected in parent routing.
Leaf Review: Logical Order and Physical Locality Are Different
The leaf chain guarantees that keys can be traversed in logical sort order. It does not guarantee that adjacent leaves occupy adjacent disk blocks or memory frames. Splits, merges and allocator history can scatter physically neighbouring keys. Rebuilds, extent-aware allocation and clustering policies can improve physical locality without changing the logical next/previous sequence.
This distinction matters when explaining range-scan performance. The algorithmic path is sequential through leaf links, but storage latency still depends on where those pages reside and whether the buffer manager can prefetch them effectively.
Leaf Review: Range Correctness Includes Endpoint Semantics
A BETWEEN-style scan, an exclusive upper bound, a prefix scan and a keyset-pagination continuation all use slightly different stop conditions. The B+ tree supplies ordered leaf navigation; the query layer defines whether equality at each boundary is included. Bugs often appear when the lower-bound search uses one equality convention while the scan stop test uses another.
Directed tests should therefore cover absent endpoints, endpoints equal to the first or last key of a leaf, duplicate runs that cross leaves and composite-key boundaries. Correct scanning is not only “follow next”; it is “follow next under precisely defined interval semantics.”
Leaf Review: The Chain Is a Second Index of the Same Data
Vertically, every leaf is discovered through separator routing. Horizontally, the same leaves appear as one ordered linked sequence. These two structures should enumerate exactly the same leaf set. Comparing them is a powerful integrity test: tree-only leaves suggest broken chain links, while chain-only leaves suggest orphaned or stale pages.
That dual representation is also why B+ tree maintenance is delicate. Every leaf split or merge must update both views so they continue to describe one identical ordered frontier.
Leaf Scan Review: Ordered Continuation Is the Real Asset
The leaf chain is valuable because it preserves continuation. Once a query is positioned, the next qualifying key should be obtainable by local movement rather than by a new global search. That principle powers range scans, nearest-neighbour traversal, duplicate runs and keyset pagination. The exact record representation can vary widely, but ordered continuation is the durable abstraction.
A strong leaf implementation therefore treats next/previous navigation, duplicate tie-breakers and endpoint semantics as part of the public behaviour of the index layer. Exact lookup is only one consumer. The leaf frontier exists to support sustained ordered access after the first search decision has already been paid for.
Leaf Layer Closing Note
The leaf layer is where the B+ tree stops being only a search tree and becomes an ordered access path. Exact lookup, duplicates, predecessor/successor, pagination and long ranges all converge on the same mechanism: find the correct bottom page, then preserve continuation through a stable total order. This is why leaf-chain correctness deserves the same status as parent-child routing correctness.
When evaluating a real index, separate three costs: reaching the first leaf, scanning leaf entries and fetching any referenced base records. The B+ tree directly optimises the first two. Clustering, covering columns, compression, prefetch and buffer caching determine how well those structural advantages translate into end-to-end query latency.
For range-oriented workloads, also measure how many leaf pages a typical query crosses and how often the scan must leave the index to fetch base rows. These two metrics distinguish leaf-chain efficiency from table-access cost and help explain why the same B+ tree can perform brilliantly for one query shape and poorly for another.
A final scan invariant is continuity: the last logical key of one leaf and the first logical key of its successor must form the same ordered sequence that a trusted global sort would produce, including duplicate tie-breakers and composite-key ordering.
Continue the B+ Tree Series
How B+ Trees Work · How B+ Tree Internal Nodes Work · How X Works Hub