Lesson 12 · Non-linear structures

B-Trees and B+ Trees

B-Trees are self-balancing search trees that store multiple keys per node, minimizing disk I/O for massive database indexes.

The Cost of Disk I/O

Standard binary search trees perform well in memory, but reading from a hard drive is orders of magnitude slower. If a BST is stored on disk, tracing a single path from root to leaf might trigger 20 or 30 separate disk reads, crippling performance.

Wide and Shallow

A B-Tree mitigates disk reads by packing dozens or hundreds of keys into a single node. When a node is read from disk, an entire block of keys is loaded into memory at once. This makes the tree incredibly wide and shallow, reducing the disk read depth drastically.

Key reference

Terms, operations, and practical uses

Database Foundations

Disk BlocksData on hard drives is read in fixed-size blocks (e.g., 4KB). B-Trees align node sizes with block sizes to maximize read efficiency.
High Branching FactorInstead of 2 children, a B-Tree node can have hundreds of children, keeping the tree exceptionally shallow.
Multi-Key NodesA single node stores multiple sorted keys, allowing binary search within the node itself after it is loaded into memory.

Tree Mechanics

Node SplittingWhen an insertion overflows a node's maximum capacity, it splits in half and promotes the median key to its parent.
Bottom-Up GrowthUnlike BSTs which grow downward, B-Trees grow upward. A new root is only created when the current root splits.
Underflow and MergingDuring deletion, if a node's key count drops below the minimum, it borrows from a sibling or merges with it.

The B+ Variant

Data at LeavesInternal nodes only store routing keys; the actual database records (or pointers to them) exist strictly in the leaf nodes.
Linked LeavesLeaf nodes maintain pointers to their adjacent siblings, forming a linked list across the bottom of the tree.
Sequential ScansBecause leaves are linked, fulfilling queries like SELECT * WHERE age > 20 is lightning fast without re-traversing the tree.

Code example

Search a multi-key B-tree node

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def search(self, k, node):
        i = 0
        while i < len(node.keys) and k > node.keys[i]:
            i += 1
        if i < len(node.keys) and k == node.keys[i]:
            return node
        elif node.leaf:
            return None
        else:
            return self.search(k, node.children[i])
root = BTreeNode(leaf=True)
root.keys = [10, 20, 30]
found = BTree().search(20, root)
print('Found Key' if found else 'Missing')

struct BTreeNode {
    vector<int> keys;
    vector<BTreeNode*> children;
    bool leaf;
};

BTreeNode* search(BTreeNode* node, int k) {
    int i = 0;
    while (i < node->keys.size() && k > node->keys[i]) i++;
    if (i < node->keys.size() && k == node->keys[i]) return node;
    if (node->leaf) return nullptr;
    return search(node->children[i], k);
}

class BTreeNode {
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    boolean leaf;
}

BTreeNode search(BTreeNode node, int k) {
    int i = 0;
    while (i < node.keys.size() && k > node.keys.get(i)) i++;
    if (i < node.keys.size() && k == node.keys.get(i)) return node;
    if (node.leaf) return null;
    return search(node.children.get(i), k);
}

Inputsearch for the displayed key

OutputFound Key

Example

Run the example step by step

Output

Node Splitting

B-Trees remain balanced from the bottom up. When a node exceeds its maximum key capacity during an insertion, it splits into two, and the median key is pushed up to the parent. If the root splits, the tree grows exactly one level taller, maintaining perfect balance.

The B+ Tree Variant

Most relational databases actually use B+ Trees. In this variant, all actual data pointers are stored only in the leaves, while internal nodes act purely as a navigational index. Furthermore, the leaf nodes are linked together, allowing blazing-fast sequential scans.