How to Learn B+ Trees: Fanout, Leaf Links, Page Splits, Merges and Database Index Engineering

Wait, What?

A tree can search hundreds of millions of records while remaining only a few pages tall.

That is why B-trees and especially B+ tree-style indexes became foundational database structures. Their power does not come from being a “better binary search tree.” It comes from designing the tree around pages, high fanout and ordered storage so that one expensive page access narrows the search dramatically.

Quick Answer

Learn B+ trees in this order: page-oriented nodes → sorted separator keys → high fanout → root-to-leaf search → linked leaves → insertion → leaf split → parent propagation → root split → deletion/redistribution/merge → bulk loading → buffer-pool locality → concurrency and recovery. The professional mental model is not “a tree with many children.” It is “an ordered index whose nodes are storage pages.”

1. Begin With the Storage Cost Model

A binary search tree is organised around individual keys and pointers. A database index is often organised around pages containing many keys. If a page is several kilobytes and can hold hundreds of routing entries, one page read can choose among hundreds of subtrees.

With fanout f, a balanced tree of height h can route to roughly f^h leaf regions. High fanout therefore keeps height small even when the record count is enormous.

2. Know the B+ Tree Shape

In the common B+ tree teaching model:

Internal pages store separator keys and child pointers.
Leaf pages store keys plus record references or payload information.
All leaves appear at the same depth.
Leaves are usually linked in key order so that range scans continue from one leaf to the next.

Real database engines differ in exact page formats and terminology, but these ideas explain why B+ trees support both point lookup and ordered traversal efficiently.

3. Search Is a Page-by-Page Routing Process

Suppose an internal page contains separator keys [20, 50, 80]. Conceptually it routes a search into four key ranges. To find key 63, compare within the page, choose the child covering the interval between 50 and 80, then repeat until a leaf is reached.

page = root
while page is internal:
    slot = upper_bound(page.keys, key)
    page = page.children[slot]

search key inside leaf page

Notice the two levels of algorithmic thinking: search within a page, then move between pages.

4. High Fanout Changes the Complexity Conversation

The textbook complexity is often written O(log_f n), where f is fanout. In storage systems, however, the important practical measure is frequently the number of page accesses rather than the number of scalar comparisons.

A root and upper internal levels may remain hot in memory, leaving only one or two lower-level page accesses on many lookups. This is why a shallow, wide tree is valuable.

5. Leaf Links Make Range Queries Natural

A point lookup descends to one leaf. A range query such as “all keys from 4000 through 5000” descends once to the starting leaf, then walks leaf pages in sorted order until the range ends.

leaf = find_leaf(4000)
while leaf and first_key(leaf) <= 5000:
    emit entries in requested range
    leaf = leaf.next

This is an important contrast with a hash table: hashing is excellent for equality lookup, while a B+ tree preserves order and therefore supports range, prefix and ordered traversal jobs.

6. Insertion Starts Simple

To insert a key:

Find the correct leaf.
Insert the key in sorted position.
If the page still fits, stop.
If it overflows, split the page.

The split is where the structure becomes interesting.

7. A Leaf Split Creates a New Routing Boundary

Imagine a leaf that can hold four entries and currently contains:

[10, 20, 30, 40]

Insert 25 and the leaf overflows:

[10, 20, 25, 30, 40]

A simplified split might produce:

left  = [10, 20]
right = [25, 30, 40]

The parent must receive a new separator that routes future searches toward the new right page. Leaf links must also be repaired so ordered scans remain correct.

8. Splits Can Cascade Upward

Adding a new child pointer to the parent may overflow the parent. Then the parent splits too, potentially propagating toward the root. When the root splits, a new root is created and the tree becomes one level taller.

This explains a crucial invariant: the tree grows at the top, not by allowing one leaf to become deeper than another.

9. Learn the Difference Between Leaf and Internal Splits

In a teaching B+ tree, a leaf split usually preserves data entries at the leaf level and copies or derives a separator for the parent. An internal-page split redistributes routing entries and promotes an appropriate separator upward.

Exact rules vary by implementation. Do not memorise one classroom split recipe as though every database engine stores pages identically. Learn the invariant: after the split, routing must remain ordered, all records must remain reachable, and the tree must remain balanced.

10. Deletion Is More Than Removing a Key

Removing an entry may leave a page underfull. Classical B+ tree treatments then consider redistribution from a sibling or merging pages. A merge can remove a separator from the parent and may cascade upward.

Production databases complicate this picture because concurrent transactions, versioned records, background cleanup and page occupancy policies affect when physical consolidation is worthwhile. The logical deletion algorithm is only the beginning.

11. Fill Factor Is an Engineering Trade-Off

Packing every page completely maximises immediate space utilisation but leaves no room for nearby insertions. Leaving free space can reduce future page splits. Too much free space, however, increases tree size and memory/storage traffic.

The right occupancy strategy depends on workload. Sequential inserts, random inserts, updates and read-heavy workloads stress the index differently.

12. Sequential and Random Inserts Behave Differently

