vault

B+ Tree

27 min read

B+ Tree

A B+ tree is a refinement of the B-Tree in which all data is stored only at the leaves — internal nodes serve purely as a routing index — and the leaves are linked together in a doubly-linked list for efficient sequential and range traversal. Two changes; both decisive. They make the B+ tree, not its predecessor the B-tree, the data structure underneath every general-purpose relational database index in production: MySQL InnoDB’s clustered and secondary indexes (the InnoDB physical-structure documentation states that “index records are stored in the leaf pages” — the leaf-only data placement that defines a B+ tree, per dev.mysql.com; Jeremy Cole’s reverse-engineered diagrams confirm the doubly-linked leaf list, per blog.jcole.us, 2013), PostgreSQL’s default btree access method (a Lehman-Yao B-link variant, per the nbtree README), SQL Server’s clustered index, Oracle’s index-organized tables, SQLite’s table B-trees, and many file systems. A point lookup (find one row by key) costs O(log_t n) disk reads, the same as a B-tree. A range scan (find all rows where age BETWEEN 30 AND 40) costs O(log_t n + k) where k is the number of returned rows — much better than a B-tree’s O(k log_t n) for the same range, because once the first matching leaf is located, subsequent leaves can be reached by following the linked-list pointers rather than re-descending from the root. Most OLTP workloads — short writes, range reads, ordered scans, index-only queries — line up with exactly the B+ tree’s strengths, which is why the design has dominated since the late 1970s. The B+ variant was popularized by Knuth in TAOCP Volume 3 (1973) and Comer’s 1979 ACM Computing Surveys paper “The Ubiquitous B-Tree,” though variants of the idea predate both.

1. Intuition — Two Surgical Changes to a B-Tree

To understand why the B+ tree exists, start with what the B-Tree gives you and what it does not.

A B-tree gives you O(log_t n) point lookups on disk-resident data, where t is engineered so that one node fits in one disk block. That is the foundational achievement. But two practical pain points remain:

Pain point 1: Range queries are awkward. A B-tree stores data at every level. To enumerate all keys in a range [lo, hi], you cannot just walk leaves — some matching keys live on internal nodes. You have to perform an in-order traversal of the entire subtree spanning the range, which means recursive descent, frequent jumps between nodes, and, in the worst case, O(k log_t n) disk seeks for k matches because the in-order walk repeatedly leaves and re-enters the path.

Pain point 2: Internal nodes carry data. This wastes precious bytes in the routing layer. If each B-tree node holds, say, 16 KB and a row is 200 bytes, then you can fit ~80 rows per page — but those rows include both keys and values. If we removed the values from internal nodes, we could fit several times more keys per node, raising the fan-out and lowering the tree’s height. Higher fan-out = fewer disk seeks. This is a free win as long as we are willing to keep all values in the leaves.

The B+ tree fixes both pain points with two changes:

  1. All values live in the leaves only. Internal nodes contain only keys and child pointers. The internal layer becomes a pure routing index — a sparse “table of contents” pointing into the dense leaf layer.
  2. Leaves are doubly-linked in key order. After locating the first leaf containing lo via descent from the root (one O(log_t n) pass), enumerate matching keys by walking right along the leaf list until exceeding hi. No re-descent, no path-popping — just a flat sequential scan.

These are minor topology changes that produce major practical improvements. Pain point 1 becomes O(log_t n + k/B) disk reads (where B is the number of keys per leaf page) — essentially “find first match, then read consecutive pages.” Pain point 2 means internal nodes pack more keys per page, lowering height. For a typical setup — 16 KB pages, 50-byte keys, 8-byte child pointers, 200-byte rows — the B+ tree’s fan-out at the internal level is ~16384 / 58 ≈ 280 keys per node, vs the B-tree’s ~16384 / 250 ≈ 65 (because B-tree internal nodes also carry rows). That is roughly 4× the fan-out, which translates to roughly log_4 = 2 shorter trees — billions-row tables fit in 3-level instead of 5-level B+ trees.

