B-Trees

Chapter 1: B-Tree Properties

A B-tree is defined by a single parameter called the minimum degree, written t (where t ≥ 2). This parameter controls how wide and short the tree is. Every rule about a B-tree flows from t.

Here are the five properties that define a B-tree. Memorize these — they are the entire specification.

Let us make this concrete with t = 3 (minimum degree 3). Each node has between 2 and 5 keys (t-1 = 2, 2t-1 = 5). Each internal node has between 3 and 6 children (t = 3, 2t = 6). The root can have as few as 1 key and 2 children.

Think of each node as a sorted array with signposts. If a node contains keys [10, 20, 30], it has four child pointers: one for keys < 10, one for keys between 10 and 20, one for keys between 20 and 30, and one for keys > 30. Each child pointer leads to an entire subtree of keys in that range.

The Routing Property in Detail

Property 4 — the multi-key routing rule — deserves careful examination. In a BST, each node has one key that divides the search space into two halves: left (≤ key) and right (≥ key). In a B-tree, each node has k keys that divide the search space into k+1 ranges:

This is exactly like a multi-way decision tree. At each node, you scan the keys to find which range your search key falls into, then descend into the corresponding child. With k keys per node, you make one (k+1)-way decision instead of k binary decisions — but you do it in a single disk read.

Think of it like a phone book directory. Each page of the directory has tab markers: A-C, D-F, G-I, ... Each tab tells you which section to flip to. The tabs are the keys; the sections are the children. A BST phone book would have one letter per page — 26 binary decisions to find any name. A B-tree phone book has all 26 letters on the first page — one decision, then flip directly to the right section.

Why the minimum fill constraint?

The rule that every non-root node must have at least t-1 keys is crucial. It guarantees that the tree stays balanced and short. If nodes could be arbitrarily empty, the tree could degenerate into a tall, skinny structure — just like an unbalanced BST. The minimum fill ensures every node is at least half full, which bounds the height.

Height bound

A B-tree with n keys and minimum degree t has height at most:

For t = 1001 and n = 10⁹: h ≤ log₁₀₀₁(500,000,000) ≈ 2.9. That is, a B-tree with minimum degree 1001 stores a billion keys in a tree of height 3. The root plus 2 more levels.

Choosing t in Practice

In theory, t can be any integer ≥ 2. In practice, t is chosen so that one node fills exactly one disk page. Here is the calculation:

With variable-length keys (like strings), the calculation is more complex. Databases typically store the maximum number of keys that fit in a page given the average key size, with overflow pages for very long keys.

The interactive visualization below lets you explore a B-tree with t = 3. Click the keys and child pointers to see the structure. Notice how every leaf is at the same depth, and every non-root node has at least 2 keys.

The Node Data Structure

Every B-tree node stores three things: a list of keys (sorted), a list of child pointers, and a flag indicating whether it is a leaf. Here is the concrete implementation:

python
class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []        # sorted list of keys
        self.children = []    # list of child node pointers
        self.leaf = leaf      # True if this is a leaf node
        self.n = 0            # number of keys currently stored

class BTree:
    def __init__(self, t):
        self.root = BTreeNode()
        self.t = t            # minimum degree
        # Every node has at most 2t-1 keys and 2t children
        # Every non-root node has at least t-1 keys

In a real database, each "node" is a disk page. The children list does not contain Python pointers — it contains page numbers. To access a child, you call disk_read(page_number), which loads the page from disk into RAM. This is the expensive operation — the one that B-trees minimize.

Deriving the Height Bound

Let us prove the height bound h ≤ log_t((n+1)/2). A B-tree of height h has:

For t = 1001, n = 10⁹: h ≤ log₁₀₀₁(500,000,000) = log(500,000,000) / log(1001) ≈ 8.7 / 3.0 ≈ 2.9. So the height is at most 3. With the root always in memory, you need just 2 disk reads to search a billion keys.

Chapter 2: Search

Searching a B-tree is a natural generalization of BST search. At each node, instead of comparing with one key and going left or right, you scan through multiple keys to find the right child pointer. The search descends level by level until it finds the key or reaches a leaf.

Here is the algorithm, step by step:

The Code

