How to Learn B+ Tree Algorithms: Pages, Branching Factor, Splits, Merges and Database Indexes

Wait, What?

A search tree can become faster by becoming much wider, because on real storage the expensive step is often not comparison—it is fetching another page.

B+ trees are one of the clearest examples of the distance between a classroom algorithm and a professional system. A binary search tree asks how many comparisons are needed. A B+ tree asks a second question: how many storage pages must be touched? That change in cost model explains why databases and file systems favour wide, shallow trees whose nodes are designed around pages rather than individual machine words.

Quick Answer

Learn the topic through the route sorted records → binary-search-tree comparison → page cost → high branching factor → internal versus leaf pages → point search → ordered range scan → insertion → split propagation → deletion → redistribution and merge → occupancy invariant → concurrency and recovery → workload-aware index choice. Draw pages and trace one search, split and merge by hand before writing implementation code.

1. Start With the Cost Model

Suppose a database contains millions of sorted keys. A balanced binary search tree gives logarithmic search depth, but a node that stores only one key wastes the fact that a disk or SSD normally transfers data in blocks or pages. If one page can hold hundreds of separator keys and child pointers, one read can eliminate far more of the search space.

This is the first professional lesson: Big-O is not the whole cost model. The number of page transfers, cache misses, pointer traversals and writes can matter as much as the number of comparisons. The companion cache-efficient algorithms guide develops this broader idea.

2. Compare a B+ Tree With a Binary Search Tree

A binary search tree usually has at most two children per node. A B+ tree may have tens, hundreds or more. This high branching factor makes the tree shallow. The price is that each node is more complex: it stores several keys, several pointers, occupancy constraints and carefully defined split and merge rules.

Do not confuse a B+ tree with the AVL and red-black trees covered in How to Learn Balanced Search Trees. Those structures rebalance mainly through rotations. B+ trees maintain balance by splitting, redistributing and merging whole multi-key pages.

3. Understand the Two Page Roles

Internal pages: store separator keys and child pointers that route the search downward.
Leaf pages: store the indexed entries or references to records.

In the common B+ tree design, all searchable data entries are at the leaves, and leaves are linked in key order. That linked-leaf property makes range scans natural: find the first matching leaf, then walk across neighbouring leaves.

PostgreSQL’s current B-tree documentation describes a multi-level page structure in which internal pages direct traversal and leaf pages hold tuples pointing to table rows. See PostgreSQL: B-Tree Indexes. SQLite’s file-format documentation likewise exposes how table and index B-trees are organised into root, interior and leaf pages. See SQLite Database File Format.

4. Trace Point Search Before Coding

Take a tiny tree with one root and three leaf pages. Give the root separator keys such as 20 and 50. Ask where keys 7, 32 and 81 should go. At each internal page, the learner should explain which interval each child pointer represents.

What key interval does this pointer cover?
Why can all other children be rejected?
Where is the final record located?
How many pages were touched?

If the learner can only recite “binary search inside each node” but cannot state the routing intervals, the invariant is not yet secure.

5. Range Search Reveals Why Leaves Are Linked

To answer “all keys from 1200 through 1400,” first search for 1200. Once the starting leaf is found, a linked sequence of leaf pages can be scanned until the upper bound is passed. The internal routing structure is used once; the ordered leaf chain then supports sequential access.

This is an important representation principle: a structure can support two different access patterns by giving different parts of the representation different jobs.

6. Insertion Is Easy Until a Page Is Full

If the target leaf has space, insert the key in sorted order. The interesting case is overflow. A full page is split into two pages, the entries are redistributed, and a separator is inserted into the parent so searches can distinguish the two children.

The split may propagate upward. If the parent is also full, it must split. In the extreme case, the root splits and a new root is created, increasing the tree height by one.

7. Draw Split Propagation as a State Transition

Do not learn insertion as a wall of code. Draw the before-state and after-state for three cases:

insert into a non-full leaf;
insert into a full leaf whose parent has room;
insert into a full leaf whose parent also overflows.

For every state transition, verify three properties: keys remain ordered, every child remains reachable through the correct separator interval, and all leaves stay at the same depth.

8. Deletion Is the Mirror Problem—but Not a Simple Reverse

Deleting an entry can leave a page below its permitted occupancy. A typical repair first asks whether a sibling can redistribute an entry. If not, pages may merge and a separator is removed from the parent. That removal can make the parent underfull, so repair may propagate upward.

The root is a special case. If it is left with one child after merging, the tree may shrink in height by promoting that child to the new root.

9. The Occupancy Invariant Is the Centre of Correctness

A B+ tree is not merely “sorted.” Each non-root page must satisfy allowed occupancy rules. Those rules guarantee a minimum branching factor, which in turn keeps height logarithmic in the number of indexed entries.

A correctness argument therefore needs more than key ordering. It must show that insertion and deletion preserve:

