Multi-Way & Disk-Oriented Trees

Why Binary Trees Struggle on Disk

A balanced BST or red-black tree over a million keys has a height around 20, Lesson 10's O(log n) guarantee. That's excellent when every step is an in-memory pointer dereference. But if every node lives on disk, that's 20 separate disk seeks to find one record, and each seek dwarfs the cost of comparing a handful of keys once you're already there.

The B-Tree Idea

A B-Tree generalizes the BST invariant from "one key, two children" to "many sorted keys, many children". For a B-Tree of minimum degree t, every node (except the root) holds between t - 1 and 2t - 1 keys, and an internal node with k keys always has exactly k + 1 children. Between any two keys in a node sits a child pointer to a subtree whose values all fall between them, the same ordering idea from Lesson 8, just spread across more than one key per node.

class BTreeNode:
    def __init__(self, leaf: bool = True) -> None:
        self.leaf = leaf
        self.keys: list[int] = []
        self.children: list["BTreeNode"] = []

class BTree:
    def __init__(self, t: int = 2) -> None:
        self.t = t                       # minimum degree: every non-root node
        self.root = BTreeNode(leaf=True) # holds between t-1 and 2t-1 keys

    def search(self, key: int, node: "BTreeNode | None" = None) -> bool:
        node = node or self.root
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return True
        if node.leaf:
            return False
        return self.search(key, node.children[i])   # one disk read per level

Searching walks down exactly one path from root to leaf, scanning each node's small, sorted key list to decide which child to follow next, still O(log n), just with a much smaller number of levels for the same n.

Splitting a Full Node

Insertion walks down from the root the same way search does, but first checks whether each node it's about to enter is already full. If so, that node splits before the descent continues: its middle key moves up into the parent, and the remaining keys divide into two smaller nodes.

    def insert(self, key: int) -> None:
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # Root is full: split it first, this is the only way height grows
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_non_full(new_root, key)
        else:
            self._insert_non_full(root, key)

    def _split_child(self, parent: "BTreeNode", index: int) -> None:
        t = self.t
        full_child = parent.children[index]
        new_child = BTreeNode(leaf=full_child.leaf)

        mid_key = full_child.keys[t - 1]           # the middle key moves up
        new_child.keys = full_child.keys[t:]
        full_child.keys = full_child.keys[:t - 1]

        if not full_child.leaf:
            new_child.children = full_child.children[t:]
            full_child.children = full_child.children[:t]

        parent.children.insert(index + 1, new_child)
        parent.keys.insert(index, mid_key)

    def _insert_non_full(self, node: "BTreeNode", key: int) -> None:
        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)          # split full children on the way down
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

tree = BTree(t=2)   # nodes hold 1 to 3 keys
for value in [10, 20, 5]:
    tree.insert(value)
# root is now a single leaf: [5, 10, 20], already at capacity

tree.insert(6)
# inserting into a full root splits it first

Figure 1: The root [5, 10, 20] is already full, so inserting 6 splits it first: the middle key 10 moves up into a new root, and the remaining keys divide into two children. 6 then lands in the left leaf, giving [5, 6].

This is the only way a B-Tree grows taller: splitting the root. Every other split happens one level below wherever it's triggered, which is exactly why the tree grows outward and upward evenly, instead of down one skewed branch the way an unbalanced BST can.

Why B-Trees Stay Shallow

Every node packing in more keys means fewer levels are needed to hold the same total number of keys. With a branching factor in the hundreds, which is typical for database indexes sized to a disk page, the difference compared to a binary tree is dramatic:

A billion-row index in 3-4 levels means 3-4 disk reads to find any row, versus ~30 for a balanced binary tree. That's the entire reason B-Trees exist.

B+ Trees: Data Only Lives in the Leaves

A B+ Tree changes one structural rule: internal nodes hold keys only for routing, every actual value is stored in a leaf, even if that key also appears in an internal node to guide searches. On top of that, every leaf keeps a pointer to the next leaf in sorted order.

Range Queries with Linked Leaves

This is the payoff for the extra next pointer: once you've found the first key in a range (a single O(log n) descent), every subsequent key in the range is just one pointer hop away, no re-descending the tree required.

class BPlusLeaf:
    def __init__(self, keys: list[int]) -> None:
        self.keys = keys
        self.next: "BPlusLeaf | None" = None    # the pointer a plain B-Tree doesn't have

def range_query(start_leaf: "BPlusLeaf | None", low: int, high: int) -> list[int]:
    result: list[int] = []
    leaf = start_leaf
    while leaf is not None:
        for key in leaf.keys:
            if low <= key <= high:
                result.append(key)
            elif key > high:
                return result       # sorted keys mean we can stop immediately
        leaf = leaf.next
    return result

leaf1 = BPlusLeaf([1, 3, 5])
leaf2 = BPlusLeaf([7, 9, 11])
leaf3 = BPlusLeaf([13, 15, 17])
leaf1.next = leaf2
leaf2.next = leaf3

print(range_query(leaf1, 5, 13))

[5, 7, 9, 11, 13]

This is exactly the query pattern behind SQL's BETWEEN, ORDER BY with a LIMIT, or pagination, all of which want a contiguous slice of sorted data rather than one specific key.

Where These Show Up

• Database indexes - PostgreSQL's default index type is a B-Tree; MySQL's InnoDB engine stores both primary and secondary indexes as B+ Trees
• Filesystems - NTFS uses B-Trees for directory indexing; Btrfs (B-Tree File System) is named directly after the structure it's built on
• Anywhere data outgrows memory - the same reasoning applies to any index that can't fully fit in RAM, minimizing levels means minimizing slow reads, whether that's a spinning disk, an SSD, or a network round-trip