B-Tree, in depth: invariants, height bounds, splitting on insert, the deletion cases and a tested implementation

Shape, invariants and height

There are two naming conventions, and mixing them causes off-by-one bugs. This article uses the minimum degree t >= 2 from Cormen and co-authors' textbook. Knuth's order m counts the maximum number of children instead. A tree of minimum degree t has order 2t. The invariants are:

1. Every node holds its keys in sorted order. An internal node with n keys has exactly n + 1 children.
2. Keys separate subtrees. Every key in child i lies between the node's keys i - 1 and i.
3. Every non-root node holds between t - 1 and 2t - 1 keys. The root holds between 1 and 2t - 1, unless the tree is empty.
4. All leaves are at the same depth.

The third and fourth rules bound the height. The root has at least two children, and every other internal node has at least t. So at depth h there are at least 2t^(h-1) nodes, each holding at least t - 1 keys. Summing gives n >= 2t^h - 1, so h <= log_t((n + 1) / 2). With t = 500 and a billion keys, h is at most 3, so a lookup touches at most four nodes. The root and the next level are almost always cached, so a cold lookup costs one or two page reads. A balanced binary tree would need about thirty.

Comparisons barely change. Binary search inside each node costs about log2(2t) comparisons, so the total is still about log2 n. The B-tree does the same work in fewer, larger memory transfers, which is what the hardware rewards.

Search and range scans

Search starts at the root. Binary-search the node's keys for k. If k is found, stop. If the node is a leaf, k is absent. Otherwise descend into the child at the position where k would be inserted. One node per level means O(log_t n) node reads.

Range scans follow from the ordering. To list keys between a and b, search for a, then do an in-order walk that stops past b. In a plain B-tree that walk climbs back through internal nodes, because they hold keys too. The B+ tree variant, discussed below, keeps every key in the leaves and links leaves together, so a range scan becomes a sequential read.

Insertion and splits

New keys always go into a leaf. The difficulty is a full leaf, one with 2t - 1 keys. The fix is to split it. The median key moves up into the parent, and the keys on either side become two nodes with t - 1 keys each. The parent gains a key and might now be full, so a naive implementation splits back up the path after reaching the leaf.

The single-pass version avoids walking back. On the way down, split any full child before entering it. That guarantees the parent always has room for a promoted median. If the root itself is full, make a new empty root above it and split the old root. This is the only way the tree grows taller, and it grows at the top, which is why all leaves stay at the same depth.

Worked example with t = 2, so each node holds at most 3 keys. Insert 10, 20, 5, 6, 12, 30, 7 and 17 in that order.

1. 10, 20 and 5 fill the root: [5, 10, 20].
2. Inserting 6 finds the root full. A new root takes the median 10, leaving children [5] and [20]. Then 6 descends left: {[10]: [5, 6] [20]}.
3. 12 and 30 go right, and 7 goes left: {[10]: [5, 6, 7] [12, 20, 30]}.
4. Inserting 17 descends right, into a full child. Split it first: 20 moves up, giving {[10, 20]: [5, 6, 7] [12] [30]}. Then 17 lands beside 12: {[10, 20]: [5, 6, 7] [12, 17] [30]}.

Deletion without underflow

Deletion mirrors insertion. Insertion must never enter a full node, and deletion must never enter a node with the minimum t - 1 keys, because removing a key there would break the invariant. Before descending into a minimal child, top it up. Then the delete can always finish in one pass. The cases are:

• Case 1. k is in a leaf. Remove it. The descent rule guarantees the leaf has a spare key, or is the root.
• Case 2. k is in an internal node at position i. If the left child has at least t keys, replace k with its predecessor (the largest key in the left subtree) and delete that recursively. If not, but the right child has at least t keys, use the successor instead. If both have only t - 1, merge them with k into one node of 2t - 1 keys, then delete k from it.
• Case 3. k is not in this node, and the child to descend into has t - 1 keys. If a neighbouring sibling has at least t keys, rotate one through the parent: the parent's separator moves down into the child, and the sibling's edge key moves up. Otherwise merge the child with a sibling and the separator between them.

A merge can empty the root. When the root has no keys but still has one child, that child becomes the root, and the tree gets one level shorter. Forgetting this step leaves a zero-key root, which is a common B-tree bug.

Continue the example. Delete 6 (case 1): {[10, 20]: [5, 7] [12, 17] [30]}. Delete 20 (case 2): its left child [12, 17] has t = 2 keys, so the predecessor 17 replaces it: {[10, 17]: [5, 7] [12] [30]}. Delete 12 (case 3): the child [12] is minimal, and its left sibling [5, 7] can lend. 10 moves down and 7 moves up, giving {[7, 17]: [5] [10, 12] [30]}, and then 12 is removed. Delete 5 (case 3): the child [5] is minimal and so is its sibling [10], so they merge with 7: [5, 7, 10]. The root becomes [17], and the result is {[17]: [7, 10] [30]}.

A complete implementation

The implementation below follows those cases exactly. It is written for clarity, with nodes as Python lists, but the structure carries straight over to fixed-size pages. Its check method asserts every invariant and returns the key count.

import bisect

class Node:
    __slots__ = ("keys", "children")
    def __init__(self, leaf=True):
        self.keys, self.children = [], None if leaf else []
    @property
    def leaf(self):
        return self.children is None