python
def b_tree_search(node, key):
    """Search for key in B-tree rooted at node.
    Returns (node, index) if found, None otherwise."""
    i = 0
    # Find the first key >= target
    while i < node.n and key > node.keys[i]:
        i += 1
    # Check if we found it
    if i < node.n and key == node.keys[i]:
        return (node, i)        # Found!
    # If leaf, key is not in tree
    if node.leaf:
        return None
    # Otherwise, read child from disk and recurse
    disk_read(node.children[i])  # ← THIS is the expensive operation
    return b_tree_search(node.children[i], key)

Cost Analysis

At each level, we do two things: scan through the keys in the node (CPU work), and read one child from disk (I/O work). The costs are:

The CPU cost is irrelevant — even O(t · log_t n) with t = 1000 is millions of times cheaper than the disk I/O. The number of disk reads, O(log_t n), is what matters. And the root node is almost always cached in RAM (it is accessed on every operation), so in practice you save one more disk read.

Amortized I/O: Why Caching Matters

In practice, the "O(log_t n) disk reads per search" is an overestimate. The root node is accessed on every search, so it stays permanently in the buffer pool (cache). Level-1 nodes are also accessed very frequently. With a modest buffer pool, the top 2-3 levels of the tree are always cached.

Let us calculate the memory needed to cache the top levels:

This is why database tuning guides always emphasize buffer pool sizing. With enough RAM to cache the internal levels of your hottest indexes, read performance becomes nearly optimal — close to 1 disk read per query regardless of dataset size.

What About Writes?

Search only reads. Insertion and deletion also write. Each modified page must eventually be flushed to disk. But writes can be deferred: mark the page "dirty" in the buffer pool and let a background process flush it later. Multiple modifications to the same page (common for hot nodes) are batched into a single write. This further amortizes the I/O cost.

The write-ahead log (WAL) ensures durability even when dirty pages have not been flushed. As long as the log entry is on disk, the modification is safe — even if the system crashes before the actual page is written. We will discuss WAL in detail in Chapter 7.

Worked Search Example

Consider searching for key 25 in this B-tree (t=3):

Now search for key 17 (not in tree):

The simulation below lets you search for a key in a B-tree. Watch how the search descends level by level, scanning keys at each node before choosing a child.

Chapter 3: Insertion

Inserting into a B-tree is more complex than BST insertion. You cannot just create a new leaf anywhere — that would violate the "all leaves at the same depth" property. Instead, every new key goes into an existing leaf. But what if the leaf is already full (has 2t-1 keys)?

The answer: split the full node before inserting. Splitting takes a full node with 2t-1 keys, pulls out the median key, and creates two nodes of t-1 keys each. The median key moves up to the parent.

Proactive Splitting: The CLRS Approach

Here is the clever part. CLRS describes a single-pass, top-down insertion. As you walk down the tree looking for the correct leaf, you split every full node you encounter on the way down — before you need to. This guarantees that when you arrive at the leaf, it is not full, so you can insert directly.

Why proactive? If you split only when needed (bottom-up), a split might push a key up to a parent that is also full, causing a cascade of splits back up the tree. With proactive top-down splitting, you never need to go back up — one pass down, done.

The Code

python
def b_tree_insert(tree, key):
    r = tree.root
    if r.n == 2 * tree.t - 1:  # root is full
        s = BTreeNode(leaf=False)
        tree.root = s
        s.children.append(r)
        split_child(s, 0)           # split old root
        insert_nonfull(s, key)
    else:
        insert_nonfull(r, key)

def insert_nonfull(node, key):
    i = node.n - 1
    if node.leaf:
        # Insert key into sorted position in 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
        node.n += 1
    else:
        # Find which child to descend into
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        # If child is full, split it first
        if node.children[i].n == 2 * t - 1:
            split_child(node, i)
            if key > node.keys[i]:
                i += 1
        insert_nonfull(node.children[i], key)

