B-trees and B+ trees

What this chapter covers

Every balanced tree so far assumed its nodes live in fast memory, where following a pointer is nearly free. B-trees drop that assumption. When a tree indexes data on disk — as every database and filesystem does — each level you descend is a disk read, roughly a hundred thousand times slower than a memory access, and the only thing that matters is reading as few blocks as possible. A binary tree, with its log₂ n levels, reads far too many. The B-tree's answer is radical width: pack hundreds of keys into each node, give each node hundreds of children, and the tree becomes only three or four levels tall for millions of keys. This chapter builds the classic B-tree, watches its nodes fill and split, and shows why fan-out — not cleverness — is what makes it the index behind the world's data.

A bit of history

The B-tree was invented in 1970 by Rudolf Bayer and Edward McCreight, working at Boeing's research labs. They were solving a concrete problem — how to index large files stored on the slow disks of the era so lookups didn't require reading the whole file — and their answer, the balanced multi-way tree, was so effective it never needed replacing. What the "B" stands for is a genuine mystery the inventors have coyly refused to settle: Bayer, balanced, Boeing, and "broad" have all been proposed, and McCreight once joked that "the more you think about what the B could mean, the better you understand B-trees." The variant that databases actually use, the B+ tree, followed shortly after. Fifty years later, B-trees and B+ trees index every relational database (PostgreSQL, MySQL, Oracle, SQLite), the major filesystems (NTFS, HFS+, ext4, Btrfs — the name is literally "B-tree filesystem"), and countless key-value stores. It may be the most commercially important data structure ever devised.

The intuition

The key realization is that on disk, cost is counted in blocks read, not comparisons. Reading a disk block gets you a few thousand bytes for the price of one slow seek, so you should make each node exactly one block and cram as many keys into it as fit. A node with, say, 128 keys has 129 children, so the tree branches 129 ways at every level instead of 2. That fan-out is everything: a binary tree over a million keys is about 20 levels deep — 20 disk reads per lookup — while a B-tree of order 128 over the same million keys is 3 levels deep, 3 disk reads. Same asymptotic O(log n), but the base of the logarithm is 128 instead of 2, and on disk that base is the whole ballgame.

Keeping a B-tree balanced uses the same overflow-and-promote move you saw hiding inside the red-black tree. A node holds between t−1 and 2t−1 keys (for minimum degree t). To insert, find the right leaf and drop the key in. If a node overflows past 2t−1 keys, split it into two half-full nodes and push its median key up into the parent — which may overflow and split in turn. The tree grows taller only when the root itself splits, and because that happens at the top, all leaves always stay at exactly the same depth. Perfect balance falls out of the splitting, no rotations required.

Complexity: how it scales

Search, insert, and delete are all $O(\log n)$ — but the meaningful measure is the number of levels, since each level is a disk read. With fan-out m, the height is $\log_m n$, dramatically fewer levels than a binary tree's $\log_2 n$. The chart makes the gap concrete, plotting levels (≈ disk reads per lookup) for an order-128 B-tree against a balanced binary tree:

At 500000 keys the B-tree stood 3 levels tall to the binary tree's 19 — about 6× fewer disk reads per lookup, and the ratio grows with data size. On real hardware, where a disk seek is milliseconds and a memory access is nanoseconds, turning 19 reads into 3 is the difference between a database that's usable and one that isn't. Within a node the B-tree does more comparisons (it scans up to 2t−1 keys), but those happen in fast memory once the block is loaded, so they're nearly free compared to the read that fetched them.

What it's good at, what it isn't

The B-tree is the right structure — the only reasonable structure — for an ordered index that lives on disk or in any storage where access is block-oriented and reads are the bottleneck. That's databases and filesystems, but also the on-disk parts of key-value stores and search engines. It keeps data sorted (so it supports range queries and ordered scans, unlike a hash index), it stays balanced automatically, and it minimizes the expensive operation — block reads — by design. Its close variant the B+ tree, which stores all actual records in the leaves and links the leaves together, is what production databases use, because it makes range scans a simple walk along the leaf level.

Where it's the wrong tool is in memory. When every node is a fast pointer-follow away, the B-tree's wide nodes and in-node scanning are pure overhead, and a red-black or AVL tree — or a hash table, if you don't need order — is simpler and faster. The B-tree's entire advantage is the disk model; remove the disk, and its reason for existing goes with it. Its delete is also genuinely intricate (nodes can underflow, requiring keys to be borrowed from siblings or nodes to be merged), which is why this chapter, like the red-black one, focuses on the insert that reveals the balancing idea.

The data, or the inputs