A real-world analogy: a B-tree is a multi-volume encyclopedia where every volume contains some entries. A B+ tree is a separately indexed encyclopedia: the index volumes contain only key terms and “see volume X, page Y” pointers; the content volumes contain the entries; and the content volumes are physically arranged in alphabetical order with each volume’s last page noting “continued in next volume.” Looking up “Aardvark to Zebra” entries means consulting the index once to find Aardvark’s volume, then reading volumes left-to-right until you finish Zebra. That linear-walk capacity is precisely what range queries exploit.

2. The Five Properties

A B+ tree of minimum degree t ≥ 2 (or “order m = 2t”) satisfies:

  1. Internal nodes hold between t − 1 and 2t − 1 keys, just like a B-tree. The root may hold as few as 1 key.
  2. Internal nodes hold only keys and child pointers — no satellite data. Each k-key internal node has exactly k + 1 children.
  3. Leaves hold the data. Each leaf stores (key, value) pairs (or (key, row pointer) for non-clustered indexes). Leaves obey the same t − 1 ≤ keys ≤ 2t − 1 count bound. Leaves do not have child pointers; the “child” slot is repurposed for the linked-list sibling pointer.
  4. Leaves are linked in a doubly-linked list in key order. Some implementations use a singly-linked list for forward-only scans; doubly-linked allows reverse iteration (ORDER BY key DESC LIMIT 10) without descending again.
  5. All leaves are at the same depth — the perfect-balance invariant inherited from the B-tree.

2.1 Why the keys-only internal nodes matter

The fan-out math is straightforward. Suppose page size is P, key size is K, child pointer size is C (8 bytes on 64-bit systems), and value size is V. Then:

  • B-tree internal node fan-out: P / (K + C + V) (each entry is key + child pointer + row data)
  • B+ tree internal node fan-out: P / (K + C) (no value)
  • B+ tree leaf fan-out: P / (K + V) (no child pointer)

For P = 16 KB = 16384, K = 16, C = 8, V = 200:

  • B-tree fan-out: 16384 / 224 ≈ 73
  • B+ tree internal fan-out: 16384 / 24 ≈ 683
  • B+ tree leaf fan-out: 16384 / 216 ≈ 75

Tree height for n = 10^9:

  • B-tree: log_73(10^9) ≈ 4.83 → 5
  • B+ tree: log_683(10^9) ≈ 3.18 → 4

Saving one level of disk reads is significant — for an OLTP query running thousands of times per second, dropping from 5 reads to 4 is a 20% latency reduction. This is the primary engineering reason B+ trees are preferred.

2.2 Key duplication between internal nodes and leaves

A subtle property: in a B+ tree, the same key appears both as a routing key in some internal node and as the actual data key in a leaf. The internal copy is just a separator value; the leaf copy is the “real” entry. The duplication is intentional — without it, an internal node could not direct searches to the right child.

This means that if we have n actual data records, we have n keys in leaves plus roughly n / t additional copies in internal nodes (for routing). The total key storage is n · (1 + 1/(t-1)) ≈ n for typical fan-outs — the routing overhead is small.

2.3 Leaf linkage variants

Some B+ tree designs link leaves singly (left-to-right only). Others use doubly-linked leaves so backward scans are also O(log n + k). A few variants link not just leaves but also internal nodes at every level (sometimes called a B-link tree, due to Lehman & Yao 1981) — this is for concurrency control, not range scans.

3. Tiny Worked Example — Insertion and Range Scan

Take t = 2, so each node holds 1–3 keys. Insert 5, 10, 20, 30, 40, 25, 35, 15, 50 and observe how the leaf list maintains.

3.1 Insert 5, 10, 20

Single leaf, also the root.

Leaf root: [5, 10, 20]   ← head of leaf list

3.2 Insert 30 — leaf splits

Leaf is full (3 = 2t − 1). Split: median is 20 (or 10, depending on convention; B+ trees typically promote the smallest key of the right half as the routing key, and keep a copy in the right leaf — see §3.3).

After split, the structure becomes:

Internal: [20]          ← routing key
         /     \
   [5, 10]   [20, 30]   ← leaves, doubly-linked: [5,10] ↔ [20,30]