def split_child(parent, i):
    """Split parent.children[i] which must be full (2t-1 keys)."""
    t = tree.t
    full_node = parent.children[i]
    new_node = BTreeNode(leaf=full_node.leaf)
    # new_node gets the last t-1 keys
    new_node.keys = full_node.keys[t:]        # keys after median
    new_node.n = t - 1
    if not full_node.leaf:
        new_node.children = full_node.children[t:]  # children after median
    # Median key goes up to parent
    median = full_node.keys[t - 1]
    full_node.keys = full_node.keys[:t - 1]  # keep first t-1 keys
    full_node.n = t - 1
    if not full_node.leaf:
        full_node.children = full_node.children[:t]
    # Insert median and new child into parent
    parent.keys.insert(i, median)
    parent.children.insert(i + 1, new_node)
    parent.n += 1

Worked Example

Let us insert the keys 10, 20, 30, 40, 50, 60, 70, 80, 5, 15 into an initially empty B-tree with t = 3 (max 5 keys per node). Follow along with the simulation below.

The key moments in this sequence:

Split Cost Analysis

How often do splits happen? Each split produces two nodes of t-1 keys from one node of 2t-1 keys. Before the next split can happen at the same node, t more keys must be inserted there. So on average, one split occurs for every t insertions. With t = 1000, you get one split per 1000 inserts. Splits are rare events.

When a split does happen, it requires:

• 1 disk read (the full node, if not already in memory)
• 2 disk writes (the two new half-nodes)
• 1 disk write (the parent, to add the median key)

Total: 4 disk I/Os for a split. Amortized over t insertions, that is 4/t extra I/Os per insert — negligible for large t.

Insertion Order and Tree Shape

Unlike BSTs, B-trees always produce balanced trees regardless of insertion order. Insert 1, 2, 3, ..., n in sorted order into a BST and you get a linked list (height n). Insert the same sequence into a B-tree and you get a perfectly balanced tree (height log_t n). The proactive splitting mechanism redistributes keys as the tree grows, maintaining balance automatically.

However, insertion order does affect space utilization. Sequential insertions into a B-tree produce nodes that are about half full (each split creates two minimum-fill nodes). Random insertions produce nodes that are about 69% full. Some databases (like PostgreSQL) detect sequential insert patterns and use a special "fast path" that fills pages more aggressively.

The Bulk Loading Optimization

If you have a large dataset and want to build a B-tree from scratch, inserting keys one at a time is wasteful. Each insert does a full root-to-leaf traversal. For n keys, that is O(n · log_t n) total disk I/Os.

The better approach is bulk loading: sort the keys first, then build the tree bottom-up by filling leaf pages to capacity, then creating internal pages over them. This requires only O(n/B) I/Os (one pass through the sorted data, writing full pages sequentially).

This is why database import tools (like MySQL's LOAD DATA INFILE or PostgreSQL's COPY) are dramatically faster than individual INSERT statements. They sort the data and bulk-load the B-tree indexes.

Chapter 4: Deletion

Deletion is the hardest operation in B-trees. The problem: after removing a key, a node might have fewer than t-1 keys, violating the B-tree property. We must fix this, and the fix depends on where the key is and what the neighboring nodes look like.

There are three cases, and each case has sub-cases. Let us work through all of them.

Case 1: Key is in a leaf

This is the simplest case. If the leaf has more than t-1 keys, just remove the key. Done. The node still satisfies the minimum-fill constraint.

Case 2: Key is in an internal node

We cannot just remove a key from an internal node — it would leave the node with one fewer key than child pointers, breaking the structure. Instead, we replace the key with its predecessor or successor and delete that instead.

Case 3: Key is not yet found, descending

We are still searching for the key and about to descend into child[i]. But child[i] has only t-1 keys — the minimum. If we delete from it, it might underflow. So before descending, we ensure the child has at least t keys.

Just like insertion uses proactive splitting, deletion uses proactive fixing on the way down. Before descending into any child, ensure it has at least t keys (not just t-1). This guarantees we never need to backtrack.

The Code

python
def b_tree_delete(node, key):
    i = 0
    while i < node.n and key > node.keys[i]:
        i += 1

    if i < node.n and key == node.keys[i]:
        if node.leaf:
            # Case 1: key in leaf — just remove
            node.keys.pop(i)
            node.n -= 1
        else:
            # Case 2: key in internal node
            delete_internal(node, i)
    else:
        if node.leaf:
            return  # key not in tree
        # Case 3: key not found yet, must descend
        # Ensure child[i] has ≥ t keys before descending
        if node.children[i].n == t - 1:
            fix_child(node, i)
        # Recurse (index may have changed after merge)
        b_tree_delete(node.children[i], key)

