Skip to main content

B+Tree Explorer

OperationInsert 18 keys

  • Internal node: separators
  • Leaf: keys
  • Search path
  • Changed by this step
  • Leaf link
#1 leaf371215#5 leaf232933#4 leaf36424855#2 leaf61677081#6 leaf889499#323366188
Tree as text
Internal #3 [23, 36, 61, 88]
  Leaf #1 [3, 7, 12, 15] → #5
  Leaf #5 [23, 29, 33] → #4
  Leaf #4 [36, 42, 48, 55] → #2
  Leaf #2 [61, 67, 70, 81] → #6
  Leaf #6 [88, 94, 99]

step 2 of 5

Insert 18 keys: ran the remaining 56 steps at once. The tree now holds 18 keys at height 2.

Insert 18 keys: ran the remaining 56 steps at once. The tree now holds 18 keys at height 2.

How it works

Insert, delete and search keys in a B+ tree and watch every step: node splits, borrowing, merges and the linked leaf level that makes range scans fast. Change the order and replay.

What a B+ tree is

A B+ tree is a sorted, balanced search tree whose nodes hold many keys each. Every leaf sits at the same depth and holds the actual keys. Every internal node holds only separators: values that tell a search which child to follow. For a separator S, everything in the child on its left is smaller than S, and everything in the child on its right is greater than or equal to S.

The leaves are also linked to each other from left to right. Once a search reaches a leaf, the next keys in sorted order are one pointer away. The tree never needs to be climbed again to read them.

In the explorer, internal nodes are dark with violet separators, leaves are green with their keys, and the dashed green arrows are the leaf links. Every node carries a number (#7) so the log can refer to it. Hover over a node name in the log to find it in the tree.

How it differs from a B-tree

In a plain B-tree, every key lives in exactly one node, internal nodes included, and a search can stop as soon as it meets its key on the way down. A B+ tree moves all the keys to the leaves and keeps only copies in the internal nodes. That costs a little duplication, but it buys two things:

  • Internal nodes contain nothing but separators and child pointers, so more of them fit in a node and the tree fans out wider.
  • Every search ends at a leaf, and the leaves form a sorted linked list, which makes range queries cheap.

Rust’s BTreeMap, which the simple filesystem chapter of the OS series uses for its directories, is the other kind: a B-tree that keeps keys and values in its internal nodes too.

Why databases use them

Databases and filesystems read storage in pages, typically a few kilobytes at a time, and each page read is expensive compared to work in memory. A B+ tree makes one node exactly one page. With 8-byte keys and 8-byte page numbers, a 4 KiB internal page holds around 250 children. Three levels of that fan-out address more than 15 million leaf pages. Any key can therefore be found in a handful of page reads, and the top levels are usually already in the cache.

Range scans are the other reason. WHERE price BETWEEN 10 AND 20 descends once to the first matching leaf and then follows the leaf links, reading only the pages that hold results. Relational databases such as SQLite, PostgreSQL and MySQL’s InnoDB are built on B-tree variants, and the B+ tree layout, with entries in a linked leaf level, is the most common of them.

The explorer uses tiny nodes (3 to 8 keys) so that splits and merges happen after a few operations rather than a few hundred. The algorithms are the same.

Inserting: splits copy up, or move up

An insert descends to the leaf where the key belongs, choosing a child at each internal node by comparing the key with its separators. The log shows each comparison. The key is then added to the leaf in sorted order.

If the leaf now holds more keys than the order allows, it splits. The upper half moves to a new leaf to its right, and the new leaf’s first key is copied into the parent as a separator. The key stays in the leaf, because leaves are where keys live.

If that pushes the parent over the limit, the parent splits too. An internal split is different: the middle separator moves up to the grandparent and stays in neither half. When the root itself splits, a new root is created above it. That is the only way a B+ tree gets taller, and it is why every leaf is always at the same depth.

Deleting: borrow, or merge

A delete removes the key from its leaf. If the leaf still holds at least the minimum, the operation is done. In this explorer, a leaf must keep at least ⌈m / 2⌉ keys and an internal node at least ⌊m / 2⌋ separators, where m is the maximum. (Textbooks state these bounds in slightly different ways; these are the largest ones that keep every split and merge legal.) The separator above may still hold the deleted value. That’s fine: a separator only has to divide its children correctly, and it doesn’t have to be a key that still exists.

If the leaf falls below the minimum, it underflows, and there are two ways to repair it:

  • Borrow: if a neighbouring sibling has a key to spare, move one across and update the separator between them. For internal nodes this is a rotation: the parent’s separator comes down, and the sibling’s outermost separator goes up.
  • Merge: if neither sibling can spare a key, combine the node with a sibling and remove the separator between them from the parent. Merging internal nodes pulls that separator down into the merged node.

A merge removes a separator from the parent, so the parent can underflow in turn, and the repair can climb the tree. If the root loses its last separator, its only child becomes the new root and the tree gets one level shorter. On underflow chooses whether the explorer tries to borrow first, the usual choice, or merge whenever the result fits.

Order and height

The order controls the trade-off. A higher order means fewer, wider levels, but more keys to compare and move inside each node. Load the high fan-out scenario and compare it with the same keys at order 4. A B+ tree holding n keys with fan-out f has height of about logf(n), which is why real trees with fan-outs in the hundreds rarely need more than four levels.

Try it

  1. Search a built tree

    Step through the search for 67. At each internal node, which comparison picked the child? How many nodes did the search read in total?

  2. Grow to height 3

    Insert 1 to 17 in order and watch the leaf splits. Why does the left half of every split never change again? Then try the same keys as 17..1 in Insert several keys, and count how many keys the tree holds when it first reaches height 3.

  3. Delete that borrows

    Delete 10. The leaf underflows, but its sibling has three keys. Which key moves, and why does the separator in the root change?

  4. Merge that removes the root

    Delete 40. This time the sibling has nothing to spare. Follow the merge up to the root. Then switch Max keys per node to 4. The same operations replay. Does the root still disappear?

  5. Range scan along the leaves

    Scan 7 to 23. Count the leaves the scan reads, then compare that with the number of internal nodes it visits. Which part of the cost grows with the size of the range?

Each one opens the matching scenario in the explorer above.

Coming next: build one

This explorer models the data structure on its own. The upcoming Database From Scratch project builds a B+ tree on real fixed-size pages, with a pager underneath and a write-ahead log on the side. Subscribe there to hear when the first chapter is published.