TreesData structureaka B+ index, leaf-linked B-tree

B+ Tree

A B-tree variant that stores all records in linked leaf nodes and uses internal nodes only as a routing index, giving fast point lookups and sequential range scans.

Pattern: Binary Search Practice (2)

Progress

Definition

A B+ tree separates routing from storage: internal nodes hold only keys that guide the search, and every record (or key/value pair) lives in a leaf. Leaves are linked left-to-right into a sorted list, so a range query is one descent to the first matching leaf followed by a sequential walk. Because internal nodes carry no values, they pack more keys per page than a B-Tree, which makes the tree shallower and the top levels small enough to stay in memory.

Every search goes all the way to a leaf, so lookups have uniform cost. Insertion splits full leaves and copies (not moves) the split key up; internal splits push the middle key up as in a B-tree. Deletion merges or borrows between sibling leaves.

B+ trees are the default index in MySQL InnoDB, PostgreSQL, SQLite, Oracle, and file systems such as NTFS, XFS, ReiserFS and ext4 (extents). When an interviewer says "database index", this is the structure.

database indexrange scanlinked leavesdiskbalanced

Intuition

A mental model before the formal terms.

Imagine a book's index printed only with chapter headings on the top pages and all the actual entries laid out in order on the bottom pages, each bottom page pointing to the next. To find one entry you follow headings down; to find everything between "cat" and "dog" you find "cat" and read forward until you pass "dog", never going back up. That forward pointer is the B+ tree's whole advantage for range scans.

How it works

Search(key): at each internal node, find the first key greater than the search key and descend into the corresponding child; at the leaf, binary-search the entries.
Insert(key, value): descend to the leaf. Insert in order. If the leaf overflows (> maxKeys), split it into two leaves, link them, and insert the first key of the right leaf into the parent as a separator. If the parent overflows, split it (moving the middle key up, not copying). A root split creates a new root and increases height.
Delete(key): remove from the leaf. If the leaf underflows, borrow from a sibling (and update the parent separator) or merge with it (and remove the separator). Propagate upward as needed.
Range(lo, hi): search for lo, then follow next pointers emitting entries until a key exceeds hi.

Why it works

Internal separators are always ≥ every key in the left subtree and < every key in the right subtree, so the descent reaches the unique leaf where the key must reside.

Splitting only when full and merging only when below half keeps every node between half and completely full, so height is O(log_t n) exactly as for a B-tree.

The leaf chain is a sorted linked list by construction: splits insert the new leaf immediately after the old one, and merges unlink the removed one.

Operations

Operation	Description	Cost
search(key)	Descend via separators to a leaf; binary-search the leaf.	O(log_t n)
insert(key, value)	Insert into a leaf, split upward on overflow.	O(log_t n)
delete(key)	Remove from a leaf, borrow/merge upward on underflow.	O(log_t n)
range(lo, hi)	Descend once, then scan the leaf chain.	O(log_t n + k)
scanAll	Walk the leaf chain from the leftmost leaf.	O(n)

Recognition

How to tell a problem wants this.

Systems design or database questions about indexes, "why is WHERE id BETWEEN fast?", clustered vs secondary indexes.
Ordered key-value storage on disk with heavy range scans.
Comparing storage engines: B+ tree (InnoDB) vs LSM tree (RocksDB).

“sorted array” → Binary Search “binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1search(key):
2  node = root
3  while node is internal: node = node.children[upperBound(node.keys, key)]
4  return node.lookup(key)
5range(lo, hi):
6  leaf = findLeaf(lo)
7  while leaf != null: for (k, v) in leaf.entries: if k > hi: return; if k >= lo: emit(k, v)
8    leaf = leaf.next

Implementation