def delete_internal(node, i):
    key = node.keys[i]
    if node.children[i].n >= t:       # Case 2a
        pred = get_predecessor(node, i)
        node.keys[i] = pred
        b_tree_delete(node.children[i], pred)
    elif node.children[i+1].n >= t:  # Case 2b
        succ = get_successor(node, i)
        node.keys[i] = succ
        b_tree_delete(node.children[i+1], succ)
    else:                              # Case 2c
        merge_children(node, i)
        b_tree_delete(node.children[i], key)

Summary of All Deletion Cases

The recurring theme: never operate on a node that is at the minimum. Before you do anything, make sure the target node has room. For insertion, "room" means not full (split if full). For deletion, "room" means above minimum (steal or merge if at minimum).

Worked Deletion Example

Let us walk through a concrete deletion sequence on a B-tree with t=3. Start with this tree containing keys [3, 5, 7, 10, 12, 15, 18, 20, 22, 25, 28, 30, 33, 35, 38, 40]:

Delete 7 (Case 1 — key in leaf with enough keys): The leaf [3,5,7] has 3 keys (> t-1 = 2). Just remove 7. Result: [3,5].

Delete 15 (Case 2a — key in internal, left child has enough keys): 15 is in the internal node [10,15]. The left child's subtree has predecessor 12. Replace 15 with 12, then delete 12 from its leaf. But wait — the leaf [12] has only 1 key (= t-1). We need Case 3. Before descending, check siblings. The left sibling [3,5] has 2 keys (= t-1) and the right sibling [18] has 1 key (= t-1). Both at minimum, so merge: combine [12] + 15 + [18] = [12,15,18]. Now delete 15 from this merged leaf. Result: internal becomes [10], children are [3,5] and [12,18].

Delete 20 (Case 2c — key in internal, both children have t-1 keys): 20 is the root key. Left child [10] and right child [30,35] — left has 1 key (t-1), but right has 2 keys. So Case 2b applies: take the successor (22), replace 20 with 22, delete 22 from the right subtree.

Each deletion case builds on the same principle: ensure you have enough keys to work with before you operate. This is the B-tree's version of "measure twice, cut once."

Chapter 5: B-Tree Showcase

This is the payoff. The simulation below is a fully interactive B-tree. You choose the minimum degree t. You insert and delete any key. You watch every split and merge in real time. The tree shows node utilization, current height, and a running count of disk reads.

Things to try:

• Insert 1, 2, 3, ..., 20 in order with t=2. Count the splits.
• Now try the same with t=4. Far fewer splits — the wider nodes absorb more keys before splitting.
• Insert 20 random keys, then delete them one by one. Watch merges reduce the tree height.
• Try to make the tree as tall as possible with t=2. How many keys do you need?

Understanding Node Utilization

After many random insertions, most nodes are between half-full and completely full. This is not an accident — the split mechanism guarantees it. When a node with 2t-1 keys splits, it produces two nodes with t-1 keys each. Those nodes are exactly at the minimum. Subsequent insertions fill them back up. The average node utilization in a random B-tree is about ln(2) ≈ 69% — a result from Knuth's analysis.

This means a B-tree wastes about 31% of its allocated space on average. In practice, this is a good tradeoff: the wasted space buys us room for future insertions without immediate splits, and 69% utilization is much better than the 50% worst case.

Disk Reads Per Operation

Watch the "Disk reads (last op)" counter as you insert and delete. For a tree of height h:

The key insight: even in the worst case, every operation does at most O(h) = O(log_t n) disk I/Os. With t = 1000 and n = 10⁹, that is 3 reads and 3 writes. The actual CPU work per node (scanning keys, shifting elements) is trivial in comparison.

Chapter 6: B+ Trees

B-trees as described by CLRS store data (or pointers to data) at every node — both internal and leaf. This is fine in theory, but real databases almost universally use a variant called the B+ tree. The difference is simple but profound.

Why B+ trees?

Three reasons, all practical:

1. Internal nodes are smaller. Since internal nodes do not carry data payloads, they carry only keys and pointers. More keys fit in a single disk page, so the branching factor is higher, so the tree is shorter. If each record is 100 bytes but each key is 8 bytes, a B-tree internal node wastes 92% of its space on data you do not need during search.

