vault

B-Tree

26 min read

B-Tree

A B-tree is a self-balancing, multi-way (k-ary) search tree designed for external-memory (disk-resident) workloads. Each internal node stores up to 2t − 1 keys and has up to 2t children, where t ≥ 2 is the minimum degree parameter chosen so that one node fits in a single disk block (typically 4–16 KB). Every leaf sits at exactly the same depth — the tree is perfectly height-balanced — and that height is Θ(log_t n), dramatically shorter than a binary tree’s Θ(log_2 n). Search, insert, and delete each touch Θ(log_t n) nodes, which translates to Θ(log_t n) disk seeks — the only metric that matters when the data does not fit in memory. B-trees were introduced by Bayer and McCreight at Boeing Research Labs — their paper “Organization and Maintenance of Large Ordered Indices” appeared in Acta Informatica volume 1, pages 173–189, 1972 (DBLP record). Comer’s 1979 ACM Computing Surveys paper “The Ubiquitous B-Tree” gives the canonical taxonomy. Production usage is enormous: traditional Relational Database indexes (Oracle, MySQL InnoDB’s clustered index uses B+ Tree specifically; SQL Server, Db2), filesystems (NTFS metadata, ReiserFS, HFS+ on macOS, btrfs as the name advertises), and key-value stores all build on the B-tree family. The interview-relevant intuition is the same as the Red-Black Tree / AVL Tree one (“rebalance after every modification”) but applied at a different scale: one disk seek per level is the cost, so making the tree shorter at the cost of fatter nodes is the obviously correct trade.

1. Intuition — Trade Tall for Fat When Disk Is Slow

Random-access memory (RAM) is roughly five orders of magnitude faster than a spinning hard disk and still two to three orders of magnitude faster than a flash SSD. For an in-memory data structure, the cost of an operation is dominated by the number of comparisons and the number of cache misses. For a disk-resident structure, comparisons are essentially free; what dominates is the number of block transfers (also called I/O operations or disk seeks). A binary search tree of n = 10^9 keys has height ~30, meaning ~30 disk seeks per lookup. At 10 ms per seek, that is 300 ms per query — unusable for an OLTP database expecting 1 ms latencies.

The B-tree’s insight, due to Bayer and McCreight (1972), is to trade tree depth for node fan-out. Instead of a binary tree where each node holds one key and has two children, use a tree where each node holds many keys (say 100–500) and has many children (101–501). The height of such a tree is log_t n rather than log_2 n — for t = 100 and n = 10^9, that is roughly 4 instead of 30. Four disk seeks per query is feasible; thirty is not.

Why specifically 2t − 1 keys per node? The number is engineered so that one B-tree node fits in exactly one disk block (or one filesystem page, typically 4 KB or 8 KB or 16 KB). Read a node, that is one I/O operation; binary-search inside it, that is many comparisons but they are all in RAM and effectively free. The asymmetry between memory speed and disk speed is the entire reason B-trees exist.

A real-world analogy: imagine a card-catalog drawer in a library. Each drawer (B-tree node) holds many cards, sorted alphabetically. To find a book, you pull out the right drawer (one “disk seek”), then flip through it to find the title (cheap because it is in your hand). If each drawer held only one card, you would be pulling drawers out and slamming them shut all day. The B-tree is the multi-card drawer; the binary search tree is the single-card drawer. When pulling drawers is expensive, you want each drawer to do a lot of work.

The “B” in B-tree’s name has never been definitively settled — McCreight himself, asked directly about it years later, answered “Everybody does!” and recalled that the name came up over lunch when they needed a label but could not legally use “Boeing” without approval, so they shortened it to “B”; it could plausibly stand for “Boeing,” “balanced,” or for “Bayer” (the senior author), but McCreight said they “never did resolve whether there was one of those that made more sense than the rest” (per the Wikipedia summary of the McCreight interview). Suggested interpretations include Boeing, balanced, between, broad, bushy, and Bayer. Knuth’s TAOCP Volume 3 sidesteps the etymology by re-parameterizing the data structure (order = maximum number of children rather than keys); Comer’s 1979 survey notes the ambiguity good-naturedly.

2. The Five Properties