1from bisect import bisect_left, bisect_right
2from typing import Optional
3 
4 
5class BPlusTree:
6    """Every RECORD lives in a leaf; internal nodes hold only routing keys.
7    Two consequences follow, and they are the whole reason databases use this
8    instead of a plain B-tree:
9      1. leaves are chained, so a range scan is one descent then a linked walk
10      2. internal nodes carry no payload, so more keys fit per block"""
11 
12    def __init__(self, order: int) -> None:
13        self.order = order  # maximum keys per node
14        self.keys_of: list[list[int]] = []
15        self.children_of: list[list[int]] = []
16        self.values_of: list[list[int]] = []
17        self.next_of: list[int] = []
18        self.is_leaf: list[bool] = []
19        self.root = self._new_node(True)
20 
21    def _new_node(self, leaf: bool) -> int:
22        self.keys_of.append([])
23        self.children_of.append([])
24        self.values_of.append([])
25        self.next_of.append(-1)
26        self.is_leaf.append(leaf)
27        return len(self.keys_of) - 1
28 
291 · Descend to the leaf that would hold this key
30    def _find_leaf(self, key: int) -> int:
31        i = self.root
32        while not self.is_leaf[i]:
33            i = self.children_of[i][bisect_right(self.keys_of[i], key)]
34        return i
35 
362 · Point lookup always reaches a leaf — internal keys are routing only
37    def get(self, key: int) -> Optional[int]:
38        leaf = self._find_leaf(key)
39        ks = self.keys_of[leaf]
40        pos = bisect_left(ks, key)
41        return self.values_of[leaf][pos] if pos < len(ks) and ks[pos] == key else None
42 
43    def insert(self, key: int, value: int) -> None:
44        path: list[int] = []
45        i = self.root
46        while not self.is_leaf[i]:
47            path.append(i)
48            i = self.children_of[i][bisect_right(self.keys_of[i], key)]
49        ks = self.keys_of[i]
50        pos = bisect_left(ks, key)
51        if pos < len(ks) and ks[pos] == key:
52            self.values_of[i][pos] = value  # replace an existing key
53            return
54        ks.insert(pos, key)
55        self.values_of[i].insert(pos, value)
56 
573 · Split leaves by COPYING the separator up (it stays in the leaf),
58        # unlike a B-tree which moves the median out of the node entirely
59        while len(self.keys_of[i]) > self.order:
60            mid = len(self.keys_of[i]) // 2
61            fresh = self._new_node(self.is_leaf[i])
62            if self.is_leaf[i]:
63                separator = self.keys_of[i][mid]  # copied, not moved
64                self.keys_of[fresh] = self.keys_of[i][mid:]
65                self.values_of[fresh] = self.values_of[i][mid:]
66                del self.keys_of[i][mid:]
67                del self.values_of[i][mid:]
68                self.next_of[fresh] = self.next_of[i]  # relink the leaf chain
69                self.next_of[i] = fresh
70            else:
71                separator = self.keys_of[i][mid]  # moved, as in a B-tree
72                self.keys_of[fresh] = self.keys_of[i][mid + 1 :]
73                self.children_of[fresh] = self.children_of[i][mid + 1 :]
74                del self.keys_of[i][mid:]
75                del self.children_of[i][mid + 1 :]
76            if not path:
77                fresh_root = self._new_node(False)
78                self.keys_of[fresh_root].append(separator)
79                self.children_of[fresh_root].extend([i, fresh])
80                self.root = fresh_root
81                return
82            parent = path.pop()
83            ppos = bisect_right(self.keys_of[parent], separator)
84            self.keys_of[parent].insert(ppos, separator)
85            self.children_of[parent].insert(ppos + 1, fresh)
86            i = parent
87 
884 · The payoff: a range scan is one descent plus a walk along the chain
89    def range(self, lo: int, hi: int) -> list[tuple[int, int]]:
90        out: list[tuple[int, int]] = []
91        i = self._find_leaf(lo)
92        while i != -1:
93            for k, key in enumerate(self.keys_of[i]):
94                if key > hi:
95                    return out
96                if key >= lo:
97                    out.append((key, self.values_of[i][k]))
98            i = self.next_of[i]
99        return out
100 
1015 · Full iteration needs no traversal at all — just follow the chain
102    def entries(self) -> list[tuple[int, int]]:
103        i = self.root
104        while not self.is_leaf[i]:
105            i = self.children_of[i][0]
106        out: list[tuple[int, int]] = []
107        while i != -1:
108            out.extend(zip(self.keys_of[i], self.values_of[i]))
109            i = self.next_of[i]
110        return out

Walkthrough

Five parallel lists replace a node class, matching the approach used in the interval tree and the B-tree entries.
bisect_right for the descent routes an exact match into the leaf that holds it; bisect_left in get then finds it within that leaf.
del self.keys_of[i][mid:] truncates in place, and note that the *leaf* branch keeps mid keys while the *internal* branch keeps mid keys but mid + 1 children — the asymmetry is deliberate.
out.extend(zip(self.keys_of[i], self.values_of[i])) pairs the two parallel lists in one C-level call.
get returns None for a miss, which is unambiguous here because values are integers.