2. Range queries are fast. Want all records with keys between 50 and 200? In a B+ tree, find 50 (follow the tree down to the leaf), then walk the leaf linked list until you pass 200. You never need to go back up to the internal nodes. In a standard B-tree, range queries require an inorder traversal that bounces between internal and leaf nodes.

3. Predictable I/O. Every search touches exactly the same number of internal nodes plus one leaf. There is no "lucky" case where the key happens to be in an internal node at level 2 instead of a leaf. This makes query planning and caching more predictable.

Notice that in the B+ tree, the key 30 appears in both an internal node and a leaf. Internal copies are just signposts — the leaf copy is where the actual data record lives.

Counting the Advantage

Let us do the math to see why B+ trees have a higher branching factor. Suppose each key is 8 bytes, each child pointer is 8 bytes, and each data record is 200 bytes. Page size is 4 KB (4096 bytes).

For a dataset of 100 million records:

Range Query Walkthrough

Suppose we want all keys in the range [15, 45] from a B+ tree. The algorithm:

B+ Tree Insertion and Deletion

B+ tree insertion works like B-tree insertion with one twist: when a leaf splits, the median key is copied up to the parent (not moved). In a B-tree, the median leaves its original node. In a B+ tree, the median stays in the right leaf (because all keys must be in leaves) and a copy goes to the parent as a routing signpost.

Deletion in a B+ tree is also slightly different. If you delete a key that appears as a signpost in an internal node, the internal copy might become stale. Some implementations leave stale signposts (they still correctly route searches). Others update the signpost to the new minimum of the right subtree. Both approaches are valid — stale signposts just waste a tiny amount of space.

Real-World Page Layout

Here is what a B+ tree page looks like in a real database (InnoDB-style, 16 KB page):

With a 16 KB page, 8-byte keys, and 6-byte child pointers, an internal node holds about 16,000 / 14 ≈ 1,143 keys — so the branching factor is about 1,144. Two levels of internal nodes can index 1,144² ≈ 1.3 million leaf pages. If each leaf holds 100 rows, that is 130 million rows reachable in 3 disk reads.

Chapter 7: B-Trees in Databases

Every time you run a SQL query with a WHERE clause on an indexed column, a B-tree (or B+ tree) is doing the work. Let us look at how the three most popular open-source databases use them.

MySQL InnoDB: Clustered B+ Tree Index

InnoDB stores the entire table as a B+ tree, ordered by the primary key. This is called a clustered index — the leaf nodes of the B+ tree contain the actual row data, not just pointers to rows stored elsewhere.

Secondary indexes in InnoDB are also B+ trees, but their leaves store the primary key (not the row data). A secondary index lookup requires two B+ tree searches: one to find the primary key in the secondary index, then another to find the row in the clustered index. This is called a double lookup or "bookmark lookup."

PostgreSQL: Heap + B-Tree Indexes

PostgreSQL takes a different approach. The table data lives in a heap — an unordered pile of row pages. Indexes are separate B-tree structures whose leaves contain tuple IDs (TIDs), which are (page number, offset) pointers into the heap.

Every index lookup in PostgreSQL requires a B-tree search followed by a heap page fetch. This seems slower than InnoDB's clustered index, but it has an advantage: secondary indexes point directly to the heap (one B-tree search), whereas InnoDB's secondary indexes require a double lookup.

SQLite: B-Tree for Tables, B+ Tree for Indexes

SQLite uses plain B-trees (not B+) for tables (which it calls "table B-trees") and B+ trees for indexes. Each database is a single file divided into fixed-size pages (default 4096 bytes). Each page is one B-tree node. The page size is the node size — this is literally what we meant by "size nodes to fit one disk page."

The Buffer Pool

Databases do not read from disk on every B-tree node access. They maintain a buffer pool — a cache of recently-accessed disk pages in RAM. When a B-tree search needs a node, it first checks the buffer pool. If the page is there (a "cache hit"), no disk I/O happens. Only on a "cache miss" does the database actually read from disk.

