TreesData structureaka multiway balanced search tree, Bayer–McCreight tree

B-Tree

A balanced multiway search tree with wide nodes holding many keys, designed to minimize disk or cache-line reads for very large ordered data.

Pattern: Binary Search Practice (2)

Progress

Definition

A B-tree of minimum degree t is a search tree where every node holds between t - 1 and 2t - 1 sorted keys and (if internal) one more child than keys, all leaves are at the same depth, and keys in child i fall between key[i-1] and key[i]. A node therefore fits one disk page or cache line, and a tree with t = 512 holds a billion keys in three levels.

Balance is maintained by splitting a full node during insertion (promoting its median to the parent) and by merging or borrowing from siblings during deletion. Because all leaves stay at the same depth and every node is at least half full, height is O(log_t n).

B-trees are the index structure of file systems (ext4, NTFS, HFS+) and databases. Most databases use the B+ Tree variant, which keeps all records in linked leaves. A Red-Black Tree is a B-tree with t = 2 drawn as a binary tree.

multiwaydiskdatabase indexfile systembalanced

Intuition

A mental model before the formal terms.

A binary tree asks one yes/no question per step; a B-tree asks "which of these 1000 buckets?" per step. When each question costs a disk seek (about 10 ms on a hard disk, or a cache miss in memory), asking fewer, fatter questions wins decisively: 30 seeks for a binary tree versus 3 for a B-tree of a billion keys.

Keeping every node at least half full and splitting only when full is what prevents the tree from ever becoming lopsided: growth happens only at the root, so all leaves stay at the same depth.

How it works

Search: at a node, binary-search the keys; if found return; else descend into the child between the two neighboring keys.
Insert (proactive splitting): walk down from the root; whenever the child you are about to enter is full (2t - 1 keys), split it first: move its median key up into the current node and split the remaining keys into two nodes of t - 1 keys each. Insert the key into the leaf you reach. If the root is full, split it and create a new root, increasing height by one.
Delete: ensure every node on the descent has at least t keys before entering it, by borrowing a key from a sibling (rotating through the parent) or merging with a sibling. In a leaf, remove the key. In an internal node, replace with the predecessor or successor and delete that recursively.
All modifications are local to a root-to-leaf path, so each operation touches O(log_t n) nodes and does O(t) work per node.

Why it works

Splitting a full node yields two nodes with t - 1 keys each, satisfying the minimum, and pushing the median up keeps the ordering invariant. Height grows only when the root splits, uniformly for all leaves.

With at least t - 1 keys per node (except the root), the number of nodes at depth d is at least 2t^(d-1), so n ≥ 2t^(h-1) - 1 and h ≤ log_t((n+1)/2).

Delete's "at least t keys before entering" rule guarantees that removing one key never violates the minimum, so no upward fix-up is needed.

Operations

Operation	Description	Cost
search(key)	Binary search within nodes, descend O(log_t n) levels.	O(t log_t n)
insert(key)	Split full nodes on the way down, insert into a leaf.	O(t log_t n)
delete(key)	Borrow or merge on the way down, remove from a leaf or via predecessor.	O(t log_t n)
split(child)	Promote the median and divide a full node in two.	O(t)
traverse	Inorder walk yields sorted keys.	O(n)
range(lo, hi)	Search lo then walk in order.	O(t log_t n + k)

Recognition

How to tell a problem wants this.

Ordered data too large for memory, or where each node access is a page read.
Systems questions: "how are database indexes implemented?", "why not a BST on disk?"
Cache-conscious in-memory ordered maps (B-tree maps in Rust, Abseil btree_map).

“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

1insert(key):
2  if root is full: newRoot = Node(); newRoot.children = [root]; splitChild(newRoot, 0); root = newRoot
3  insertNonFull(root, key)
4insertNonFull(node, key):
5  if node is leaf: insert key into node.keys in sorted position
6  else:
7    i = index of child for key
8    if children[i] is full: splitChild(node, i); if key > node.keys[i]: i += 1
9    insertNonFull(children[i], key)

Implementation