Ascending keys tend to concentrate insertion at the right edge of the tree. Random keys distribute insertions across many leaves. These patterns affect cache locality, split frequency, fragmentation and write behaviour.

When benchmarking an index, “insert one million rows” is incomplete. You must say how keys are distributed.

13. Bulk Loading Is Not Repeated Single-Row Insertion

If a large sorted data set is available at once, an index can often be built bottom-up: pack leaves efficiently, link them, then construct parent levels from separator keys. This avoids many incremental searches and splits.

This is a general algorithmic principle: when the whole input is known in advance, a batch construction algorithm may be much better than replaying an online update algorithm.

14. Page Layout Matters

A real page needs headers, slot information, keys, pointers, free-space management and perhaps overflow references. SQLite’s current file-format documentation, for example, specifies separate interior and leaf B-tree page types, page headers, cell-pointer arrays and overflow pages for large payloads.

The practical lesson is that an abstract node is not free. Metadata, variable-length keys and payloads all change effective fanout.

15. Record References Change the Meaning of the Leaf

A leaf entry might contain the full row, a row identifier, a primary key or some other record locator depending on the storage engine and whether the index is clustered or secondary. This can make two visually similar B-tree indexes have very different space and lookup costs.

Always ask: what exactly is stored at the leaf, and what additional lookup is required after the leaf is found?

16. Concurrency Turns Splits Into Protocols

With many threads or transactions, a page split cannot be treated as an isolated list operation. Searches may be traversing the structure while another operation changes page boundaries. Implementations therefore need latching or other concurrency-control protocols, careful ordering of structural changes, and recovery rules for crashes.

The classic B-link-tree idea, associated with Lehman and Yao, adds sibling-link/fence information that helps concurrent searches remain safe while structural changes occur. Modern database engines use sophisticated variants rather than a classroom global lock.

17. Recovery Is Part of a Durable Index

A page split may touch multiple pages: the original page, a new sibling and a parent. If the machine crashes halfway through, the database must recover to a structurally valid state. Write-ahead logging and recovery protocols therefore interact with index algorithms.

This is a key professional transition: a correct in-memory data structure is not automatically a correct persistent database index.

18. B+ Trees and LSM Trees Optimise Different Workloads

B+ trees support ordered point/range access with in-place page updates and balanced search. LSM-tree designs buffer writes and reorganise data through immutable sorted runs and compaction. Neither is universally superior.

The correct comparison includes read amplification, write amplification, space amplification, range-query behaviour, cache/buffer effects and workload distribution.

19. Current Production Systems Show the Abstraction Becoming Real

PostgreSQL’s current documentation describes its B-tree indexes as multi-level page structures whose levels are linked, with leaf pages holding tuples that point toward table rows and internal pages routing to lower levels. It also documents implementation concerns such as page splitting and deduplication. SQLite publishes its on-disk B-tree page format in unusual detail, making it a useful source for studying how page headers, cells and overflow storage turn a textbook tree into a file structure.

20. Common Failure States

Treating a B+ tree as merely a binary tree with more children.
Ignoring page size and assuming fanout is an abstract constant.
Forgetting that leaf links are what make long range scans efficient.
Using the same split rule for leaves and internal pages without checking the chosen model.
Forgetting to update parent separators after structural changes.
Assuming all database engines store complete records in secondary-index leaves.
Benchmarking only lookup count while ignoring page reads, buffer hits and writes.
Testing only sequential keys and generalising to random workloads.
Implementing concurrent page splits without a structural-consistency protocol.

21. Practice Ladder: Beginner to Professional

Beginner: search a hand-drawn B+ tree and explain every separator choice from root to leaf.
Foundation: insert a sequence of keys into a tiny order-4 tree and trace every split and parent update.
Intermediate: implement linked leaves and compare point queries with range scans.
Advanced: build a page-sized implementation using binary search within pages and measure height/fanout as key size changes.
Professional: model buffer-pool hits, page splits, fill factor, bulk loading, concurrency and recovery; compare behaviour against an LSM-tree workload.
Transfer: explain why a wider node can be faster even though searching within that node performs more comparisons.

Learning Hall Boundary

This article owns page-oriented balanced search-tree indexing, especially B+ tree search, leaf chaining, splits, merges and storage-engine implementation concerns. It does not replace the site’s general balanced-tree article, hash-table material, LSM-tree article, database join material or crash-recovery article. Those are neighbouring but distinct algorithmic jobs.

Evidence Boundary

Bayer and McCreight’s 1972 work on the organisation and maintenance of large ordered indexes is foundational to B-tree history; Douglas Comer’s 1979 Ubiquitous B-Tree survey documents the family’s early importance. For current production evidence, see the PostgreSQL current B-Tree documentation, including page structure, splitting and implementation details, and the SQLite database file-format specification, which documents interior/leaf page types, cell layouts and overflow storage. These sources also demonstrate why production index engineering goes beyond the simplified node diagrams used in introductory courses.

Professional rule: you understand B+ trees when you can reason simultaneously about key order, page occupancy, fanout, structural invariants and storage cost—and can explain what must stay correct when a page splits while other operations are still using the index.