Note the key 20 appears in both the internal node (as a separator) and the right leaf (as data). This duplication is normal and expected — the routing copy says “if your search key is ≥ 20, go right,” and the leaf copy is the actual record.

3.3 Insert 40

Goes to the right leaf:

Internal: [20]
         /     \
   [5, 10]   [20, 30, 40]

3.4 Insert 25 — right leaf splits again

Right leaf is full. Split: take 30 as routing key (smallest of right half). The internal node [20] now needs to absorb the new routing key:

Internal: [20, 30]
         /   |    \
   [5,10] [20,25] [30,40]
   leaf list: [5,10] ↔ [20,25] ↔ [30,40]

3.5 Insert 35, 15 — fits without splits

Internal: [20, 30]
         /   |       \
   [5,10,15] [20,25] [30,35,40]
   leaf list: [5,10,15] ↔ [20,25] ↔ [30,35,40]

3.6 Insert 50 — middle leaf full? No, rightmost leaf full

Right leaf [30, 35, 40] is at capacity. Wait — insert path for 50 is the rightmost leaf, which has 3 keys (full). Split: routing key 40 (or 35 depending on chosen median):

After split, internal [20, 30] must absorb new routing key 40:

Internal: [20, 30, 40]
         /  |   |    \
   [5,10,15] [20,25] [30,35] [40,50]
   leaf list: [5,10,15] ↔ [20,25] ↔ [30,35] ↔ [40,50]

The internal node now holds [20, 30, 40] — at capacity. The next leaf split will trigger an internal-node split (the standard B-tree promotion mechanic; the median goes to a new root one level up).

3.7 Range query: “find all keys in [22, 38]”

This is the range-query payoff. Steps:

  1. Descend from root: 22 falls between 20 and 30, so descend into the second child (the leaf [20, 25]).
  2. Walk that leaf: 25 is in range; 25 ≥ 22 and 25 ≤ 38, so emit 25.
  3. Follow the linked-list pointer to the next leaf: [30, 35]. Both 30 and 35 are in range; emit both.
  4. Follow the linked-list pointer: [40, 50]. 40 > 38, so stop.

Result: [25, 30, 35]. Total work: 1 descent (O(log_t n) reads) + 2 leaf reads. The B-tree equivalent would have performed an in-order traversal touching some interior nodes, requiring O(k log_t n) work in the worst case. The B+ tree’s leaf linkage transforms range queries from O(k log n) into O(log n + k).

4. Algorithm — Same as B-Tree, Plus Leaf Linkage

The algorithmic structure is parallel to a B-tree’s, with three changes: (a) data only goes into leaves, (b) leaf splits also re-link the doubly-linked list, (c) the routing key in an internal node is duplicated to the right child after a split, not removed from it.

BPlusSearch(root, k):
    node := root
    while node is internal:
        i := smallest index s.t. k < node.key[i]   # binary search inside node
        node := node.child[i]
    # Now `node` is a leaf
    return leaf binary-search for k in node.key

The descent always reaches a leaf, even if the key matches an internal-node routing key — because that routing key’s value lives in a leaf, not in the internal node. Number of disk reads: tree height + 1 (the +1 is the leaf itself).

4.2 Insert

Like a B-tree, but the actual (key, value) insertion happens at a leaf. When a leaf overflows, it splits into two leaves, the smallest key of the right half is promoted to the parent as a routing key (also kept in the right leaf), and the leaf doubly-linked list is updated to insert the new leaf between the old leaf and its right neighbor.

BPlusInsert(T, k, v):
    root := T.root
    if root is full:
        new_root := new internal node with single child = root
        SplitChild(new_root, 0)
        T.root := new_root
    InsertNonfull(T.root, k, v)

InsertNonfull(node, k, v):
    if node is leaf:
        insert (k,v) into node.entries in sorted order
    else:
        i := index of child responsible for k
        if node.child[i] is full:
            SplitChild(node, i)
            if k > node.key[i]:
                i := i + 1
        InsertNonfull(node.child[i], k, v)