Complexity (this implementation)

time O(log_order n) for get and insert; O(log_order n + k) for a range of k entries · space O(n)

This is the structure SQLite and every relational database uses for indexes, which is why the range scan and the leaf chain matter more than the asymptotics.

Language notes

zip(keys, values) pairs two parallel lists lazily and list.extend consumes it in C — much faster than an index loop.
del lst[i:] truncates in place; lst = lst[:i] would rebind a local and leave the stored list unchanged.
bisect_right versus bisect_left is the descent-versus-lookup distinction and getting it backwards routes exact matches wrong.
sortedcontainers.SortedDict provides ordered iteration and range views without implementing this, and is the practical choice in Python.

Common mistakes in this language

Writing self.keys_of[i] = self.keys_of[i][:mid] in the split, which rebinds the list element correctly but is easy to confuse with the local-rebinding version that does not.
Using the same truncation for leaves and internal nodes, forgetting that internal nodes keep one more child than keys.
Descending with bisect_left.

Language differences that matter here

Signalling a lookup miss: C++ uses an out-parameter plus bool (or std::optional), Python returns None, TypeScript number | undefined (checked), and JavaScript undefined (unchecked) — four different contracts, and only TypeScript forces the caller to handle it.
Pairing two parallel arrays: Python zip plus list.extend is one call, while the other three need an index loop.
Truncating in place: C++ resize, Python del lst[i:], JS/TS .length = — and Python is the one where the near-identical lst = lst[:i] silently does something else.
Ordered-map alternatives: sortedcontainers.SortedDict in Python and std::map in C++ mean this is educational there; JavaScript has no ordered map at all, which makes a B+ tree the actual answer rather than a demonstration.

Complexity

Operation	Average	Worst	Note
Access	O(log n)	O(log n)	By key; always reaches a leaf.
Search	O(log n)	O(log n)	O(log_t n) page reads.
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)
Update	O(log n)	O(log n)	In place at the leaf.
Range query	O(log n + k)	O(log n + k)	Sequential over the leaf chain.
Full scan	O(n)	O(n)	Leaf chain only; internal nodes untouched.
Space	O(n)		Separator keys are duplicated in internal nodes; internal levels are small enough to cache in memory.

Advantages & disadvantages

Advantages

Range scans and full scans are sequential through the leaf chain — no back-tracking through internal nodes.
Higher fan-out than a B-tree (internal nodes hold keys only), so shallower trees and better cache use.
Uniform lookup cost: every search ends at a leaf.

Disadvantages

Keys are duplicated: separators appear in internal nodes and again in leaves.
Point lookups always go to a leaf even when the key appears in an internal node.
Write amplification on random inserts; LSM trees can be better for write-heavy workloads.

Use cases

Relational database indexes (InnoDB clustered index, PostgreSQL btree, SQLite).
File system metadata and extents (NTFS, XFS, ext4, Btrfs).
Key-value stores like LMDB and BoltDB.
Any ordered on-disk map needing efficient range iteration.

Use it when

Disk-resident ordered indexes with frequent range scans (BETWEEN, ORDER BY, prefix scans).
Clustered storage where rows live in the leaves and sequential I/O matters.
Any ordered key-value store with mixed point and range access.

Avoid it when

Purely in-memory small maps — Red-Black Tree or Hash Map.
Extremely write-heavy, append-mostly workloads — LSM trees reduce write amplification.
Only point lookups with no ordering — Hash Table indexes.

Alternatives

B-Tree Hash Table Skip List Red-Black Tree

Common mistakes

Moving (rather than copying) the split key up from a leaf, which loses the record.
Copying (rather than moving) the middle key up from an internal split, which duplicates a separator.
Forgetting to relink the leaf chain after a split or merge.
Assuming a key found in an internal node means it exists; only leaves are authoritative.

Interview patterns

Explain why B+ trees beat B-trees for range queries and why databases prefer them.
Estimate index height from page size, key size and row count.
Discuss clustered vs secondary indexes and what the leaves store in each.
Compare B+ tree and LSM tree read/write/space amplification.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Where does O(n log n) come from?Beginner
Recursion versus iterationIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Search in Rotated Sorted ArrayIntermediate

Interview problems

Design HashMapeasy Kth Smallest Element in a BSTmedium