1from bisect import bisect_left, bisect_right
2 
3 
4class BTree:
5    """B-tree of minimum degree t: every node holds between t-1 and 2t-1 keys
6    and, if internal, one more child than keys. Wide nodes mean a shallow tree,
7    which is the entire point — height is log_t(n), so a disk-resident index of
8    a billion keys with t = 100 is about 5 levels deep instead of 30."""
9 
10    def __init__(self, min_degree: int) -> None:
11        self.t = min_degree
12        self.keys_of: list[list[int]] = []
13        self.children_of: list[list[int]] = []
14        self.is_leaf: list[bool] = []
15        self.root = self._new_node(True)
16 
17    def _new_node(self, leaf: bool) -> int:
18        self.keys_of.append([])
19        self.children_of.append([])
20        self.is_leaf.append(leaf)
21        return len(self.keys_of) - 1
22 
231 · Search descends one level per node, scanning keys within it
24    def contains(self, key: int) -> bool:
25        i = self.root
26        while True:
27            ks = self.keys_of[i]
28            pos = bisect_left(ks, key)
29            if pos < len(ks) and ks[pos] == key:
30                return True
31            if self.is_leaf[i]:
32                return False
33            i = self.children_of[i][pos]
34 
352 · Split a full child in two, pushing its median key up into the parent
36    def _split_child(self, parent: int, idx: int) -> None:
37        t = self.t
38        full = self.children_of[parent][idx]
39        fresh = self._new_node(self.is_leaf[full])
40 
41        # the median moves up; the right half moves into the new node
42        mid = t - 1
43        median = self.keys_of[full][mid]
44        self.keys_of[fresh] = self.keys_of[full][mid + 1 :]
45        del self.keys_of[full][mid:]
46        if not self.is_leaf[full]:
47            self.children_of[fresh] = self.children_of[full][t:]
48            del self.children_of[full][t:]
49        self.keys_of[parent].insert(idx, median)
50        self.children_of[parent].insert(idx + 1, fresh)
51 
523 · Insert top-down, splitting any full node on the way so the parent
53    # always has room — that is what makes it a single downward pass
54    def insert(self, key: int) -> None:
55        t = self.t
56        if len(self.keys_of[self.root]) == 2 * t - 1:
57            fresh = self._new_node(False)
58            self.children_of[fresh].append(self.root)
59            self.root = fresh
60            self._split_child(self.root, 0)  # the tree grows in height only here
61        i = self.root
62        while not self.is_leaf[i]:
63            pos = bisect_right(self.keys_of[i], key)
64            if len(self.keys_of[self.children_of[i][pos]]) == 2 * t - 1:
65                self._split_child(i, pos)
66                if key > self.keys_of[i][pos]:
67                    pos += 1
68            i = self.children_of[i][pos]
694 · The leaf is guaranteed non-full, so the key just slots in
70        self.keys_of[i].insert(bisect_right(self.keys_of[i], key), key)
71 
725 · In-order traversal visits keys in sorted order, interleaving
73    # each child subtree with the key that follows it
74    def _inorder(self, i: int, out: list[int]) -> None:
75        ks = self.keys_of[i]
76        leaf = self.is_leaf[i]
77        for k in range(len(ks)):
78            if not leaf:
79                self._inorder(self.children_of[i][k], out)
80            out.append(ks[k])
81        if not leaf:
82            self._inorder(self.children_of[i][-1], out)
83 
84    def keys(self) -> list[int]:
85        out: list[int] = []
86        self._inorder(self.root, out)
87        return out

Walkthrough

Three parallel lists (keys_of, children_of, is_leaf) replace a node class, avoiding one Python object per node.
bisect_left for search and bisect_right for descent are the two library calls that replace hand-written binary searches — Python and C++ both have them, JS/TS do not.
del self.keys_of[full][mid:] truncates in place; slicing to a new list and reassigning would allocate.
self.children_of[i][-1] reads the last child with a negative index, which is the cleanest of the four spellings.
self.keys_of[i].insert(bisect_right(...), key) finds the position and inserts in two calls; insort_right from bisect does both in one.