class BTree:
    def __init__(self, t=3):
        self.t, self.root = t, Node()

    def search(self, k):
        x = self.root
        while True:
            i = bisect.bisect_left(x.keys, k)
            if i < len(x.keys) and x.keys[i] == k:
                return True
            if x.leaf:
                return False
            x = x.children[i]

    def _split_child(self, x, i):
        t, y = self.t, x.children[i]
        z = Node(leaf=y.leaf)
        median = y.keys[t - 1]
        z.keys, y.keys = y.keys[t:], y.keys[:t - 1]
        if not y.leaf:
            z.children, y.children = y.children[t:], y.children[:t]
        x.keys.insert(i, median)
        x.children.insert(i + 1, z)

    def insert(self, k):
        if len(self.root.keys) == 2 * self.t - 1:      # grow at the top
            s = Node(leaf=False)
            s.children.append(self.root)
            self.root = s
            self._split_child(s, 0)
        x = self.root
        while not x.leaf:
            i = bisect.bisect_right(x.keys, k)
            if len(x.children[i].keys) == 2 * self.t - 1:
                self._split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            x = x.children[i]
        bisect.insort(x.keys, k)

    def delete(self, k):
        self._delete(self.root, k)
        if not self.root.keys and not self.root.leaf:  # shrink at the top
            self.root = self.root.children[0]

    def _delete(self, x, k):
        t = self.t
        i = bisect.bisect_left(x.keys, k)
        if i < len(x.keys) and x.keys[i] == k:
            if x.leaf:                                  # case 1
                x.keys.pop(i)
                return
            left, right = x.children[i], x.children[i + 1]
            if len(left.keys) >= t:                     # case 2a: predecessor
                y = left
                while not y.leaf:
                    y = y.children[-1]
                x.keys[i] = y.keys[-1]
                self._delete(left, x.keys[i])
            elif len(right.keys) >= t:                  # case 2b: successor
                y = right
                while not y.leaf:
                    y = y.children[0]
                x.keys[i] = y.keys[0]
                self._delete(right, x.keys[i])
            else:                                       # case 2c: merge
                self._merge(x, i)
                self._delete(left, k)
            return
        if x.leaf:
            return                                      # absent
        if len(x.children[i].keys) == t - 1:            # case 3
            i = self._fill(x, i)
        self._delete(x.children[i], k)

    def _fill(self, x, i):
        t, c = self.t, x.children[i]
        if i > 0 and len(x.children[i - 1].keys) >= t:  # borrow from left
            s = x.children[i - 1]
            c.keys.insert(0, x.keys[i - 1])
            x.keys[i - 1] = s.keys.pop()
            if not c.leaf:
                c.children.insert(0, s.children.pop())
            return i
        if i < len(x.children) - 1 and len(x.children[i + 1].keys) >= t:
            s = x.children[i + 1]                       # borrow from right
            c.keys.append(x.keys[i])
            x.keys[i] = s.keys.pop(0)
            if not c.leaf:
                c.children.append(s.children.pop(0))
            return i
        if i < len(x.children) - 1:                     # merge with right
            self._merge(x, i)
            return i
        self._merge(x, i - 1)                           # merge with left
        return i - 1

    def _merge(self, x, i):
        left, right = x.children[i], x.children.pop(i + 1)
        left.keys += [x.keys.pop(i)] + right.keys
        if not left.leaf:
            left.children += right.children

Test it the way you would test any balanced tree: a long random sequence of inserts, deletes and lookups checked against a reference set, with an invariant check after every operation. The run used to verify this code made 20,000 random operations for each of t = 2, 3, 4 and 7, with zero failures. Small t matters most, because with t = 2 almost every operation touches a boundary case.

Variants and engineering

B+ trees. Internal nodes hold only separator keys, and all records live in leaves that are linked to their neighbours. Internal nodes fit more separators, so fan-out rises, and range scans become a walk along the leaf chain. Most database indexes and file systems use this form.

Bulk loading. Building a tree by inserting sorted keys one at a time leaves nodes about half full. If the data is already sorted, fill leaves left to right to a chosen fill factor, then build each internal level from the first key of each node below. This is far faster and gives a denser tree.

Choosing t. On disk, size a node to a page and derive t from key and pointer sizes. In memory, nodes of a few cache lines often beat red-black trees, because a scan over contiguous keys is cheap compared with a cache miss. Rust's standard BTreeMap is a B-tree for this reason.

Concurrency and durability. Multi-threaded B-trees use latch crabbing: hold a child's latch before releasing the parent's, and release ancestors early once the child cannot split or merge. Lehman and Yao's B-link tree adds right-sibling pointers so that readers can recover from a concurrent split without locking. On disk, a crash in the middle of a split must not leave a half-written tree, so engines log changes first or write modified pages to new locations (copy-on-write).

Failure modes

When to use something else

Choose a B-tree when you need ordered keys, range queries and predictable worst-case latency, especially when data lives on pages. A hash table wins for exact-match lookups and gives no ordering. An LSM tree wins for write-heavy workloads, because it turns random writes into sequential ones, and it pays with read amplification and compaction. LSM trees versus B-trees compares the two in detail. A trie wins when keys share long prefixes and you query by prefix.

What to do next

1. Implement the tree yourself from the invariants before reading the code above, then compare.
2. Run the randomized test at t = 2 with an invariant check after every operation, and keep it in your suite.
3. Trace the deletion example by hand, naming the case at each step.
4. Add a range scan, then convert the tree into a B+ tree with linked leaves and compare scan speed.
5. Write a bulk loader for sorted input and measure node fill against one-by-one insertion.
6. Benchmark an in-memory B-tree against a sorted array and a balanced binary tree at several values of t.
7. Read how a database engine stores the same structure on pages, and find its page size and fan-out.