A B-tree of minimum degree t ≥ 2 satisfies:

  1. Every node holds between t − 1 and 2t − 1 keys, except the root, which can hold as few as 1 key (so an empty B-tree is a single-node tree with one key, not a special “empty” object).
  2. An internal node with k keys has exactly k + 1 children. The keys partition the children’s key-ranges: child i holds keys < key[i]; child k (the rightmost) holds keys > key[k−1].
  3. All leaves are at the same depth. This is the perfect-balance invariant; it is what makes a B-tree’s height bound work.
  4. Within a node, keys are stored in sorted order. This lets us binary-search inside a node.
  5. Internal nodes store both keys and child pointers; leaves store keys (and, depending on variant, satellite data).

The minimum-degree bound t − 1 ≤ keys ≤ 2t − 1 is the key invariant. The lower bound prevents nodes from becoming so empty that the tree’s branching factor degrades; the upper bound forces a split before a node would overflow. Many textbooks parameterize differently — some use the order m = 2t (so a node has between ⌈m/2⌉ − 1 and m − 1 keys); CLRS uses t; Knuth uses m. They are equivalent; the relationship is m = 2t.

2.1 Why t − 1 ≤ keys?

The lower bound matters because of the height bound (§6). If a node could legally hold one key, the tree could degenerate into something close to a binary search tree. Forcing every non-root node to carry at least t − 1 keys means every internal node has at least t children, which gives the tree a guaranteed branching factor of t — and that branching factor is what makes log_t n work.

2.2 Why 2t − 1 and not 2t?

The choice of 2t − 1 (rather than 2t) makes the split operation symmetric. A full node has exactly 2t − 1 keys. To insert a 2t-th key, you split: take the median key, push it up to the parent, and split the remaining 2t − 1 keys evenly into two new children of t − 1 keys each. That clean median split is impossible if a node held 2t keys (you would have a leftover key with nowhere to go). The off-by-one is engineered for elegance.

3. Tiny Worked Example — Insertion with Splits

Take t = 2, so each node holds 1–3 keys and has 2–4 children. (t = 2 is the smallest legal B-tree, equivalent to a 2-3-4 tree.) Insert 10, 20, 5, 6, 12, 30, 7, 17 into an initially empty B-tree.

3.1 Insert 10, 20

Both fit in the root.

[10, 20]

3.2 Insert 5

Sorted insertion in the root.

[5, 10, 20]

The root is now full (3 keys = 2t − 1).

3.3 Insert 6 — first split

The root is full. We must split before inserting. Median of [5, 10, 20] is 10. Promote 10 to a new root; split the rest:

        [10]
       /    \
   [5]      [20]

Now insert 6 normally — it goes in the left child:

        [10]
       /    \
   [5, 6]   [20]

3.4 Insert 12, 30

Both fit without splitting.

        [10]
       /    \
   [5, 6]   [20, 30]

Insert 12 — it goes in the right child (since 12 > 10):

        [10]
       /    \
   [5, 6]   [12, 20, 30]

3.5 Insert 7 — split again

The path for 7 leads to the left child [5, 6]. Not full — insert directly:

        [10]
       /    \
   [5, 6, 7]  [12, 20, 30]

Both leaves are now full. The next insertion that lands in either will trigger a split.

3.6 Insert 17 — pre-emptive split

The descent for 17 crosses the right child [12, 20, 30], which is full. CLRS’s elegant pre-emptive splitting rule: split full nodes on the way down, before descending into them. This guarantees that we never need to split on the way back up.

Split right child: median 20 promoted to parent.

        [10, 20]
       /   |    \
   [5,6,7] [12]  [30]

Now descend into the appropriate child for 17. Since 10 < 17 < 20, we descend into the middle child [12]. Insert 17:

        [10, 20]
       /   |    \
   [5,6,7] [12, 17]  [30]

The tree’s height after 8 insertions is 1; in a binary BST, those 8 keys would form a tree of height up to 7 (worst case) or about log_2 8 = 3 (best case). With t = 2, the B-tree’s branching saves us depth.

For a more dramatic example, with t = 100, a tree of height 4 can hold up to 100^4 ≈ 10^8 keys — eight zeros of fan-out compression compared to a binary tree of the same depth.

4. Algorithm — Search, Insert, Delete

A B-tree search is a top-down descent that, at each node, either finds the key or chooses the unique child whose key-range contains the target.