The root node of every frequently-used index is virtually always in the buffer pool (it is accessed on every query). Internal nodes near the root are also likely cached. In practice, only the leaf node access triggers a disk read. For a B+ tree with height 4, that means 3 cache hits and 1 disk read — blazing fast.

Concurrency: B-Tree Locking

In a multi-threaded database, many transactions access the B-tree simultaneously. Without coordination, two threads might try to split the same node, corrupting the tree. Databases use latches (lightweight locks) to protect B-tree pages.

The naive approach — lock the entire tree for every operation — destroys concurrency. The standard technique is latch crabbing (also called "latch coupling"):

A node is "safe" if the current operation cannot cause a structural change (split or merge) at that node. For search, every node is safe (no modifications). For insert, a node is safe if it has fewer than 2t-1 keys (room for one more without splitting). For delete, a node is safe if it has more than t-1 keys (room to lose one without merging).

Latch crabbing ensures that at most two levels are locked at any time. This allows operations on different parts of the tree to proceed in parallel — a reader in the left subtree does not block a writer in the right subtree.

Write-Ahead Logging and B-Trees

What happens if the database crashes while splitting a B-tree node? A split modifies three pages: the full node, the new sibling, and the parent. If the system crashes after writing the sibling but before updating the parent, the tree is corrupted — the new sibling is an orphan.

Databases solve this with Write-Ahead Logging (WAL). Before modifying any B-tree page, the database writes a log entry describing the change. If a crash occurs, the recovery process replays the log to complete or undo partial operations. The log is append-only and sequential, so writing it is fast.

An alternative approach is copy-on-write (COW), used by LMDB and btrfs. Instead of modifying pages in place, write new pages and atomically update the root pointer. This eliminates the need for WAL but increases write amplification (every modification creates new pages all the way up to the root).

COW trades write amplification for simplicity and free snapshots. LMDB is single-writer (no write concurrency) but achieves phenomenal read performance because readers never need locks — they just follow the root pointer they started with, which always points to a consistent snapshot.

Compaction and Fragmentation

Over time, B-tree pages become fragmented. Deletions leave gaps. Splits create half-full pages. Pages that were once adjacent on disk may become scattered. This causes two problems:

Internal fragmentation: Pages are not fully utilized. A page with 50% utilization wastes half its space. Databases periodically run OPTIMIZE TABLE (MySQL) or REINDEX (PostgreSQL) to rebuild the B-tree from scratch, compacting all pages.

External fragmentation: Logically adjacent leaf pages (e.g., keys 1-100 and keys 101-200) may be physically scattered across the disk. Sequential range scans become random I/O. SSDs mitigate this (random reads are nearly as fast as sequential), but HDDs suffer badly.

Choosing the Right Index

Not every column needs an index, and not every index should be a B-tree. Here is a decision guide:

Each secondary index adds overhead to every INSERT, UPDATE, and DELETE on the table (the index must be updated too). A table with 5 indexes effectively writes 6 times for every row modification: once to the table plus once to each index. This is why DBAs are cautious about over-indexing.

Chapter 8: Interview Arsenal

Cheat Sheet

Design Questions

Coding Drills

Complexity Comparison

Worked Design Problem: "Design a Key-Value Store"

This is a common system design interview question. Here is a staff-engineer-grade walkthrough using B-trees.

Step 1: Choose the data structure. We need point lookups AND range scans, so hash tables are out. B+ tree is the standard choice. LSM-tree is an alternative if writes dominate reads.

Step 2: Page size. Use 16 KB pages (InnoDB default). With 32-byte keys and 8-byte child pointers, an internal page holds ~400 keys. Branching factor ≈ 400.

Step 3: Estimate tree dimensions.

Step 4: Write path. PUT = search (4 reads) + write leaf page (1 write) + WAL entry (1 sequential write). The WAL write is sequential (fast). The page write may be deferred (dirty page in buffer pool, flushed later). Amortized write latency: ~0.5ms on SSD. Under 5ms target.

Step 5: Buffer pool sizing. Cache the top 2 levels (41 pages = 656 KB) plus hot leaf pages. With 1 GB of RAM for the buffer pool, you can cache ~65,000 pages = 1% of all pages. After warm-up, the hot set gives >90% hit rate.

