B-Tree

Why many keys per node?

A binary search tree holds one key per node, so a million keys need at least 20 levels, and a careless insertion order can make it far deeper. That is fine in memory, but on a disk every level is a separate block read, about 100,000 times slower than a comparison.

A B-tree packs many keys into one node, sized to fill one disk block. With 200 keys per node, a billion keys need only about 4 levels. It also keeps itself perfectly balanced: all leaves are always at the same depth.

The rules (order m)

Rule	Order 3	Order 4	Order m
Most children per node	3	4	m
Most keys per node	2	3	m − 1
Fewest keys (except the root)	1	1	⌈m/2⌉ − 1
Leaves	all at the same depth

Inside a node the keys are sorted, and they separate the children: everything in child i lies between keys i − 1 and i. Order 3 gives the 2-3 tree and order 4 the 2-3-4 tree (which is closely related to a red–black tree). Many textbooks (CLRS) describe B-trees by their minimum degree t instead: at most 2t − 1 keys per node.

Search

Start at the root. Inside the node, find the first key ≥ the target. If it equals the target, done. Otherwise go down to the child between the two neighbouring keys, and repeat. A search visits one node per level. In the example tree, searching for 17 visits [10], [20] and [12, 17]; searching for 8 visits [10], [6] and [7] and fails at the leaf.

Insertion

1. Search down to the leaf where the key belongs and insert it there, keeping the keys sorted.
2. If the leaf now has m keys (one too many), split it: the left half stays, the right half becomes a new node, and the middle key moves up into the parent.
3. The parent may now overflow too, so repeat upwards.
4. If the root splits, the middle key becomes a new root. That is the only way the tree gets taller, so the leaves always stay at the same depth.

The example (order 3)

Insert 10, 20, 5, 6, 12, 30, 7, 17, 3, 25:

• 10, 20 fit in the root. 5 makes [5, 10, 20]: split, 10 moves up as the new root, with [5] and [20] below.
• 6 → [5, 6]; 12 → [12, 20]; 30 → [12, 20, 30]: split, 20 moves up → root [10, 20].
• 7 → [5, 6, 7]: split, 6 moves up → root [6, 10, 20], which overflows too: split, 10 becomes the new root.
• 17, 3 and 25 fit into existing leaves.

Result (3 levels):

                 [10]
         [6]              [20]
    [3, 5]   [7]    [12, 17]   [25, 30]

With order 4, the same keys fit into 2 levels: root [6, 10, 20] with leaves [3, 5], [7], [12, 17], [25, 30].

Deletion (in brief)

Deleting from a leaf may leave it with too few keys (underflow). Then:

• Borrow a key from a sibling that has a spare one, rotating it through the parent, or
• Merge with a sibling, pulling the separating key down from the parent. The parent may underflow in turn; if the root becomes empty, the tree loses a level.

Deleting a key from an inner node first swaps it with its in-order predecessor or successor, which is always in a leaf.

B-tree versus B+ tree

	B-tree	B+ tree
Where the data is	in every node, each key once	only in the leaves
Inner nodes	keys and data	copies of keys, for routing only
Leaves linked	no	yes, for fast range scans
Used by	some file systems, in-memory indexes	almost every database index (MySQL InnoDB, PostgreSQL)

Code

import bisect, random

class BNode:
    def __init__(self, keys=None, kids=None):
        self.keys, self.kids = keys or [], kids or []      # no kids = leaf

class BTree:
    """B-tree of order m: every node has at most m - 1 keys and m children."""
    def __init__(self, m=3):
        self.m, self.root = m, BNode()

    def search(self, key):
        node, path = self.root, []
        while True:
            i = bisect.bisect_left(node.keys, key)
            path.append(node.keys)
            if i < len(node.keys) and node.keys[i] == key:
                return True, path
            if not node.kids:
                return False, path
            node = node.kids[i]

    def insert(self, key):
        split = self._insert(self.root, key)
        if split:                                          # the root itself split: the tree grows UP
            mid, right = split
            self.root = BNode([mid], [self.root, right])

    def _insert(self, node, key):
        i = bisect.bisect_left(node.keys, key)
        if i < len(node.keys) and node.keys[i] == key:
            return None                                    # already there
        if not node.kids:
            node.keys.insert(i, key)                       # insert into the leaf
        else:
            split = self._insert(node.kids[i], key)
            if split:                                      # a child split: take its middle key
                mid, right = split
                node.keys.insert(i, mid)
                node.kids.insert(i + 1, right)
        if len(node.keys) < self.m:
            return None
        h = len(node.keys) // 2                            # overflow: split around the middle key
        right = BNode(node.keys[h + 1:], node.kids[h + 1:])
        mid = node.keys[h]
        node.keys, node.kids = node.keys[:h], node.kids[:h + 1]
        return mid, right

    def levels(self):
        out, level = [], [self.root]
        while level:
            out.append([n.keys for n in level])
            level = [k for n in level for k in n.kids]
        return out

t = BTree(3)
for k in [10, 20, 5, 6, 12, 30, 7, 17, 3, 25]:
    t.insert(k)
print(t.levels())
# [[[10]], [[6], [20]], [[3, 5], [7], [12, 17], [25, 30]]]
print(t.search(17))
# (True, [[10], [20], [12, 17]])
print(t.search(8))
# (False, [[10], [6], [7]])
t4 = BTree(4)
for k in [10, 20, 5, 6, 12, 30, 7, 17, 3, 25]:
    t4.insert(k)
print(t4.levels())
# [[[6, 10, 20]], [[3, 5], [7], [12, 17], [25, 30]]]

The code was also checked on random insertions for orders 3, 4 and 5: every leaf is at the same depth, the keys come out sorted, and every node respects the minimum and maximum number of keys.

Common mistakes

• Saying a node of order m holds m keys. It holds at most m − 1 keys and m children.
• Splitting by copying the middle key. In a B-tree the middle key moves up; copying is what a B+ tree does for leaf splits.
• Growing the tree at the bottom. New levels appear only when the root splits.
• Forgetting that the parent can overflow after receiving the middle key. Splits can cascade up to the root.
• Confusing order and minimum degree. “Order m” counts children; CLRS’s t means at most 2t − 1 keys.