BTreeSearch(x, k):
    i := 1
    while i ≤ x.n and k > x.key[i]:
        i := i + 1
    if i ≤ x.n and k == x.key[i]:
        return (x, i)
    if x is leaf:
        return null
    DiskRead(x.child[i])
    return BTreeSearch(x.child[i], k)

Inside each node, the linear scan can be replaced with a binary search for O(log t) comparisons — but since t is at most a few hundred, the constant difference rarely matters. The disk read is the expensive operation; the in-node search is “free.”

4.2 Insert (with pre-emptive splitting)

BTreeInsert(T, k):
    r := T.root
    if r.n == 2t − 1:
        s := AllocateNode()
        T.root := s
        s.leaf := false
        s.n := 0
        s.child[1] := r
        BTreeSplitChild(s, 1)
        BTreeInsertNonfull(s, k)
    else:
        BTreeInsertNonfull(r, k)

BTreeInsertNonfull(x, k):
    i := x.n
    if x is leaf:
        while i ≥ 1 and k < x.key[i]:
            x.key[i+1] := x.key[i]
            i := i − 1
        x.key[i+1] := k
        x.n := x.n + 1
        DiskWrite(x)
    else:
        while i ≥ 1 and k < x.key[i]:
            i := i − 1
        i := i + 1
        DiskRead(x.child[i])
        if x.child[i].n == 2t − 1:
            BTreeSplitChild(x, i)
            if k > x.key[i]:
                i := i + 1
        BTreeInsertNonfull(x.child[i], k)

The pre-emptive split (split full children on the way down, even if you might not actually insert into them) is a CLRS design decision that simplifies the algorithm: you never recurse back up to fix a split. Production implementations sometimes use lazy splitting (only split on the way back up), which avoids unnecessary writes — at the cost of more complicated code.

4.3 Split (the heart of the algorithm)

BTreeSplitChild(x, i):
    z := AllocateNode()             # new sibling
    y := x.child[i]                 # full child being split
    z.leaf := y.leaf
    z.n := t − 1
    for j := 1 to t − 1:
        z.key[j] := y.key[j + t]    # copy upper half to z
    if not y.leaf:
        for j := 1 to t:
            z.child[j] := y.child[j + t]
    y.n := t − 1                    # y now holds lower half
    for j := x.n + 1 down to i + 1:
        x.child[j+1] := x.child[j]
    x.child[i+1] := z
    for j := x.n down to i:
        x.key[j+1] := x.key[j]
    x.key[i] := y.key[t]            # median of y promoted to parent
    x.n := x.n + 1
    DiskWrite(y)
    DiskWrite(z)
    DiskWrite(x)

Three disk writes per split. The median key (y.key[t]) goes up to the parent; the lower t − 1 keys stay in y; the upper t − 1 keys move to the new sibling z. Each new node has exactly t − 1 keys — at the lower bound but legal.

4.4 Delete (genuinely intricate)

Deletion is the hardest part of B-tree mechanics — CLRS devotes a full sub-chapter to it. The complications arise because, after deletion, a node might fall below the t − 1 minimum, requiring either a borrow from a sibling or a merge with a sibling. The shape of the cases mirrors the insert/split logic but in reverse.

The high-level recipe (CLRS Ch. 18.3):

  1. Find the key to delete. If it is in a leaf and the leaf has more than t − 1 keys, simply delete it.
  2. If the key is in an internal node, replace it with its in-order predecessor or successor (which lives in a leaf) and recurse to delete that predecessor/successor from the leaf.
  3. Pre-emptive fattening (analogous to pre-emptive splitting on insert). On the descent, if the next child has exactly t − 1 keys, fatten it first by either:
    • Borrowing a key from a sibling that has more than t − 1 keys (the sibling gives up one key, the parent’s separator key drops down, and the child’s new key takes the parent’s separator’s old position).
    • Merging the child with a sibling if both have exactly t − 1 keys: combine into a single 2t − 1-key node, pulling the separator down from the parent.

Production B-tree code (e.g., InnoDB) uses a more lenient delete — it allows underfull nodes for a while and consolidates lazily — because in OLTP workloads, deletes are rare and concurrent insertions tend to refill the tree.

5. Python Implementation (Pedagogical)

A simplified in-memory B-tree, ignoring disk I/O. Real B-trees serialize nodes to and from disk pages; this implementation focuses on the algorithmic logic.

from typing import Optional
 
