Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 79 ยท Storage and Indexing

B-Trees and B+ Trees

Understand B-trees and B+ trees: node structure, search, insert with splits, delete with merges, height and fan-out, and run a live Python B+ tree that prints its nodes.

A multilevel index is a great idea with one problem: a plain sorted index becomes expensive to keep correct when records are inserted and deleted. The B-tree family solves this. A B-tree is a balanced, wide, shallow search tree whose nodes are as large as a disk page. Every path from the root to a leaf has the same length, every node is at least half full, and the tree reorganizes itself locally with splits and merges.

The B+ tree is a variant that is used by practically every relational database for its indexes, including SQLite, PostgreSQL, MySQL/InnoDB, Oracle and SQL Server. In this lesson you will see how the nodes are structured, how search, insert and delete work, why the tree stays so short, and how a B+ tree differs from a B-tree. A live Python B+ tree prints its nodes after each insert so you can watch the splits happen.

Why trees for disks

One node, one page Reading a node costs one I/O.
Wide, not tall Hundreds of children per node.
Always balanced Every leaf is at the same depth.
1 / 2

Node structure

A B+ tree of order m (the maximum number of children) obeys these rules:

  • An internal node with k keys has k + 1 children. The keys are separators: everything in the subtree to the left of key K is smaller than K, everything to its right is greater than or equal to K.
  • A leaf node holds up to m - 1 keys, each with a pointer to the row (or the row itself in a clustered tree). Leaves are linked left to right.
  • Every node except the root is at least half full. The root has at least two children (unless it is a leaf).
  • All leaves are at the same level.

Inner nodes of a B+ tree store only keys, no row pointers. That leaves more room for keys, which means more children per node and a shorter tree. The leaves hold everything.

A classic B-tree, in contrast, stores a row pointer next to every key in every node, so a search can stop early in an inner node. That saves a few reads for some keys but makes inner nodes bigger and the leaves harder to scan in order.

Searching

Searching for key K starts at the root. In each node, find the first separator greater than K and follow the child pointer just before it. When you reach a leaf, scan it for K. The cost is the tree height, one page read per level.

A range query (BETWEEN 25 AND 60) does one descent to find the first matching key and then follows the leaf chain to the right until the keys exceed the upper bound. No other level is touched again. This is the big practical advantage of B+ trees over B-trees and over hashing.

Insertion and splits

To insert K, search for the leaf where it belongs and put it in place. If the leaf has room, you are done. If not, the leaf splits: the keys are divided into two leaves, and a separator is pushed up into the parent.

  • In a leaf split, the first key of the new right leaf is copied up (it must stay in the leaf as well, since leaves hold all keys).
  • In an internal split, the middle key is moved up (it does not stay below).
  • If the parent overflows, it splits in the same way, and so on up the tree. If the root splits, a new root is created and the tree grows by one level. That is the only way the height increases, which is why all leaves stay at the same depth.

The following TryIt is a complete B+ tree with at most 3 keys per node (tiny, so that splits happen quickly). It supports insert, point search and range search, and prints the tree level by level. Read the printed trees in order.

Python A B+ tree that prints its nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last picture is the one to study: after inserting 5, 15 and 25 the root [30 50 70] overflowed (it would hold four keys), so the middle key 50 moved up into a new root, and the tree grew from two to three levels. Notice that 30, 50 and 70 are still present in the leaves, because separators are copied up from leaves. The printed search result is (row, pages read), here 3 pages for a three-level tree whether or not the key exists. The range query touched only leaves after the first descent.

Deletion

Deleting K also starts with a search. Remove the key from its leaf. If the leaf is still at least half full, you are done. If it has become too small (an underflow), the tree repairs it locally:

  1. Redistribute (borrow): if a sibling leaf has more than the minimum, move one key from it into the underfull leaf and update the separator in the parent.
  2. Merge: if the sibling is exactly at the minimum, merge the two leaves into one and remove the separator from the parent.

Removing a separator can make the parent underflow, and the same repair repeats upward. If the root ends up with a single child, that child becomes the new root and the tree shrinks by a level. A deleted key may still appear as a separator in an inner node: that is harmless, since separators only need to direct the search correctly. Many real systems also delay merges, because underfull pages are cheaper than constant reshaping.

Height and fan-out

The number of children of a node is its fan-out. A page of 8 KB with 8-byte keys and 8-byte pointers holds about 500 entries, so a B+ tree with fan-out 500 has: 1 level = 500 keys, 2 levels = 250,000, 3 levels = 125,000,000, 4 levels = 62 billion. After many random inserts nodes are on average about 69% full, which lowers the figures a bit but not the idea: searching a table with hundreds of millions of rows costs about four page reads, and the top levels are cached in memory, so often only one or two reads actually hit the disk.

Python Fan-out, levels and B-tree vs B+ tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The B+ tree packs about 50% more children into the same page, which can save a whole level on very large tables.

Why B+ trees dominate

Property B-tree B+ tree
Row pointers In every node Only in leaves
Inner node fan-out Smaller Larger, so the tree is shorter
Search cost Variable (may stop early) Always root to leaf, predictable
Range scan Needs in-order traversal across levels Follow the leaf chain
Full ordered scan Visits inner nodes too Reads only the leaves

Predictable cost, cheap range scans and high fan-out are exactly what a database needs. You have already seen B+ trees in practice: every SQLite SEARCH ... USING INDEX in the previous lessons is a descent through one. SQL syntax and tuning are covered in SQL Indexes.

The tree above is a teaching model: no deletes, no concurrency, no page I/O. Real implementations add latching or lock-free techniques for concurrent access, store variable-length keys, compress prefixes and write nodes to a log before changing them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What happens to the height of a B+ tree when the root splits?

    A new root is created above the two halves, so every path becomes one step longer at the same time. This is how the tree stays balanced.
  2. 2. In a leaf split of a B+ tree, what happens to the separator key that goes into the parent?

    Leaves must contain every key with its row pointer, so the first key of the new right leaf is copied. In an internal split the middle key is moved.
  3. 3. Why is a range query cheaper on a B+ tree than on a B-tree?

    After finding the first key, a B+ tree reads neighbouring leaves in order. A B-tree has to move up and down between levels to visit keys in order.
  4. 4. A leaf drops below half full after a delete and its sibling is at the minimum. What is the repair?

    Borrowing only works if the sibling has spare keys. Otherwise the two nodes are merged, which may cascade to the parent.
  5. 5. With a fan-out of about 500, roughly how many levels are enough for 100 million keys?

    500^3 is 125 million, so three levels suffice, and the root and second level are usually cached.

Summary

  • B-trees and B+ trees are balanced, page-sized, wide trees whose nodes are at least half full.
  • Search costs one page read per level; inserts split full nodes (leaf: copy up, internal: move up) and the root split is the only thing that makes the tree taller.
  • Deletes repair underflows by borrowing from or merging with a sibling.
  • B+ trees keep row pointers only in linked leaves, so inner nodes have higher fan-out and range scans follow the leaf chain.
  • With fan-out in the hundreds, even billions of rows need only three or four levels.

Next: Hashing: Static, Extendible and Linear.