Step 6: Crash recovery. WAL with checkpointing. On crash, replay WAL from last checkpoint. Recovery time proportional to WAL length since last checkpoint (seconds to minutes).

Complete B-Tree Implementation

Here is a complete, working Python B-tree that you can copy and run. Every function maps directly to the pseudocode in CLRS. Study the split_child and delete functions — these are the two that interviewers care about most.

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

class BTree:
    def __init__(self, t):
        self.root = BTreeNode()
        self.t = t  # minimum degree (must be ≥ 2)

    def search(self, key, node=None):
        """Return (node, index) or None."""
        if node is None:
            node = 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 (node, i)
        if node.leaf:
            return None
        return self.search(key, node.children[i])

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # Root is full — grow the tree
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self.root = new_root
            self._split_child(new_root, 0)
            self._insert_nonfull(new_root, key)
        else:
            self._insert_nonfull(root, key)

    def _split_child(self, parent, i):
        """Split parent.children[i], which must be full."""
        t = self.t
        full = parent.children[i]
        new = BTreeNode(leaf=full.leaf)
        # Median key
        median = full.keys[t - 1]
        # Right half goes to new node
        new.keys = full.keys[t:]
        full.keys = full.keys[:t - 1]
        if not full.leaf:
            new.children = full.children[t:]
            full.children = full.children[:t]
        # Insert median into parent
        parent.keys.insert(i, median)
        parent.children.insert(i + 1, new)

    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 inorder(self, node=None):
        """Return all keys in sorted order."""
        if node is None:
            node = self.root
        result = []
        for i in range(len(node.keys)):
            if not node.leaf:
                result.extend(self.inorder(node.children[i]))
            result.append(node.keys[i])
        if not node.leaf:
            result.extend(self.inorder(node.children[-1]))
        return result

# Usage:
tree = BTree(t=3)
for key in [10, 20, 30, 40, 50, 60, 70, 80, 5, 15]:
    tree.insert(key)
print(tree.inorder())
# Output: [5, 10, 15, 20, 30, 40, 50, 60, 70, 80]

print(tree.search(30))   # (<node>, 0) — found!
print(tree.search(99))   # None — not found

Notice the key design decision in _insert_nonfull: we check if the child is full before descending. If it is, we split it immediately and then decide which of the two resulting children to descend into. This is the proactive splitting that guarantees a single downward pass.

Verification: How to Check B-Tree Invariants

When implementing or debugging a B-tree, you need a function that verifies all five properties. Here is a verification checklist you can turn into code:

python
def verify_btree(tree):
    """Verify all B-tree properties. Raises AssertionError if violated."""
    t = tree.t

    def check(node, min_key, max_key, depth, leaf_depth):
        # Property 3: keys are sorted
        for i in range(len(node.keys) - 1):
            assert node.keys[i] < node.keys[i+1], f"Keys not sorted: {node.keys}"

        # Property 1: key count bounds
        if node != tree.root:
            assert len(node.keys) >= t - 1, f"Underflow: {len(node.keys)} < {t-1}"
        assert len(node.keys) <= 2 * t - 1, f"Overflow: {len(node.keys)} > {2*t-1}"

        # Property 4: keys within bounds from ancestors
        for k in node.keys:
            assert min_key < k < max_key, f"Key {k} outside [{min_key},{max_key}]"

        if node.leaf:
            # Property 5: all leaves at same depth
            if leaf_depth[0] is None:
                leaf_depth[0] = depth
            assert depth == leaf_depth[0], f"Leaf at depth {depth}, expected {leaf_depth[0]}"
        else:
            # Property 2: k keys = k+1 children
            assert len(node.children) == len(node.keys) + 1
            # Recurse into children with tightened bounds
            bounds = [min_key] + node.keys + [max_key]
            for i, child in enumerate(node.children):
                check(child, bounds[i], bounds[i+1], depth + 1, leaf_depth)

    check(tree.root, float('-inf'), float('inf'), 0, [None])
    print("All B-tree properties verified! ✓")

Run this after every insert and delete during development. It catches bugs immediately. The function checks all five properties in O(n) time by visiting every node once.

Five Dimensions of B-Tree Mastery

Chapter 9: Connections

B-trees sit at the intersection of algorithms and systems. Understanding them connects you to a web of related ideas.