class BTreeNode:
    __slots__ = ("keys", "children", "leaf")
 
    def __init__(self, leaf: bool = True) -> None:
        self.keys: list[int] = []
        self.children: list["BTreeNode"] = []
        self.leaf: bool = leaf
 
class BTree:
    def __init__(self, t: int = 2) -> None:
        if t < 2:
            raise ValueError("Minimum degree t must be ≥ 2")
        self.t = t                          # minimum degree
        self.root = BTreeNode(leaf=True)
 
    # -------- Search --------
    def search(self, k: int, node: Optional[BTreeNode] = None) -> Optional[tuple[BTreeNode, int]]:
        if node is None:
            node = self.root
        i = 0
        while i < len(node.keys) and k > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == k:
            return (node, i)
        if node.leaf:
            return None
        return self.search(k, node.children[i])
 
    # -------- Insert --------
    def insert(self, k: int) -> None:
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # Root is full — grow the tree taller by one level.
            s = BTreeNode(leaf=False)
            s.children.append(root)
            self._split_child(s, 0)
            self.root = s
            self._insert_nonfull(s, k)
        else:
            self._insert_nonfull(root, k)
 
    def _insert_nonfull(self, x: BTreeNode, k: int) -> None:
        i = len(x.keys) - 1
        if x.leaf:
            # Shift larger keys right and slot k in.
            x.keys.append(0)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == 2 * self.t - 1:
                self._split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self._insert_nonfull(x.children[i], k)
 
    def _split_child(self, x: BTreeNode, i: int) -> None:
        """Split x.children[i] (which is full) around its median key."""
        t = self.t
        y = x.children[i]
        z = BTreeNode(leaf=y.leaf)
        # Move upper t-1 keys of y into z.
        z.keys = y.keys[t:]                 # keys[t] is the median
        median = y.keys[t - 1]              # NOTE: convention mismatch with CLRS — see below
        # Re-do with CLRS-correct indexing:
        median = y.keys[t - 1]              # The t-th key (0-indexed: index t-1) is the median.
        z.keys = y.keys[t:]
        y.keys = y.keys[:t - 1]
        if not y.leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]
        # Insert z as x's child after y, and median as the separator key in x.
        x.children.insert(i + 1, z)
        x.keys.insert(i, median)
 
    # -------- Inorder for sanity checking --------
    def in_order(self, node: Optional[BTreeNode] = None) -> list[int]:
        if node is None:
            node = self.root
        result: list[int] = []
        for i, key in enumerate(node.keys):
            if not node.leaf:
                result.extend(self.in_order(node.children[i]))
            result.append(key)
        if not node.leaf:
            result.extend(self.in_order(node.children[len(node.keys)]))
        return result
 
 
# Demo: insert the §3 sequence.
bt = BTree(t=2)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
    bt.insert(k)
assert bt.in_order() == [5, 6, 7, 10, 12, 17, 20, 30]
assert bt.search(12) is not None
assert bt.search(99) is None
 
# Stress test: insert 1..1000 with t=10 — height should be small.
bt2 = BTree(t=10)
for k in range(1, 1001):
    bt2.insert(k)
assert bt2.in_order() == list(range(1, 1001))

The two non-obvious design choices in the implementation:

  1. Pre-emptive splitting in _insert_nonfull. Before descending into children[i], we check if it is full and split if so. This guarantees that the recursion never “comes back up” needing to split the parent — the parent always has room because we just made room in it.

  2. The median index t − 1 (0-indexed) versus t (1-indexed). CLRS uses 1-indexed arrays where the median is y.key[t] (the t-th of 2t − 1). In 0-indexed Python, this becomes y.keys[t - 1]. The off-by-one is a classic source of B-tree implementation bugs; getting it right requires being explicit about which indexing convention you are using.

6. Complexity — The Disk-Seek Analysis

6.1 Height bound

Claim: A B-tree of minimum degree t containing n keys has height h ≤ log_t((n + 1)/2).

Proof: The minimum number of keys in a B-tree of height h is achieved when every node holds the minimum (t − 1 keys, except the root with 1). Counting:

  • Level 0 (root): 1 node, ≥ 1 key.
  • Level 1: ≥ 2 children of root, each with ≥ t − 1 keys.
  • Level 2: ≥ 2t children (each level-1 node has ≥ t children), each with ≥ t − 1 keys.
  • Level i: ≥ 2 · t^(i-1) nodes, each with ≥ t − 1 keys.