sorted keys within pages;
correct separator ranges between parent and children;
all leaves at the same depth;
legal page occupancy, except temporary local states while repair is in progress;
valid linked-leaf ordering for scans.

The proof habits in How to Learn Algorithm Correctness Proofs transfer directly here.

10. Branching Factor Explains the Shallow Height

If each internal page has roughly hundreds of children, the number of reachable leaves grows very quickly with each level. That is why large indexes often require only a small number of page traversals from root to leaf. The exact fan-out depends on page size, key size, pointer size and metadata overhead.

Professional analysis should therefore ask not only “What is O(log n)?” but “What is the logarithm’s effective base, and how many expensive storage accesses does that height imply?”

11. A Database B+ Tree Is More Than the Textbook Structure

Real implementations must deal with concurrency, latching, crash recovery, page allocation, prefix compression, duplicate keys, variable-length records, background maintenance and hardware behaviour. Carnegie Mellon’s 15-445/645 database course makes this transition explicit by asking students to implement B+ tree pages, search, insertion, deletion, iteration and concurrency control. See CMU 15-445/645 B+ Tree Project.

12. Concurrency Changes the Meaning of “Correct”

In a single-threaded drawing, a split happens atomically. In a database, another operation may be reading or modifying nearby pages at the same time. Professional implementations therefore need a protocol that controls who may inspect or mutate a page while structural changes occur.

The learning point is not to memorise a specific latch-coupling recipe. It is to recognise that once operations overlap in time, the invariant must hold from the perspective of concurrent observers as well as after the final state is reached.

13. B+ Tree, Hash Index or Something Else?

B+ tree: strong general choice for ordered equality and range queries.
Hash index: can be attractive for equality-focused workloads but does not naturally preserve order for range scans.
Specialised indexes: may be better for text, spatial, multidimensional or append-heavy workloads.

PostgreSQL exposes several index families precisely because no single algorithm dominates every query shape. Its current index-type documentation lists B-tree, Hash, GiST, SP-GiST, GIN and BRIN as distinct choices. See PostgreSQL: Index Types.

14. Common Learning Failure States

Treating B+ trees as binary search trees with larger nodes.
Confusing where records live in B-trees versus B+ trees.
Forgetting to update parent separators after a split or redistribution.
Merging pages without repairing the parent.
Allowing a non-root page to remain illegally underfull.
Losing leaf-link order during split or merge.
Counting comparisons while ignoring page transfers.
Assuming textbook single-threaded code can be used unchanged in a concurrent database.

15. A Scaffold-Fade Learning Ladder

Level 1: search a sorted list and a balanced binary tree.
Level 2: compare a tall binary tree with a shallow high-fan-out tree under a page-read cost model.
Level 3: route searches through a hand-drawn B+ tree.
Level 4: perform leaf insertion without overflow.
Level 5: split a leaf and repair the parent.
Level 6: trace a cascading split to a new root.
Level 7: repair underflow by redistribution or merge.
Level 8: implement search, update and range iteration against a page abstraction.
Level 9: reason about concurrency, recovery and realistic workload choice.

For advanced programming topics, 2025 ITiCSE research on faded Parsons problems found value in preserving scaffolding while reintroducing generative work. See Caraco, Lojo and Fox (2025). A B+ tree exercise can fade progressively from labelled page diagrams to missing separator logic, then split logic, then full implementation.

16. Read and Trace Before Writing

The Raspberry Pi Foundation’s computing pedagogy guidance recommends reading, tracing and explaining code before expecting learners to write it, and highlights structured approaches such as PRIMM. See Computing pedagogy at the Raspberry Pi Foundation. For B+ trees, tracing page states is especially valuable because many bugs are structural rather than syntactic.

17. Immediate, Delayed and Transfer Checks

Immediate: route five keys through a given tree.
Structural: label every separator interval.
Insertion: predict the exact pages changed by one overflowing insert.
Deletion: decide whether redistribution or merge is needed.
Delayed: re-derive split and merge rules without notes.
Transfer: choose between a B+ tree, hash index and direct scan for several workloads.

18. AI Assistance Boundary

AI can generate small page layouts, produce insertion sequences that trigger particular split cases, and check a learner’s hand trace. The learner should still be able to state the page invariant, explain every separator, predict structural repair and justify the index choice from the workload.

Professional Direction

Professional study extends into B-link trees, latch-free and optimistic techniques, write-optimised tree variants, prefix compression, bulk loading, buffer-pool interaction, recovery logging, concurrent iterators and cloud-storage-aware indexes. The durable idea remains simple: choose a node size that matches the storage hierarchy, keep the tree shallow, preserve occupancy and ordering invariants, and measure the implementation under the workload it will actually serve.

Algorithm-learning rule: do not ask only “How many comparisons does search take?” Ask “What is the expensive unit of movement on this machine, and how should the data structure reshape itself around that unit?”