Where B-Trees Came From

Where B-Trees Lead

Modern Research: Beyond Traditional B-Trees

B-trees have been the dominant index structure for 50 years, but researchers continue to push the boundaries:

Learned Indexes (Kraska et al., 2018): Instead of a tree of comparisons, use a machine learning model to predict where a key is. A neural network trained on the data distribution can predict the position of any key in a sorted array with high accuracy. The prediction replaces the tree traversal. On read-only workloads with static data, learned indexes can be 1.5-3x faster than B-trees while using 10-100x less memory. The challenge: handling inserts, deletes, and distribution shifts. Active research area.

Bw-Trees (Levandoski et al., 2013): Lock-free B-trees for multi-core systems. Instead of latching individual pages, Bw-trees use compare-and-swap (CAS) operations and delta chains. Each modification creates a small delta record that is prepended to a page's chain. Periodically, deltas are consolidated into a new base page. Used in SQL Server Hekaton and Azure Cosmos DB.

ALEX (Ding et al., 2020): An "adaptive learned index" that handles inserts by combining learned models with gapped arrays. It self-tunes its structure based on the workload, gradually reshaping itself as the data distribution evolves. Achieves near-learned-index read performance with practical insert support.

Write-Optimized Indexes: B^ε-trees (Brodal & Fagerberg, 2003) add write buffers to each node, batching writes and flushing them down periodically. They achieve O(log_B n / B^ε) amortized insert cost — exponentially better than B-trees for write-heavy workloads. TokuDB (now PerconaFT) implements this as "Fractal Tree Indexes."

The Bigger Picture

B-Tree vs LSM-Tree: The Great Debate

The most important alternative to B-trees is the Log-Structured Merge-Tree (LSM-tree), invented by Patrick O'Neil in 1996. It powers Cassandra, RocksDB, LevelDB, HBase, and many modern "NoSQL" databases. The tradeoff is fundamental:

When to choose B-trees: Read-heavy workloads, range queries, predictable latency requirements, traditional OLTP (banking, e-commerce). This is most workloads.

When to choose LSM-trees: Write-heavy workloads (logging, time-series, event streams), write-once-read-rarely patterns, workloads where sequential I/O matters (HDDs, distributed storage). Also when you need simple crash recovery (immutable files are easier to recover than in-place-modified pages).

Modern systems increasingly blur this line. RocksDB is an LSM-tree that adds Bloom filters and prefix seeking to improve read performance. WiredTiger (MongoDB's engine) supports both B-tree and LSM modes. Research systems like Dostoevsky and Monkey allow tuning the LSM structure along a continuum between pure LSM and pure B-tree behavior.

The Landscape of Tree-Based Indexes

What We Covered

In this lesson you learned:

• The problem: Disk I/O is 10 million times slower than RAM access, making BST height the bottleneck.
• The solution: B-trees maximize branching factor to minimize height (and thus disk reads).
• The five properties: Degree t, sorted keys, k+1 children, same-depth leaves, minimum fill.
• Search: Scan keys at each node, descend to the right child. O(log_t n) disk reads.
• Insertion: Proactive top-down splitting ensures single-pass insertion.
• Deletion: Three cases with proactive fixing (steal or merge) on the way down.
• B+ trees: The practical variant — data in leaves only, leaves linked for range scans.
• Databases: How MySQL, PostgreSQL, and SQLite use B-trees. Buffer pools. WAL. Clustered vs secondary indexes.

Recommended Reading

• CLRS Chapter 18 — the definitive textbook treatment of B-trees. Focus on the split and merge pseudocode.
• "Designing Data-Intensive Applications" by Martin Kleppmann — Chapter 3 covers B-trees vs LSM-trees with excellent production context.
• "Database Internals" by Alex Petrov — deep dive into how B-trees are implemented in real databases. Covers page formats, buffer pools, WAL, concurrency.
• "The Case for Learned Index Structures" by Kraska et al. (2018) — the paper that started the learned index revolution.
• Bayer & McCreight, "Organization and Maintenance of Large Ordered Indices" (1972) — the original B-tree paper. Surprisingly readable.

"The art of programming is the art of organizing complexity, of mastering multitude and avoiding its bastard chaos as effectively as possible." — Edsger Dijkstra