SplitChild(parent, i) for a leaf child: split the leaf into two halves; promote the smallest key of the new right half to parent.key[i]; update both new leaves’ linked-list pointers (right leaf’s prev is left leaf, left leaf’s next is right leaf, and the right leaf’s next is the original right neighbor of the old leaf).

SplitChild for an internal child: identical to B-tree split — the median is moved up, not duplicated.

4.3 Range query

BPlusRangeQuery(root, lo, hi):
    leaf := descend to leaf containing lo
    out := []
    while leaf is not null:
        for entry (k, v) in leaf:
            if k > hi: return out
            if k >= lo: out.append((k, v))
        leaf := leaf.next     # follow doubly-linked list
    return out

O(log_t n) for the descent + O(k / B) page reads where k is the number of returned entries and B is keys-per-leaf. This is the B+ tree’s killer feature; everything else is convenient bookkeeping.

4.4 Delete (with linked-list maintenance)

Identical structure to B-tree delete, with two extra steps when a leaf is removed or merged:

  1. Update the linked-list pointers: when leaf L is merged with sibling L', the merged result inherits the new combined pointers (L.prev → merged_leaf → L'.next).
  2. When borrowing a key from a sibling, the linked list does not change (the leaves themselves are unchanged, just one entry moves between them).

Underflow is handled the same way as a B-tree: if a leaf falls below t − 1 keys, borrow from a sibling if possible; otherwise merge with a sibling. The internal-node side is identical to B-tree delete.

5. Python Implementation (Pedagogical)

In-memory, ignoring disk page semantics. Captures the leaf-only data placement and linked-list traversal.

from typing import Optional
from dataclasses import dataclass, field
 
@dataclass
class BPlusInternalNode:
    keys: list[int] = field(default_factory=list)
    children: list["BPlusNode"] = field(default_factory=list)
 
@dataclass
class BPlusLeafNode:
    keys: list[int] = field(default_factory=list)
    values: list = field(default_factory=list)
    next: Optional["BPlusLeafNode"] = None
    prev: Optional["BPlusLeafNode"] = None
 
BPlusNode = "BPlusInternalNode | BPlusLeafNode"
 
class BPlusTree:
    def __init__(self, t: int = 3) -> None:
        if t < 2:
            raise ValueError("t must be >= 2")
        self.t = t
        self.root: BPlusNode = BPlusLeafNode()
 
    # -------- Search --------
    def search(self, k: int):
        leaf = self._find_leaf(k)
        for i, key in enumerate(leaf.keys):
            if key == k:
                return leaf.values[i]
        return None
 
    def _find_leaf(self, k: int) -> BPlusLeafNode:
        node = self.root
        while isinstance(node, BPlusInternalNode):
            i = 0
            while i < len(node.keys) and k >= node.keys[i]:
                i += 1
            node = node.children[i]
        return node
 
    # -------- Range query (the B+ tree's killer feature) --------
    def range_query(self, lo: int, hi: int) -> list[tuple[int, object]]:
        out = []
        leaf: Optional[BPlusLeafNode] = self._find_leaf(lo)
        while leaf is not None:
            for k, v in zip(leaf.keys, leaf.values):
                if k > hi:
                    return out
                if k >= lo:
                    out.append((k, v))
            leaf = leaf.next
        return out
 
    # -------- Insert --------
    def insert(self, k: int, v) -> None:
        # Top-level: if root is full, grow tree taller.
        if self._is_full(self.root):
            new_root = BPlusInternalNode()
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_nonfull(self.root, k, v)
 
    def _is_full(self, node: BPlusNode) -> bool:
        return len(node.keys) == 2 * self.t - 1
 
    def _insert_nonfull(self, node: BPlusNode, k: int, v) -> None:
        if isinstance(node, BPlusLeafNode):
            i = 0
            while i < len(node.keys) and node.keys[i] < k:
                i += 1
            if i < len(node.keys) and node.keys[i] == k:
                node.values[i] = v        # update existing
                return
            node.keys.insert(i, k)
            node.values.insert(i, v)
        else:
            i = 0
            while i < len(node.keys) and k >= node.keys[i]:
                i += 1
            if self._is_full(node.children[i]):
                self._split_child(node, i)
                if k >= node.keys[i]:
                    i += 1
            self._insert_nonfull(node.children[i], k, v)
 
    def _split_child(self, parent: BPlusInternalNode, idx: int) -> None:
        """Split parent.children[idx] (which is full) into two; promote a routing key."""
        t = self.t
        full_child = parent.children[idx]
        if isinstance(full_child, BPlusLeafNode):
            new_leaf = BPlusLeafNode()
            # Left keeps lower t keys; right takes upper t-1.
            new_leaf.keys = full_child.keys[t - 1:]
            new_leaf.values = full_child.values[t - 1:]
            full_child.keys = full_child.keys[:t - 1]
            full_child.values = full_child.values[:t - 1]
            # Linked-list maintenance.
            new_leaf.next = full_child.next
            new_leaf.prev = full_child
            if full_child.next is not None:
                full_child.next.prev = new_leaf
            full_child.next = new_leaf
            # Promote: smallest key of the new (right) leaf is the routing key.
            promoted = new_leaf.keys[0]
            parent.keys.insert(idx, promoted)
            parent.children.insert(idx + 1, new_leaf)
        else:
            # Internal-node split — identical to B-tree split: median goes up.
            new_internal = BPlusInternalNode()
            promoted = full_child.keys[t - 1]
            new_internal.keys = full_child.keys[t:]
            new_internal.children = full_child.children[t:]
            full_child.keys = full_child.keys[:t - 1]
            full_child.children = full_child.children[:t]
            parent.keys.insert(idx, promoted)
            parent.children.insert(idx + 1, new_internal)
 
 
