B+ Tree

A B+ tree is a balanced search tree built from page-shaped nodes. Internal pages hold guide keys that choose a child; leaf pages hold the record keys in sorted order. Every leaf sits at the same depth, and neighboring leaves are linked. That combination gives point lookups a short root-to-leaf path and lets range queries descend once, then scan forward. In a database, one ordered index can therefore serve WHERE key = ?, BETWEEN, and a compatible ORDER BY scan.

The defining split rule is easy to blur: a leaf split copies its first right-hand key upward because that key is still a record in the leaf layer. An internal split pushes its middle guide upward, removing it from both split children. Watch which copy remains and the distinction becomes physical rather than mnemonic.

How a B+ Tree Is Organized

This lesson uses order to mean the maximum number of children in an internal page. An order-m page therefore has at most m - 1 keys when settled. With order 3, a page can hold two keys; a third key causes overflow and a split.

An internal page with guides [15, 30] has three child intervals:

• child 0 receives keys < 15;
• child 1 receives keys 15 <= key < 30; and
• child 2 receives keys >= 30.

The search uses the right-hand child when a key equals a guide. That matters because copied leaf separators also remain in the right leaf. Following equality rightward reaches the record copy.

Internal keys are routing evidence, not the record layer. The leaf chain is the complete sorted sequence of record keys. A guide may duplicate a record key, but counting both would count one logical record twice.

Insertion and the Two Split Rules

Insertion first descends to one leaf, finds the sorted slot, and writes the key there. If the page remains within its key limit, the operation is done. If it overflows, the repair depends on the page type.

For a leaf split, the keys are divided between the old leaf and a new right leaf. The new leaf first inherits the old next pointer; then the old leaf points to the new leaf. Writing the links in that order avoids losing the old successor. The first key in the right leaf is copied into the parent as a separator. It stays in the right leaf because range scans read records from leaves only.

For an internal split, the middle guide is removed from the overflowing page and pushed into its parent. Guides to its left remain in the old internal page; guides to its right move into a new internal page with the corresponding children. The pushed value belongs in neither child page. If the parent overflows, the same internal rule repeats upward. If no parent exists, a new root is created.

The tree grows only at the root, so every leaf remains at the same depth after a cascade.

B+ Tree Copy, Push, and Scan: Step by Step

The default run uses order 3 and performs:

insert 10, insert 20, insert 5, insert 15, insert 25, insert 30, search 25, range 9 27

1. Insert 10 and 20. The root is one leaf page, [10, 20].
2. Insert 5. The leaf becomes [5, 10, 20], which exceeds the two-key limit. It splits into [5, 10] and [20]. Separator 20 is copied into a new root.
3. Insert 15. It belongs in the left leaf, producing [5, 10, 15]. This is a non-rightmost split: the new leaf [15] inherits the old successor [20], then [5, 10] points to [15]. Separator 15 is copied into the root.
4. Insert 25. It routes right of guide 20 and joins the leaf as [20, 25] without a split.
5. Insert 30. The right leaf overflows as [20, 25, 30] and splits into [20, 25] and [30]. Copying 30 into the root makes the root guides [15, 20, 30], so the internal page also overflows. Its middle guide 20 is pushed into a new root. Unlike the earlier leaf copies, 20 now disappears from both split internal pages.

The final structure is:

                 [20]
              /        \
            [15]       [30]
           /   \       /   \
      [5,10]  [15] [20,25] [30]
          └────→────→────→

The leaf chain is [5, 10] -> [15] -> [20, 25] -> [30]. Every record is present exactly once in that chain, even though 15, 20, and 30 also appear as internal guides.

Point Search and Range Scan

search(25) follows one child per level. Guide 20 sends equality and larger keys to the right internal page. Guide 30 then selects its left child, leaf [20, 25]. A binary search inside that leaf finds 25. The trace visits three pages: root, internal page, leaf.

range(9, 27) also starts with one root-to-leaf descent. The lower bound lands in [5, 10] at key 10. The scan emits 10, follows next to emit 15, follows next again to emit 20 and 25, then follows one more link and stops when it sees 30 > 27. The result is [10, 15, 20, 25] after three leaf-link hops.

The critical behavior is not merely that leaves are sorted. Their links preserve the order across page boundaries, so the range tail does not restart at the root for each output.

When a B+ Tree Index Fits

Use an ordered tree index when a workload needs both exact-key lookup and ordered traversal. A hash index can be a better fit for an equality-only access path, but it does not provide this sorted leaf walk for range predicates or ordered output. Database products differ in how they name and implement their tree indexes, so engine-specific page formats remain outside this lesson's model.

B+ Tree Complexity and the +k Scan Cost

Let n be the number of records, m the order, and k the number of returned records.

The fanout base is meaningful: real page-sized nodes can hold many guides, so a tree covering many records may still have few levels. A page visit is a potential cache lookup or storage read, not automatically a disk I/O because a buffer pool may already hold that page. Following adjacent leaves gives the engine a sequential access pattern instead of repeating the root descent for every result. This animation uses orders 3 through 5 so every key and pointer remains visible; those tiny orders are for teaching, not a database recommendation.

B+ Tree Edge Cases

• Empty tree: the root is an empty leaf. Search misses, and a range returns no records.
• First split: a leaf root becomes two leaves under a new internal root.
• Duplicate key: the unique-key teaching model returns without changing any page or link. Production indexes may support duplicates through engine-specific record identifiers or payloads.
• Missing point key: descent still reaches exactly one candidate leaf; absence in that leaf ends the search.
• Empty range: the lower-bound position may already be above hi, producing an empty result without following another leaf.
• Range beyond the maximum: the scan follows links until the tail's null marker and returns every qualifying record. The Wide range preset uses range(1, 99) to return all eight stored keys and expose the full + k cost.
• Visualization limit: insert remains clickable at 12 records so the trace can explain that only the drawing is full. A B+ tree has no fixed 12-record capacity.

Common Mistakes in B+ Trees

• Pushing a leaf separator. Removing the separator from both leaves deletes a record from the leaf-only data layer.
• Copying an internal separator. Keeping the pushed middle guide in a child creates the wrong child intervals and blurs guide keys with records.
• Routing equality left. Copied separators describe the first key of the right subtree, so equality must choose that right-hand child.
• Breaking the leaf chain during a split. Set right.next to the old successor before changing leaf.next.
• Restarting every range step at the root. The output may remain ordered, but the repeated tree descent throws away the O(log_m n + k) scan behavior.
• Reading the diagram as a disk format. The page shapes teach fanout, balance, and linkage; they are not PostgreSQL or MySQL page bytes.

A Note on Simplification

This lesson is a textbook, in-memory B+ tree with unique integer keys, fixed order, immediate half splits, and no deletion. It omits buffer pools, physical page I/O, fill factors, prefix compression, duplicate record lists, concurrency latches, write-ahead logging, MVCC, recovery, and engine-specific page layouts. Real database indexes also store payloads or row identifiers and usually have far larger fanout. The model isolates the structural contract: internal guides route, leaves retain the records, split rules preserve balance, and leaf links make ordered scans sequential.