B-Trees: The Index Behind Every Database

A tree built for slow storage

A red-black tree is optimised to minimise comparisons in RAM. A B-tree (Bayer and McCreight, 1972) is optimised for something else entirely: minimising the number of disk reads, which are vastly slower than any in-memory comparison. Instead of one key per node, a B-tree of order m packs many keys into each node — enough to fill exactly one disk page or cache line — so a single slow read pulls in hundreds of comparisons' worth of information at once.

order m B-tree, every non-root node holds:
  between ceil(m/2) - 1  and  m - 1   keys
  between ceil(m/2)      and  m       children (internal nodes)

keys inside a node are sorted; the k+1 children of a node with k keys
"straddle" the k keys, so child[i] holds keys strictly between
key[i-1] and key[i]

Insertion: fill, split at the median, push up

A new key is inserted into the appropriate leaf, keeping it sorted. If that leaf now holds m keys — one too many — it splits: the median key moves up into the parent, and the keys on either side of it become two separate half-full nodes.

insert(key):
  leaf = find_leaf(key)
  insert key into leaf, keeping it sorted
  while leaf.keyCount == m:               // overfull, must split
    mid = leaf.keys[m / 2]                 // median key
    left, right = split leaf around mid
    if leaf has no parent:
      create new root with mid, children [left, right]  // tree grows +1 level
    else:
      insert mid into leaf.parent, replace leaf with [left, right]
      leaf = leaf.parent                   // the split may cascade upward

The crucial detail is that a B-tree only grows upward, by splitting the root, so every leaf always stays at the exact same depth — there is no leaf that is deeper than another, unlike an unbalanced binary tree.

Why the height barely counts as logarithmic

A B-tree's height is O(log_m n), where the base of the logarithm is the branching factor m, not 2. A red-black tree with a million keys has a height around 2·log2(1,000,000) ≈ 40. A B-tree of order 200 storing the same million keys has a height around log_200(1,000,000) ≈ 2.6 — practically 3 levels. That difference is the entire reason B-trees exist: with a large enough m chosen to match a disk page or cache line, essentially any database table with millions or billions of rows can be searched in 3 or 4 disk reads, and the top one or two levels typically stay cached in RAM permanently, making most lookups even cheaper in practice.

B+ trees and B* trees

Almost no production database uses a plain B-tree; nearly all use a B+ tree. The difference: internal nodes in a B+ tree store copies of keys purely to route searches, while all the actual data lives in the leaves, and the leaves are linked into a chain. That chain turns an ordered range query — "give me every row between X and Y" — into a single tree descent followed by a fast sideways walk along linked leaves, instead of repeated full tree traversals. A B* tree goes further and delays splitting: when a node overflows, it first tries to redistribute keys with a sibling, splitting into two only when both neighbours are also full, and splits 2 full nodes into 3 two-thirds-full ones instead of 2 half-full ones — keeping nodes fuller (about 2/3 instead of 1/2) at the cost of a more complex insert.

Frequently asked questions

Try it live

Everything above runs in your browser — open B-Trees and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.