CodeLudo 🔥 Daily Guides

Why Databases Use B-Trees: Fewer Levels Beats Fewer Comparisons

✓ numbers produced by the code on this page · Published 2026-08-20

Two earlier pages in this cluster name B-trees as what databases and filesystems actually use, and both defer the reason. Here it is, and it is not that a B-tree is a cleverer balanced tree.

It is that balanced binary trees optimise the wrong thing once your data lives on disk.

Levels are the cost, not comparisons

Every other structure in this cluster counts comparisons or pointer hops, because in memory those are what you pay. Storage changes the arithmetic completely. Reading a page from a disk is millions of times slower than comparing two integers — so once a tree is too big for memory, the number that matters is how many levels a lookup touches, because each level is a separate read.

A well-balanced binary tree of a billion keys is about 30 levels deep. That is 30 disk reads for one lookup, and the ~30 comparisons between them are free by comparison. Halving the comparisons would gain nothing. Halving the levels would halve the lookup.

A B-tree does that by putting many keys in each node instead of one.

Drag the branching factor

A node of order m holds up to m − 1 keys and has up to m children.

Grow a B-tree wider, not taller

A B-tree is a search tree whose nodes hold many keys instead of one. A node of order m holds up to m − 1 keys and has up to m children, so the tree fans out instead of stretching down.

The same 24 keys form a tree 5 levels deep at order 3, and 2 levels deep at order 8 — same data, same insert order, no rotations anywhere. Every leaf sits at the same depth in both (true and true), because a B-tree only ever gains height at the root: a full node splits and pushes its median key upward, and the tree grows a level only when that reaches the top.

That shape is the whole point for storage. Holding 1,000,000,000 keys takes about 30 levels in a binary tree and 4 in a B-tree of order 400. When each level is a separate page read from disk, that is the difference between 30 reads and 4.

Filled nodes are internal, outlined ones are leaves. Whatever you do, every leaf stays on the bottom row — that is the invariant, not a coincidence of these inputs.

Add twenty-odd keys, then drag the order slider. The same keys go from a tall thin tree to a short wide one, and no rotation happens anywhere. A B-tree never rebalances the way an AVL tree does. It stays balanced because of how it grows.

It grows at the root, not at the leaves

This is the part that makes the invariant work, and it is the opposite of every other tree here.

In a binary search tree a new value lands at the bottom, and the tree gets taller wherever it happens to land — which is exactly how insert order ruins it. A B-tree inserts into a leaf too, but when a node is full it splits in two and pushes its median key up into its parent. If the parent is full, it splits too. If that reaches the root, the root splits and a brand new root is created above it.

That is the only way a B-tree can ever gain height. Since the root is the thing that moves upward, every leaf descends by one level at the same instant — so all leaves are always at the same depth. The lab reports that as a live check rather than a claim, because it is the definition of the structure and it is easy to state and hard to believe until you watch it hold.

The numbers

python 
import math


def node(leaf=True):
    return {"keys": [], "children": [], "leaf": leaf}


def split_child(parent, i, order, stats):
    """Split parent's full child i, pushing its median key up into parent."""
    stats["splits"] += 1
    full = parent["children"][i]
    mid = (order - 1) // 2
    right = node(full["leaf"])
    right["keys"] = full["keys"][mid + 1:]
    median = full["keys"][mid]
    if not full["leaf"]:
        right["children"] = full["children"][mid + 1:]
        full["children"] = full["children"][:mid + 1]
    full["keys"] = full["keys"][:mid]
    parent["keys"].insert(i, median)
    parent["children"].insert(i + 1, right)


def insert_nonfull(nd, key, order, stats):
    i = len(nd["keys"]) - 1
    if nd["leaf"]:
        nd["keys"].append(None)
        while i >= 0 and key < nd["keys"][i]:
            nd["keys"][i + 1] = nd["keys"][i]
            i -= 1
        nd["keys"][i + 1] = key
        return
    while i >= 0 and key < nd["keys"][i]:
        i -= 1
    i += 1
    if len(nd["children"][i]["keys"]) == order - 1:
        split_child(nd, i, order, stats)
        if key > nd["keys"][i]:
            i += 1
    insert_nonfull(nd["children"][i], key, order, stats)


def insert(root, key, order, stats):
    """The ONLY place height changes: a full root splits and a new root appears above it."""
    if len(root["keys"]) == order - 1:
        fresh = node(leaf=False)
        fresh["children"].append(root)
        split_child(fresh, 0, order, stats)
        root = fresh
    insert_nonfull(root, key, order, stats)
    return root


def levels(nd):
    return 1 if nd["leaf"] else 1 + levels(nd["children"][0])


def in_order(nd, out=None):
    if out is None:
        out = []
    if nd["leaf"]:
        out.extend(nd["keys"])
        return out
    for i, key in enumerate(nd["keys"]):
        in_order(nd["children"][i], out)
        out.append(key)
    in_order(nd["children"][-1], out)
    return out


def all_leaves_level(nd, depth=1, seen=None):
    """A B-tree's defining invariant: every leaf sits at the same depth."""
    if seen is None:
        seen = set()
    if nd["leaf"]:
        seen.add(depth)
    else:
        for child in nd["children"]:
            all_leaves_level(child, depth + 1, seen)
    return len(seen) == 1


print(f"{'order':>5} {'keys':>7} {'levels':>7} {'splits':>7} {'sorted':>7} {'leaves level':>13}")
for order in (3, 4, 8):
    for count in (100, 1000):
        stats = {"splits": 0}
        root = node()
        for k in range(1, count + 1):          # sorted input, the worst case everywhere else
            root = insert(root, k, order, stats)
        ok = in_order(root) == list(range(1, count + 1))
        print(f"{order:>5} {count:>7,} {levels(root):>7} {stats['splits']:>7} {str(ok):>7} {str(all_leaves_level(root)):>13}")

print()
print("Levels needed to hold N keys, by branching factor:")
print(f"{'keys':>12} {'order 2':>9} {'order 8':>9} {'order 100':>10} {'order 400':>10}")
for n in (1_000, 1_000_000, 1_000_000_000):
    row = [math.ceil(math.log(n + 1, m)) for m in (2, 8, 100, 400)]
    print(f"{n:>12,} {row[0]:>9} {row[1]:>9} {row[2]:>10} {row[3]:>10}")
Output 
order    keys  levels  splits  sorted  leaves level
    3     100       7      94    True          True
    3   1,000      10     991    True          True
    4     100       6      90    True          True
    4   1,000       9     983    True          True
    8     100       3      29    True          True
    8   1,000       5     326    True          True

Levels needed to hold N keys, by branching factor:
        keys   order 2   order 8  order 100  order 400
       1,000        10         4          2          2
   1,000,000        20         7          4          3
1,000,000,000        30        10          5          4

Note the input: 1 to 1,000 in sorted order, the sequence that turns a plain binary search tree into a 1,000-level linked list. The B-tree does not care. At order 8 it is 5 levels, every leaf on the same row, contents in order — no rotations, no special handling of sorted input, nothing.

The lower table is why the structure exists. A billion keys need 30 levels at branching factor 2 and 4 at branching factor 400. A real database index picks its order from the disk page size — fit as many keys into one page as the page holds, because reading 400 keys costs the same as reading one. Three or four reads to find any row among a billion is the entire reason your database does not slow down as it fills.

What this page simplifies