Complexity (this implementation)

time O(log_t n) node visits for search and insert; O(t) work within each node · space O(n) keys across O(n/t) nodes

For in-memory ordered data in Python, sortedcontainers.SortedList uses a list-of-lists with a similar shallow structure and is far faster than a hand-written B-tree.

Language notes

bisect.insort_right(lst, x) combines the search and the insert, and is what production code would use in the leaf step.
del lst[i:] truncates in place, unlike lst = lst[:i] which rebinds and leaves the original for the collector.
Negative indexing (children[-1]) reads the last element directly, with no len() - 1 arithmetic.
sortedcontainers.SortedList and SortedDict are the practical answers; SQLite and every relational database use B-trees internally, which is where the structure actually earns its keep.

Common mistakes in this language

Using lst = lst[:i] inside the split, which rebinds a local and leaves the stored node list unchanged.
Using bisect_left for the descent, sending equal keys left.
Forgetting the pos += 1 adjustment after splitting.

Language differences that matter here

Binary search within a node is a library call in C++ (lower_bound/upper_bound) and Python (bisect_left/bisect_right), and hand-written in JS/TS — and Python additionally has insort to combine the search with the insert.
Truncating an array in place: C++ resize, Python del lst[i:], JS/TS assignment to .length — three unrelated spellings, and in Python the tempting lst = lst[:i] rebinds instead of truncating.
Reading the last child: Python children[-1], C++ children.back(), JS/TS children[children.length - 1].
Ordered-map alternatives differ sharply: C++ has std::map (red-black) plus B-tree libraries, Python has sortedcontainers, and JavaScript has nothing ordered at all — which is the strongest argument for implementing this there rather than importing it.

Complexity

Operation	Average	Worst	Note
Access	O(log n)	O(log n)	By key; O(log_t n) page reads.
Search	O(log n)	O(log n)	O(t log_t n) comparisons, O(log_t n) I/Os.
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)
Update	O(log n)	O(log n)
Split / Merge	O(t)	O(t)
Range query	O(log n + k)	O(log n + k)
Traversal	O(n)	O(n)
Space	O(n)		Height ≤ log_t((n+1)/2). Nodes are at least half full, so space is at most 2n key slots.

Advantages & disadvantages

Advantages

Minimizes I/O: O(log_t n) page reads, typically 3–4 for billions of keys.
Guaranteed balance with only local restructuring.
Excellent locality; wins over binary trees even in memory for large n.

Disadvantages

Complex insertion and especially deletion code.
Nodes can be half empty, wasting up to 50% of space.
Range scans require going back up through internal nodes (fixed by the B+ Tree).

Use cases

File system directories and metadata (ext4 HTree, NTFS, Btrfs, APFS).
Database indexes (usually the B+ variant).
In-memory ordered maps optimized for cache lines.
Key-value stores and LSM-tree components.

Use it when

Ordered data on disk or SSD where node reads dominate: databases, file systems.
Very large in-memory ordered maps where cache misses dominate.
You need guaranteed balance with shallow height and sequential range scans.

Avoid it when

Small in-memory sets — a Red-Black Tree or AVL Tree is simpler.
No ordering needed — a Hash Map.
Range scans dominate and records are large — prefer the B+ Tree.

Alternatives

B+ Tree Red-Black Tree AVL Tree Skip List Hash Map

Common mistakes

Splitting reactively (after overflow) without handling the parent overflowing recursively; the proactive top-down split avoids this.
Off-by-one in the split: the median goes to the parent, left keeps t - 1, right gets t - 1.
Forgetting to adjust the child index after a split when the key is greater than the promoted median.
Deleting from a node with only t - 1 keys without first borrowing or merging.
Letting an empty root persist after a merge instead of promoting its single child.

Interview patterns

Explain why databases use B-trees instead of BSTs (I/O cost model).
Compute the height for a given page size and key size.
Walk through insertions that trigger a root split.
Compare B-tree vs B+ tree vs LSM tree for read/write workloads.

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

Don't delegate understanding

The manifesto →