Summing keys from level 0 to level h:

n ≥ 1 + (t − 1) · Σ_{i=1}^{h} 2 · t^{i-1}
  = 1 + 2(t − 1) · (t^h − 1) / (t − 1)
  = 1 + 2(t^h − 1)
  = 2 t^h − 1

Solving: t^h ≤ (n + 1)/2, i.e., h ≤ log_t((n + 1)/2). ∎

So for t = 100 and n = 10^9, h ≤ log_100(5 × 10^8) ≈ 4.35, meaning a 1-billion-key B-tree of fan-out 100 has height at most 4 or 5. That is at most 5 disk reads to find any key.

6.2 Per-operation costs

OperationCPU comparisonsDisk I/Os
SearchO(t · log_t n) = O(t log n / log t)O(log_t n)
InsertO(t · log_t n)O(log_t n)
DeleteO(t · log_t n)O(log_t n)

The CPU cost has a t factor because each node-internal scan touches up to 2t − 1 keys. With binary search inside a node, it becomes O(log_2 t · log_t n) = O(log_2 n) — same as a binary tree, asymptotically. What changes is the I/O count, which is the actual bottleneck for disk-resident data.

6.3 Why disk I/O is the only metric that matters

A modern HDD does ~100 random IOPS (I/O operations per second). A modern NVMe SSD does ~500K–1M random IOPS. RAM does ~10⁸–10⁹ random accesses per second. The cost gap is enormous: one disk seek equals tens of thousands or more in-memory operations. The B-tree’s design makes this explicit — the t factor pays for itself many times over because it shrinks the I/O count by a factor of log_2 t / log_2 2 = log_2 t.

For an SSD-based system with ~50 μs per random read and t = 200, n = 10^{12}: log_t n ≈ log_200(10^{12}) ≈ 5.2. Six reads × 50 μs = 300 μs per query. That is the foundation of every “production-grade key-value store” you have ever used.

6.4 Space

O(n) total. Per-node overhead is one block (4–16 KB) regardless of fill — typical fill ratio is ~70% in production (Knuth’s analysis suggests ln 2 ≈ 69% is the steady-state fill on uniform inserts, due to the splitting dynamics).

7. Variants and Comparison to In-Memory Trees

7.1 B+ Tree — the actual database index

The B+ tree (covered in its own note) puts all data in leaves only and links the leaves in a doubly-linked list. This makes range scans efficient (O(log n + k) for a range of k results) and is what every real database uses. The B-tree (this note) puts data at every level, which is conceptually cleaner but worse for range queries.

7.2 B* tree

B-stars require nodes to be at least 2/3 full (instead of 1/2 full as in B-trees). Splitting is delayed by attempting to redistribute keys with siblings before splitting; when two sibling pages are both full, both are split into three. Higher fill ratio, lower tree height, but more complex bookkeeping.

7.3 Red-Black Tree equivalence

A B-tree of minimum degree t = 2 (so 1–3 keys per node) is exactly a 2-3-4 tree, and Bayer’s 1972 paper on “symmetric binary B-trees” — what we now call red-black trees — explicitly proves that 2-3-4 B-trees can be encoded as binary trees with red/black coloring. This connection is why you should think of red-black trees as “B-trees pretending to be binary” and B-trees as “red-black trees set free to be wide.”

7.4 Comparison with Red-Black Tree and AVL Tree

PropertyB-tree (t = 100)Red-Black TreeAVL Tree
Storage targetDiskMemoryMemory
Height for n = 10^9~4~60 (2 log_2 n)~43 (1.44 log_2 n)
Cache misses per lookup~4~20 (one per level)~14
Implementation lines~500~150~120
Best workloadDisk-resident OLTPIn-memory ordered mapIn-memory read-heavy
Production examplesInnoDB, Postgres, NTFSJava TreeMap, C++ std::map, Linux CFSOCaml Map, some embedded

The high-level rule of thumb: if data fits in RAM, use a binary balanced BST (RB or AVL); if it spills to disk, use a B-tree (or B+ tree). The crossover is measured in tens of GB depending on workload.

7.5 LSM Tree as the modern alternative