# Demo: insert and range-query.
bpt = BPlusTree(t=2)
data = [(5, "a"), (10, "b"), (20, "c"), (30, "d"), (40, "e"),
        (25, "f"), (35, "g"), (15, "h"), (50, "i")]
for k, v in data:
    bpt.insert(k, v)
assert bpt.search(25) == "f"
assert bpt.search(99) is None
range_result = bpt.range_query(22, 38)
assert [k for k, _ in range_result] == [25, 30, 35]

The implementation makes three pedagogical points clear:

  1. _find_leaf always descends to a leaf. Even when the key matches an internal routing key, the descent continues — because the actual record lives in a leaf. The descent’s loop condition k >= node.keys[i] (rather than k > node.keys[i]) is the convention that ensures keys equal to a routing key are routed to the right child, where the actual leaf copy lives.

  2. range_query walks leaf.next. No descent during the walk — this is what makes the operation O(log n + k).

  3. Leaf split duplicates the smallest right-half key into the parent. This is different from internal-node split (where the median is moved, not copied). The duplication is what makes the routing layer work correctly.

6. Complexity

6.1 Per-operation costs (in disk I/Os)

OperationB-treeB+ tree
Point searchO(log_t n)O(log_t n)
InsertO(log_t n)O(log_t n)
DeleteO(log_t n)O(log_t n)
Range query for k resultsO(k log_t n) worst caseO(log_t n + k/B) where B = keys per leaf
Sequential scan (full table)O(n) (in-order DFS)O(n/B) (linked-list walk)

The asymptotic point-operation costs are identical because both trees have height Θ(log_t n). The constants differ: B+ trees have higher fan-out at internal nodes (no row data), so the height for the same n is smaller in absolute terms (~3 vs ~5 for n = 10^9).

The range-query difference is the dominant practical advantage. OLTP queries are ~80% point lookups + range scans, so cutting range-scan costs by a factor of B (the leaf fan-out, typically ~50–500) is enormous.

6.2 Height bound

Same as B-tree (proof in B-Tree §6.1):

h ≤ log_t((n + 1) / 2)

But “the same” is misleading because B+ tree internal t is larger than B-tree t for the same page size. With internal fan-out t_int and leaf fan-out t_leaf:

  • Number of leaves needed: ⌈n / t_leaf⌉.
  • Tree levels above leaves: log_{t_int}(n / t_leaf).
  • Total height: 1 + log_{t_int}(n / t_leaf).