The height chart builds order-128 B-trees at growing sizes and compares their levels to a balanced binary tree's — measuring the thing that actually costs money, disk reads per lookup. The animation uses a tiny B-tree (order 4, so nodes hold at most 3 keys and split quickly) and inserts ten keys, so you can watch nodes fill, overflow, and split, with medians rising toward the root.

Build it, one function at a time

Search scans a node's sorted keys, then descends into the right child — one node visit (disk read) per level:

def search(self, key, node=None, probe=None):
    """O(log_m n) node visits, O(t) work per node. Within a node, scan its sorted keys
    for the key or the child to descend into. Each node visited is one disk read in the
    real thing, so the fat nodes mean very few of them."""
    node = self.root if node is None else node
    if probe is not None:
        probe.append(1)             # count this node visit (a "disk read")
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    if i < len(node.keys) and node.keys[i] == key:
        return True
    if node.leaf:
        return False
    return self.search(key, node.children[i], probe)

Insert splits any full node before descending, so there's always room, and splits the root to grow taller:

def insert(self, key):
    """Insert into the correct leaf. To keep every level full enough, split any node
    that's already full BEFORE descending into it, so there's always room. If the root
    itself is full, split it into a new root — the only way a B-tree grows taller, which
    keeps all leaves at the same depth."""
    if self.search(key):
        return
    root = self.root
    if len(root.keys) == 2 * self.t - 1:
        new_root = BTreeNode(leaf=False)
        new_root.children.append(root)
        self._split_child(new_root, 0)
        self.root = new_root
        self._insert_nonfull(new_root, key)
    else:
        self._insert_nonfull(root, key)

The split is the balancing move — cut a full node in half and lift its median into the parent:

def _split_child(self, parent, i):
    """Split parent.children[i], a full node, into two half nodes and lift its median
    key up into the parent. This is the B-tree's balancing move — the same overflow-and-
    promote a 2-3-4 tree (and a red-black tree) uses, just with wider nodes."""
    t = self.t
    full = parent.children[i]
    sibling = BTreeNode(leaf=full.leaf)
    median = full.keys[t - 1]
    sibling.keys = full.keys[t:]           # right half of the keys
    full.keys = full.keys[:t - 1]          # left half; median moves up
    if not full.leaf:
        sibling.children = full.children[t:]
        full.children = full.children[:t]
    parent.keys.insert(i, median)
    parent.children.insert(i + 1, sibling)

Watch it work

Here's a small B-tree (each node holds at most 3 keys) built by inserting ten values. Green marks the node the new key landed in. Step through it and watch the mechanics: keys accumulate in a node, sorted, until it holds three; the next key would overflow it, so the node splits into two, and its median key rises into the parent. When the root itself overflows and splits, the tree gains a level — and because that only ever happens at the top, every leaf stays at the same depth throughout. Notice how few levels it takes to hold ten keys, and imagine each node holding a hundred instead of three: that's how three levels hold a million:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the B-tree. The library tab is the only honest counterpart: a function computing the height of a balanced binary tree over the same keys — the disk reads you'd pay without fat nodes — because Python has no B-tree; it's the structure inside your database, not your standard library.

"""The B-tree — the balanced search tree reimagined for disk, and the structure that
indexes essentially every database and filesystem in the world.

A binary search tree branches two ways per node, so it's tall — log₂ n levels. But when
each node lives on disk, every level you descend is a disk read, the slowest thing a
computer does, and tallness is death. The B-tree fixes this by making nodes *fat*: each
node holds many keys and has many children (hundreds, in practice), so the tree is
short — log_m n levels — and a lookup touches only a handful of disk blocks. It stays
balanced the way a 2-3-4 tree does: insert into a leaf, and when a node overflows, split
it and push its middle key up to the parent, growing the tree taller only at the root.

This implementation is the classic B-tree with minimum degree `t`: every node (except the
root) holds between t−1 and 2t−1 keys.
"""


class BTreeNode:
    __slots__ = ("keys", "children", "leaf")

    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf


class BTree:
    def __init__(self, t=3):
        self.t = t                      # minimum degree: max 2t-1 keys, max 2t children
        self.root = BTreeNode(leaf=True)

    # region: search
    def search(self, key, node=None, probe=None):
        """O(log_m n) node visits, O(t) work per node. Within a node, scan its sorted keys
        for the key or the child to descend into. Each node visited is one disk read in the
        real thing, so the fat nodes mean very few of them."""
        node = self.root if node is None else node
        if probe is not None:
            probe.append(1)             # count this node visit (a "disk read")
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return True
        if node.leaf:
            return False
        return self.search(key, node.children[i], probe)
    # endregion

    # region: insert
    def insert(self, key):
        """Insert into the correct leaf. To keep every level full enough, split any node
        that's already full BEFORE descending into it, so there's always room. If the root
        itself is full, split it into a new root — the only way a B-tree grows taller, which
        keeps all leaves at the same depth."""
        if self.search(key):
            return
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_nonfull(new_root, key)
        else:
            self._insert_nonfull(root, key)
    # endregion

    # region: split_child
    def _split_child(self, parent, i):
        """Split parent.children[i], a full node, into two half nodes and lift its median
        key up into the parent. This is the B-tree's balancing move — the same overflow-and-
        promote a 2-3-4 tree (and a red-black tree) uses, just with wider nodes."""
        t = self.t
        full = parent.children[i]
        sibling = BTreeNode(leaf=full.leaf)
        median = full.keys[t - 1]
        sibling.keys = full.keys[t:]           # right half of the keys
        full.keys = full.keys[:t - 1]          # left half; median moves up
        if not full.leaf:
            sibling.children = full.children[t:]
            full.children = full.children[:t]
        parent.keys.insert(i, median)
        parent.children.insert(i + 1, sibling)
    # endregion

    def _insert_nonfull(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_nonfull(node.children[i], key)

    def height(self):
        h, node = 1, self.root
        while not node.leaf:
            node = node.children[0]
            h += 1
        return h

    def inorder(self):
        out = []

        def rec(node):
            for i, k in enumerate(node.keys):
                if not node.leaf:
                    rec(node.children[i])
                out.append(k)
            if not node.leaf:
                rec(node.children[-1])

        rec(self.root)
        return out

"""B-trees live in databases and filesystems, not in a Python module — there's no stdlib
B-tree. The point of a B-tree is *height*: because a lookup's cost on disk is the number of
nodes (blocks) it reads, the meaningful comparison is a B-tree's log_m n levels against a
binary tree's log₂ n levels. So the reference here computes the height of a perfectly
balanced BINARY tree over the same number of keys — the number of disk reads you'd pay
without the B-tree's fat nodes.
"""
import math


# region: binary_height
def balanced_binary_height(n):
    """Height (levels, ≈ disk reads per lookup) of a perfectly balanced BINARY search tree
    over n keys: ⌈log₂(n+1)⌉. The B-tree's whole reason to exist is to make this number
    much smaller by branching hundreds of ways instead of two."""
    if n <= 0:
        return 0
    return math.ceil(math.log2(n + 1))
# endregion

Scratch vs library

There's no speed face-off here, because a B-tree's whole point is invisible in a pure-memory benchmark — the disk reads it saves don't show up when everything is in RAM. The real comparison is the one the height chart makes: 3 levels versus 19 at half a million keys. To feel what that means, price it in disk time. A random disk seek is on the order of a millisecond; a memory access is a hundred nanoseconds. Nineteen seeks is ~19 milliseconds per lookup; three seeks is ~3. Multiply by the millions of lookups a database serves and the difference is between a system that responds instantly and one that grinds. That is why the B-tree matters: it doesn't compute a better answer than a red-black tree, it computes the same answer while touching the slow part of the machine six times less. Match your structure to the memory hierarchy it runs on — the deepest lesson in practical data structures, and the one the B-tree teaches most vividly.

Where you'll actually meet it

You meet B-trees every time you query a database. Create an index in PostgreSQL, MySQL, Oracle, or SQLite and you've built a B+ tree; every indexed lookup and range scan walks it. Filesystems are built on them — NTFS, HFS+, APFS, ext4's directories, and Btrfs (named for the structure) organize files and metadata as B-trees so opening a file in a huge directory stays fast. Key-value and document stores (from BerkeleyDB to modern engines) use B-trees or their log-structured cousins for on-disk ordering. Even at smaller scale, any time data is too big for memory and must stay sorted on storage, the B-tree is the answer. It is, quietly, one of the most-executed data structures on Earth.

Takeaways

A B-tree is a balanced search tree with very wide nodes — one disk block each — so its height is $\log_m n$ instead of $\log_2 n$, turning a lookup from twenty disk reads into three. It stays balanced by splitting overflowing nodes and promoting medians, keeping all leaves at equal depth with no rotations, and its B+ variant chains the leaves for fast range scans. It's the right structure exactly when data lives on disk and reads are the bottleneck — which is why it indexes essentially every database and filesystem — and the wrong one in memory, where a red-black tree is simpler.

That completes the classic trees. One structure remains in the tier, and it's a tree of a completely different character. Union-Find doesn't store ordered data or answer range queries; it tracks which elements belong to the same group, merging groups and testing membership in almost-constant time. It's the structure behind Kruskal's minimum spanning tree, connected components, and network connectivity — and it closes the tree tier by showing that a tree can be a tool for grouping, not just for searching.