For write-heavy workloads, modern systems often prefer LSM Trees (Log-Structured Merge trees: LevelDB, RocksDB, Cassandra, ScyllaDB, BigTable). LSM amortizes random writes into sequential writes, which is much faster on both spinning disks and SSDs at the cost of read amplification and compaction overhead. B-trees still dominate read-heavy and update-in-place workloads (relational OLTP).

8. Production Examples

MySQL InnoDB. Uses B+ Tree for both clustered (primary key) and secondary indexes. The MySQL glossary describes InnoDB indexes as “B-tree data structures” but notes “B-tree structures used by MySQL storage engines may be regarded as variants” (MySQL 8.0 glossary); the InnoDB physical-structure page confirms that “index records are stored in the leaf pages” (dev.mysql.com) — the leaf-only data placement that defines a B+ tree. Page size defaults to 16 KB, with sequential inserts leaving pages ~15/16 full and random inserts between 50% and 15/16 full. Jeremy Cole’s instrumentation of the InnoDB on-disk format (blog.jcole.us, 2013) measured ~468 records per leaf page and ~1,203 records per non-leaf page on a 16 KB page with a simple integer primary key — concrete numbers behind the abstract “fan-out”. The index height for a billion-row table on that schema is on the order of 3–4 levels.

PostgreSQL. Default index type is a B-tree (technically a Lehman-Yao concurrent B+ tree variant for lock-free reads). Page size 8 KB.

SQL Server, Oracle, Db2. All use B+ trees for indexes. The clustering vs non-clustering distinction is about whether row data lives at the leaf level (clustered) or whether the leaf points to row locations in a separate heap (non-clustered).

SQLite. B-tree (page-based, default 4 KB pages). The implementation in btree.c is a well-documented reference.

Filesystems. NTFS metadata uses B-trees. HFS+ and HFSX (older macOS) use B-trees for catalog and extents. ext4 has B-tree-like extent trees. ReiserFS and JFS were designed around B-trees. btrfs’s name is literally “B-tree filesystem”; every metadata structure (subvolumes, file extents, inode tree, checksum tree) is a B-tree.

Berkeley DB and LMDB. Embedded key-value stores using B-trees / B+ trees as the underlying ordered storage.

9. Pitfalls

9.1 Confusing B-tree, B+ tree, and B* tree

These names get used interchangeably in casual writing, but they are distinct. B-tree (this note): data at every level. B+ tree: data only in leaves, leaves linked in a list (this is what databases actually use). B tree*: nodes at least 2/3 full. When discussing “the database B-tree,” people almost always mean a B+ tree; clarify before writing code.

9.2 Choosing the minimum degree without measuring the disk page size

Setting t is a tuning decision, not a constant of nature. Match it to the storage system’s natural block size. For 4 KB pages and ~100-byte keys, 2t − 1 ≈ 40 keys per node is reasonable. Picking t too small wastes the page; picking t too large means each node spans multiple pages and a single read becomes multiple I/Os.

9.3 Off-by-one on the median index

CLRS uses 1-indexed arrays (y.key[t] is the median of 2t − 1 keys). 0-indexed languages need y.keys[t - 1]. Mixing the two conventions silently produces lopsided splits. Test with t = 2, t = 3, and a hand-traced example before trusting your implementation.

9.4 Forgetting to update parent pointers in a non-recursive implementation

A recursive B-tree (like the one in §5) does not need parent pointers because the recursion stack tracks the path. Iterative implementations need explicit parent pointers, and updating them on splits and merges is error-prone — especially when a split’s median promotion changes the parent’s key positions.

9.5 Concurrency

A naive B-tree implementation cannot handle concurrent reads and writes. Real databases use one of: Lehman-Yao B-link trees (each node has a “right link” to its rightmost sibling for race-free traversal during splits), lock coupling (hold lock on parent while acquiring lock on child, then release parent), or lock-free B+ trees (Bw-tree, used in SQL Server’s Hekaton). Concurrency turns the simple algorithm in this note into a research-paper-level engineering problem.

9.6 Not handling the root specially

The root is allowed to have fewer keys than other nodes (as few as 1). Forgetting this special case crashes on small trees or empty trees. The BTreeInsert outer wrapper grows the tree taller by one level when the root is full — that wrapper is doing the special handling; the recursion handles all non-root nodes uniformly.

9.7 Assuming log_t n reads is exactly the number of disk seeks