For n = 10^9, t_leaf = 75, t_int = 683: 1 + log_683(10^9 / 75) = 1 + log_683(1.33 × 10^7) ≈ 1 + 2.5 ≈ 3.5 → 4.

For a B-tree with t = 73 and the same n: log_73(10^9) ≈ 4.83 → 5.

So B+ saves one level (~20% I/O reduction) for typical OLTP setups.

6.3 Range-query analysis

For a range [lo, hi] returning k results spread across ⌈k/B⌉ leaves:

  • Descent to first leaf: Θ(log_t n) reads.
  • Linked-list walk: ⌈k/B⌉ reads (one per leaf scanned).
  • Total: Θ(log_t n + k/B).

For k = 1000, B = 80, log_t n = 4: 4 + 13 = 17 reads. The B-tree would do ~80 leaf reads plus interior nodes for the same range, easily 5×–10× more I/O.

This is why every database planner prefers B+ trees for WHERE col BETWEEN x AND y queries; the optimizer can scan a contiguous leaf range directly.

6.4 Space

O(n) total. The internal-node overhead is small because internal nodes are sparse (only one entry per leaf, divided by branching factor). For a tree with L leaves at fan-out t_int, the number of internal nodes is roughly L / (t_int − 1) + L / (t_int − 1)^2 + ... ≈ L / (t_int − 2). Internal storage is ~1% of leaf storage when t_int = 100.

7. Why Databases Pick B+ Tree (the Production Argument)

Three reasons, in roughly the order they matter for OLTP:

7.1 Range scans are first-class

OLTP workloads are full of WHERE col BETWEEN x AND y, ORDER BY col LIMIT n, WHERE prefix = ? (range scan on indexed column where the prefix uses an indexed range). The B+ tree’s O(log n + k) range query maps perfectly onto these patterns. A B-tree would force the query planner to choose between (a) re-descending for each row (O(k log n), terrible) or (b) building a separate sorted structure per query (overhead). Neither is acceptable.

7.2 Internal nodes pack more keys → shorter trees

Already analyzed in §6.2: B+ internal fan-out is several times higher than a B-tree’s because internal nodes carry only routing data. Shorter trees = fewer disk reads per point lookup. For an OLTP database serving 100K queries/second, a 20% latency reduction is a 25% throughput increase.

7.3 Sequential leaf access is cache- and prefetch-friendly

Modern OS page caches and SSDs both prefetch on sequential access patterns. A linked-list leaf walk in a B+ tree is exactly such a pattern: the OS observes read page X, read page X+1, read page X+2 and starts pre-issuing reads for X+3, X+4. The effective per-leaf cost during a long scan can drop below one read because the prefetcher hides latency. The B-tree’s in-order traversal jumps around the tree non-sequentially and defeats prefetch.

The flip side: B+ trees are slightly more complex to implement than B-trees (the leaf-linkage and key-duplication mechanics) and use slightly more memory (key duplication between internal and leaf layers). These are minor costs relative to the gains.

8. Variants and Engineering Refinements

Adds a “right link” pointer to every node (internal too) plus a “high key” upper bound, enabling race-free concurrent traversal during splits. When a search follows a downlink to a child and discovers the search key exceeds the child’s high key, the page must have been concurrently split — the search follows the right-link to find the new sibling holding the desired range. PostgreSQL’s nbtree README states this explicitly: “This directory contains a correct implementation of Lehman and Yao’s high-concurrency B-tree management algorithm (P. Lehman and S. Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp 650-670)” (postgres/src/backend/access/nbtree/README). The README also notes that PostgreSQL adopts a simplified version of the deletion logic from Lanin & Shasha’s “A Symmetric Concurrent B-Tree Algorithm” (1986) for the parts L&Y did not cover.

8.2 Bw-tree

A latch-free B+ tree variant introduced by Microsoft Research (Levandoski, Lomet, Sengupta 2013) for SQL Server’s Hekaton in-memory engine. Uses a mapping table to redirect logical page IDs to physical pages, allowing atomic compare-and-swap installation of “delta records” without locks.

8.3 Fractal tree (TokuDB)

