B-tree Basics
Suppose you have a billion keys and you want to find one of them. If the keys sit in a plain file, you may have to read the whole file. If they sit in a sorted file, you can jump to the right spot with binary search, but inserting a new key then means shifting everything after it. A database needs something better: a structure that keeps keys in order, finds any key in a handful of steps, and accepts new keys without rewriting the whole thing. The B-tree is the structure that database storage engines have relied on for decades to do exactly that.
Why Disks Break Ordinary Search Trees
A binary search tree gives you lookups in about $\log_2 N$ comparisons for $N$ keys, if it stays balanced. Each node holds one key and points to two children, so every comparison halves the remaining search space. In memory, that is fast.
On disk, the cost model changes. Reading a single node means reading a block from storage, and a random block read costs far more than a comparison. A balanced binary tree over a billion keys is about 30 levels deep, so a lookup could mean around 30 separate reads. On a spinning disk, each of those reads can take several milliseconds.
The common wrong intuition is that a tree is a tree, and where it lives does not matter. It matters a great deal here. The thing you are minimizing is not comparisons but trips to storage. A B-tree is built around that single goal.
Pages and the Fanout That Keeps Trees Shallow
Storage devices and the operating system move data in fixed-size blocks, and a database calls its unit of transfer a page. Pages are commonly 4 KB to 16 KB. A B-tree makes each node exactly one page, and it lets each node hold many keys instead of one.
The number of child pointers a node has is its fanout. If a 16 KB page holds about 1000 key and pointer pairs, the fanout is roughly 1000. The height of the tree then scales with the logarithm of the key count in base $f$, where $f$ is the fanout:
$$h \approx \log_f N$$
With $f = 1000$ and $N = 10^9$, the height is about 3. Three or four page reads find any key among a billion. A binary tree needs about 30 reads for the same job.
The exact layout of keys and pointers varies between systems, and the most common variant stores values only in the leaves. The search idea stays the same whatever the layout is.
The chart below compares the number of levels needed by a binary tree and by a B-tree with fanout 1000 as the key count grows.
spec: chart (grouped bar chart) titled "Levels to reach a key: binary tree vs B-tree with fanout 1000". X-axis categories: "1 thousand keys", "1 million keys", "1 billion keys", "1 trillion keys". Y-axis label "Levels (tree height)", scale 0 to 45. Two bar series: "Binary search tree" with values 10, 20, 30, 40; "B-tree, fanout 1000" with values 1, 2, 3, 4. Legend at top. Add a short caption under the chart: each level of a B-tree is one page read on disk.
Searching a B-tree
Every internal node stores separator keys, which are keys that split the range of its children. A node with separators $k_1 < k_2 < \dots < k_m$ has $m + 1$ children. Keys less than $k_1$ live in the first child, keys between $k_1$ and $k_2$ live in the second, and so on.
A search starts at the root. The database reads the root page, which is one disk access, and binary-searches the separators in memory. That tells it which child to visit next. It reads that child, repeats the step, and stops when it reaches a leaf. The total cost is the number of levels, one page read each.
Take a root holding separators 20 and 40. To find key 30, you compare 30 with 20 and 40, find that it falls between them, and follow the middle pointer. The middle child holds keys between 20 and 40, so you search it next. Nothing outside that one path is ever touched.
The diagram below shows a small tree and the path a search for key 30 takes through it.
spec: static diagram of a small B-tree with three levels. Root node at top labelled with keys [20 | 40] and three pointer slots. Its three children in the middle level: left node [5 | 10 | 15], middle node [25 | 30 | 35], right node [45 | 50 | 60]. Leaves are the same nodes, so show the middle node as the leaf that holds key 30. Draw the search path for key 30 in a bold colour: arrow from root to the middle child (labelled "30 is between 20 and 40"), then highlight key 30 inside the middle child. Label the root as "Level 1 (root)", middle as "Level 2 (leaf)". Caption under the diagram: a lookup reads one page per level.
Inserting and Deleting Keys
An insert first finds the leaf where the new key belongs, using the same search. It then adds the key in sorted order inside that leaf. Most inserts stop there, and the tree does not change shape at all.
When the target leaf is already full, the database has to make room. It divides the full node into two nodes, a step called a split, and pushes a new separator key up into the parent. The parent may now be full too, so the split can travel upward. If it reaches the root, the root splits and a new root is created above the old one. This is the point most people find surprising: a B-tree grows at the top, not at the bottom. Its height goes up by one only when the root itself splits.
Deletion runs the other way. You find the key and remove it. If a node falls below half full, the tree rebalances by borrowing a key from a sibling or merging two nodes. A merge can remove a level, which shrinks the tree. The precise rules for splits and merges belong to the implementation story, so here it is enough to know that both operations exist and keep the tree in shape.
The diagram below shows a root split, which is the one case where the tree gains a level.
spec: static diagram showing a root split in two stages side by side. Left stage labelled "Before insert": a single root node [10 | 20 | 30 | 40] full with four keys and five child pointers, children below it not drawn in detail, just small boxes labelled "children". Right stage labelled "After inserting 25": a new root at top containing the single separator [20], with two child nodes below: left child [10 | 15] and right child [25 | 30 | 40], and an arrow noting "height grows from 1 to 2". Use arrows between the two stages labelled "split". Keep labels exact as written.
The Invariants That Keep It Balanced
An invariant is a rule the structure must always satisfy. A B-tree has three that matter. Keys are sorted within every node and across the whole tree. Every leaf sits at the same depth. Every node except the root is at least half full.
These rules are what give the B-tree its guarantees. Because every leaf is at the same depth, every lookup reads the same number of pages. Because nodes stay at least half full, the fanout never drops below $f/2$, so the height is bounded by
$$h \le \log_{f/2} N$$
Imagine what happens without them. If you insert keys in sorted order into a plain binary search tree, each new key goes to the far right, and the tree becomes a chain of $N$ nodes. A B-tree cannot degenerate like that, because it never grows downward at the leaves. It only grows at the root.
One more thing to hold on to. A single insert can change several pages, for example a leaf, its parent, and perhaps the root. If the machine crashes halfway through, the tree could be left inconsistent. Keeping those multi-page changes safe is a separate problem, handled by transaction processing and recovery, and it is the reason the B-tree needs more than good shape to be a dependable storage structure.
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.