Modern operating systems and database engines cache recently-read pages in a buffer pool. The top levels of the B-tree (root, root’s children) are almost always cache-hot, so the actual I/O count is log_t n − cached_levels, often 0–2 reads instead of 4–5. Capacity planning ignores this at its peril (and conversely, claiming “B-trees do log_t n reads” without acknowledging caching is technically misleading in practice).

9.8 Treating in-memory B-trees as faster than RB/AVL

For in-memory data, a B-tree’s cache-friendliness can rival a binary BST’s, but the implementation complexity is far higher. Unless you have a specific reason (cache-oblivious tree research, persistent data structures, want to share code with a disk-resident form), use a Red-Black Tree or AVL Tree for in-memory ordered maps.

10. Diagram — A B-tree with t = 3

flowchart TD
    R["[20, 50]"]
    A["[5, 10, 15]"]
    B["[25, 30, 40]"]
    C["[55, 70, 90]"]
    R --> A
    R --> B
    R --> C

What this diagram shows. A 3-level B-tree of minimum degree t = 3 (so 2–5 keys per node). The root holds two keys, 20 and 50, partitioning the universe into three ranges: (−∞, 20), (20, 50), (50, +∞). Each child holds keys within its range. A search for 30 goes: read root, see 20 < 30 < 50, descend into middle child, find 30. Two reads total (root + middle child). For n in the millions and t in the hundreds, the tree height stays small (3–4), and any search resolves in 3–4 reads. Notice the leaf structure is uniform — every leaf is at the same depth (1 here) — which is the perfect-balance invariant. If we were to insert keys causing a leaf to overflow, that leaf splits, the median goes up to the parent, and (in the rare case the parent was already full) the split propagates upward. The root is the only node that can be split into a new level, growing the tree taller.

11. Common Interview Problems

SourceProblemConnection to B-tree
Systems-design interview”How does a database index work?”Direct: explain B+ tree, page-fitting, fan-out vs depth
Systems-design interview”Why are databases slow on SELECT WHERE non_indexed_col = X?”Index missing → full table scan instead of O(log n) B-tree lookup
Systems-design interview”Difference between clustered and non-clustered index?”Clustered: row data in B+ tree leaves. Non-clustered: leaves point to heap rows
LC 1825Finding MK AverageCould use a B-tree-backed multiset; in practice a balanced BST or segment tree
Codeforces / contest”Implement an order-statistic tree”A B-tree augmented with subtree-size counts
OSes / DB course”Explain how InnoDB stores rows”Clustered B+ tree on primary key
Distributed systems”Why doesn’t MongoDB use a hash table for indexes?”Range queries — B+ trees beat hash for ordered scans

For interviews, the most-asked B-tree questions are the systems-design ones above. Implementing a B-tree from scratch in a coding interview is rare (it would take an hour even for a fluent practitioner) but knowing the structure — fan-out, height, why it fits a page — is expected at any company doing database/storage work.

12. Open Questions

  • What is the optimal t for a modern NVMe SSD with 4 KB physical sector size and 16 KB filesystem page size? The answer involves modeling the SSD’s internal page size, FTL overhead, and read amplification.
  • How does the choice of B-tree vs LSM-tree shift as storage devices’ write/read symmetry changes? Persistent memory (Optane, CXL) blurs the line.
  • What is the right concurrency primitive for B-trees in 2026? Lehman-Yao B-link trees (1981) remain the standard, but modern lock-free designs (Bw-tree, Masstree) make different trade-offs.

Resolved

The Bayer & McCreight 1972 attribution is confirmed against DBLP’s record of Acta Informatica vol. 1, pages 173–189. The “B” etymology being unsettled is confirmed by McCreight’s own quoted recollection (see §1). The “typical fan-out” figures were previously stated as round-number rules of thumb (t = 100); §8 now cites Jeremy Cole’s measured InnoDB values (~468 records per leaf page, ~1,203 per non-leaf page on a 16 KB page with an integer primary key) as a concrete primary anchor. Remaining genuine uncertainty: the optimal fan-out for a given schema is workload- and key-size-dependent and not a fixed constant — the formula fan-out ≈ page_size / (key_size + pointer_size [+ row_size for B-trees]) is exact, but the “typical” values depend on which workload you pick as typical.

13. See Also

Graph View

Backlinks