Buffers messages (insert/update/delete) at internal nodes and flushes them down lazily in batches. Reduces I/O for write-heavy workloads at the cost of read amplification. Sits between B+ trees and LSM Trees on the read/write trade-off curve.

8.4 Prefix B+ tree

Stores a prefix of each key in internal nodes instead of the full key, increasing internal-node fan-out for variable-length string keys. Used in some XML and document-oriented databases.

8.5 Clustered vs non-clustered indexes

A clustered B+ tree stores the actual row data in the leaves. There is one clustered index per table (typically the primary key). MySQL InnoDB and SQL Server use this design — the primary key index is the table.

A non-clustered B+ tree stores (key, row_pointer) pairs in the leaves; the row data lives elsewhere (in a heap or in the clustered index). PostgreSQL uses non-clustered indexes by default; row data lives in the heap, indexes point into it.

The clustered design saves one I/O per lookup (the index scan returns the row directly). The non-clustered design allows multiple secondary indexes without per-row data duplication.

9. Pitfalls

9.1 Confusing B-tree and B+ tree in code or interviews

Casually saying “the database uses a B-tree” is technically wrong almost always — it uses a B+ tree. PostgreSQL’s btree access method is misnamed (it is actually a B+ tree variant). MySQL InnoDB documentation says “B-tree” interchangeably with “B+ tree.” When precision matters (interview, code review, paper), distinguish clearly.

9.2 Forgetting that internal-node keys are duplicated in leaves

A common implementation bug: mistakenly removing the routing key from the right leaf after a split (because that pattern works for B-trees, where the median moves up). In B+ trees, the routing key in the parent is a copy of the smallest key in the right leaf, not a removal of it. Removing it from the leaf corrupts the tree.

9.3 Off-by-one on routing key comparison

Search descent uses k >= node.keys[i] (greater than or equal) to send equal keys right. Using k > node.keys[i] makes equal keys go left, missing the leaf where the actual record lives. This bug surfaces only when the inserted key happens to equal a routing key — rare on random data, common on monotonic inserts, which are what real workloads do.

9.4 Not maintaining the leaf linked list on splits and deletes

The leaf linked list is the whole reason B+ trees exist. On every leaf split, you must update four pointers (new leaf’s prev/next, old leaf’s next, original next-leaf’s prev). On every leaf merge, three pointers. Forgetting any one corrupts the linked list — and the only symptom is range queries silently returning incorrect results.

9.5 Concurrency is genuinely difficult

A naive B+ tree breaks under concurrent inserts and reads because a reader may follow a pointer to a leaf that is mid-split. Production systems use Lehman-Yao B-link trees, lock coupling, or hardware transactional memory (HTM). Implementing concurrent B+ trees from scratch is a graduate-level distributed systems exercise; do not attempt it in production code without studying primary literature first.

9.6 Treating the B+ tree as a black box for non-uniform distributions

B+ trees assume keys are distributed uniformly enough that random insertions roughly fill nodes evenly. Monotonically increasing inserts (e.g., timestamps, auto-increment primary keys) cause every insert to land in the rightmost leaf, splitting it repeatedly. The rightmost path is hot; the rest of the tree is cold. Many databases implement fillfactor tuning or insert-buffer tricks (InnoDB’s “change buffer”) to mitigate this. Test your real workload’s key distribution.

9.7 Assuming B+ tree is fastest for every workload

For write-heavy workloads (especially batch ingestion), LSM Trees often win by 10×–100× because they buffer writes in memory and flush them in sorted runs sequentially. For very small in-memory data (under 100 KB), a sorted array with binary search is faster (no pointer overhead). For equality-only lookups on uniformly distributed keys, hash tables beat B+ trees by ~5×.

9.8 Failing to flush leaf-list updates atomically with split

In a crash-safe B+ tree on disk, the new leaf’s data, the old leaf’s truncation, and the linked-list pointer updates must be applied atomically (or with a recoverable redo/undo log). Real databases use write-ahead logging (WAL); ad-hoc B+ tree implementations on disk often skip this and corrupt themselves on power loss.

10. Diagram — B+ Tree with Linked Leaves

flowchart TD
    R["Internal: [20, 50]"]
    L1["Leaf: [5, 10, 15]"]
    L2["Leaf: [20, 25, 30, 40]"]
    L3["Leaf: [50, 70, 90]"]
    R --> L1
    R --> L2
    R --> L3
    L1 -.next.-> L2
    L2 -.next.-> L3
    L3 -.prev.-> L2
    L2 -.prev.-> L1

What this diagram shows. A 2-level B+ tree where internal nodes contain only routing keys [20, 50] and the actual data (key, value) pairs live entirely in leaves. The dashed edges represent the doubly-linked list connecting leaves in key order; solid edges are the standard parent-to-child pointers. A point search for 25 descends from the root, sees 20 ≤ 25 < 50, descends into the middle leaf, and finds it. A range query for [12, 32] first descends to the leaf containing the smallest matching key (the leaf [5,10,15] for 15, or [20,25,30,40] for 20, depending on the lower bound), then walks rightward via the dashed pointers, emitting matching entries until exceeding the upper bound. Critically, the keys 20 and 50 in the internal node are duplicates of leaf data — 20 lives both as a routing key in the internal node and as an actual entry in the second leaf. The internal layer is a sparse routing index over the dense leaf layer.

11. Common Interview Problems

SourceProblemConnection to B+ tree
Systems-design”Design an autocomplete system”Range query on prefix (a LIKE 'pre%' lookup is a range scan)
Systems-design”Design a time-series database”Range queries on timestamp; B+ tree is the inner index
Systems-design”Why is WHERE col BETWEEN x AND y fast on indexed columns?”Direct: leaf-linked-list traversal
Systems-design”Why is LIKE '%suffix' slow?”No prefix → no range starting point → falls back to full scan
Systems-design”Difference between clustered and non-clustered index?”Leaf payload: full row vs row pointer
Systems-design”What goes wrong with monotonic primary keys?”Right-side hot spot in leaf splits
Database internals”Walk me through how InnoDB does a SELECT”B+ tree descent + leaf scan
Distributed”Why does a hash-partitioned index defeat range queries?”Hashing destroys key locality required for leaf-linked-list scans

For interviews, the most-asked B+ tree questions are systems-design ones: “how do databases work” and “why is one query fast and another slow.” Implementing a B+ tree from scratch in a coding interview almost never happens, but explaining the structure (leaves only, linked, internal layer is routing) is expected at any company doing storage or DB work.

12. Open Questions

  • What is the right comparison between B+ trees and learned indexes (Kraska et al. 2018, “The Case for Learned Index Structures”)? Learned indexes can be faster for static read-only data but lose to B+ trees for OLTP workloads with updates.
  • Does the Bw-tree’s latch-free design actually beat well-tuned latch-based B+ trees in production? Microsoft published positive results for Hekaton, but independent benchmarks are scarce.
  • How do B+ trees adapt to byte-addressable persistent memory (Optane, CXL)? The block-oriented design assumes paged I/O; persistent memory is closer to random RAM. New variants like FPTree and HiKV reshape the structure for these devices.

Resolved

InnoDB-uses-B+trees is anchored against the MySQL 8.0 InnoDB physical-structure documentation (“index records are stored in the leaf pages”) and Jeremy Cole’s reverse-engineered diagram of the InnoDB on-disk format (showing doubly-linked leaves). The MySQL glossary calls them “B-tree” generically but explicitly notes that “B-tree structures used by MySQL storage engines may be regarded as variants due to sophistications not present in a classic B-tree design” (MySQL 8.0 glossary) — the variant being a B+ tree. PostgreSQL’s Lehman-Yao claim is verified verbatim against the nbtree README in the master branch as of 2026-05-30 (see §8.1). Genuine residual uncertainty: the §1 fan-out numbers (280 vs 65) remain illustrative — they are correct given the stated key/row-size assumptions but real schemas vary; Jeremy Cole’s empirical numbers (~468 leaf records, ~1,203 non-leaf records on 16 KB pages with integer primary keys) are a stronger primary anchor for “what real InnoDB does with a real schema.”

13. See Also

Graph View

Backlinks