---
title: B-Trees
module: Data Structures
moduleNumber: 4
lessonNumber: 10
order: 410
summary: |
  When data lives on disk, the cost that dominates is block transfers, not
  comparisons — and a binary tree of a billion keys is thirty reads deep. A
  B-tree of minimum degree $t$ is short and wide: $t-1$ to $2t-1$ keys per node,
  all leaves at one depth, height $O(\log_t n)$. Insertion splits a full node on
  the way down and pushes its median up; deletion borrows or merges to keep nodes
  full enough. High fan-out is what minimizes disk I/O.
topics: [Balanced Trees]
sources:
  - book: CLRS
    ref: "Ch. 18 — B-Trees"
  - book: Skiena
    ref: "§3.4 — Balanced Search Trees"
  - book: Erickson
    ref: "Ch. — Balanced Search Trees"
practice:
  - title: 'Design HashMap'
    slug: design-hashmap
    difficulty: Easy
  - title: 'Convert Sorted Array to BST'
    slug: convert-sorted-array-to-binary-search-tree
    difficulty: Easy
  - title: 'Kth Smallest Element in a BST'
    slug: kth-smallest-element-in-a-bst
    difficulty: Medium
  - title: 'Range Sum Query - Mutable'
    slug: range-sum-query-mutable
    difficulty: Medium
---

[Red-black and AVL trees](/algorithms/data-structures/balanced-trees) minimize the _number of nodes_ on a root-to-leaf
path — the right objective when every node is a pointer dereference in RAM. But
the moment the data outgrows memory and lives on a disk or SSD, the dominant cost
changes completely. Reading one **block** (a page, typically $4$ to $16$ KB) from
disk is millions of times slower than a comparison in cache, and you pay that
cost _per node touched_, whatever the node's size. A binary tree of $10^9$ keys
has height $\approx 30$, so a search is up to $30$ block reads — thirty trips to
the disk for one lookup.[^clrs-btree]

To cut the number of reads, make each node hold _many_ keys, so a single block read brings in
a whole fan-out's worth, and the tree is short enough that only two or three reads
reach any key. That is the **B-tree**: a balanced multiway search tree designed so
that height is $O(\log_t n)$ for a large branching factor $t$, and node size
matches the disk block.

## Structure: short and wide by design

A **B-tree of minimum degree** $t \ge 2$ is a search tree whose nodes hold a range
of keys and children rather than just one key and two children.

> **Definition (B-tree).** A B-tree of minimum degree $t \ge 2$ satisfies:
> - Every node holds its keys **in sorted order**, $key_1 \le key_2 \le \cdots$.
> - Every node other than the root holds between $t-1$ and $2t-1$ keys; the root
>   holds between $1$ and $2t-1$. A node is **full** when it has $2t-1$ keys.
> - A node with $k$ keys has exactly $k+1$ children. Its keys **separate** the
>   child subtrees: every key in child $i$ lies between $key_{i-1}$ and $key_i$.
> - **All leaves sit at the same depth** $h$, so the tree is height-balanced by
>   construction.

The keys inside a node act like a series of fence posts, and the children hang in
the gaps between them — a generalization of the BST's single key and two children
to $k$ keys and $k+1$ children.

$$
% caption: A B-tree of minimum degree $t = 3$ (so $2$ to $5$ keys per node). Each node's keys
%          partition the range; the children between consecutive keys hold exactly the keys in
%          that gap. All leaves lie at the same depth.
\begin{tikzpicture}[
  >=stealth,
  keynode/.style={draw, minimum height=6mm, inner sep=2pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[keynode] (root) at (0,0) {\,$30\ \ 60$\,};
  \node[keynode] (a) at (-3.6,-1.6) {\,$8\ \ 17$\,};
  \node[keynode] (b) at (0,-1.6) {\,$40\ \ 50$\,};
  \node[keynode] (c) at (3.6,-1.6) {\,$72\ \ 85$\,};
  \draw[->] (root.south) -- (a.north);
  \draw[->] (root.south) -- (b.north);
  \draw[->] (root.south) -- (c.north);
  \node[keynode] (d1) at (-6.4,-3.4) {\,$2\ \ 5$\,};
  \node[keynode] (d2) at (-4.6,-3.4) {\,$11\ \ 14$\,};
  \node[keynode] (d3) at (-2.8,-3.4) {\,$20\ \ 25$\,};
  \node[keynode] (d4) at (-1.0,-3.4) {\,$34\ \ 38$\,};
  \node[keynode] (d5) at (0.4,-3.4) {\,$44\ \ 47$\,};
  \node[keynode] (d6) at (1.8,-3.4) {\,$55\ \ 58$\,};
  \node[keynode] (d7) at (3.4,-3.4) {\,$66\ \ 70$\,};
  \node[keynode] (d8) at (5.2,-3.4) {\,$78\ \ 80$\,};
  \node[keynode] (d9) at (7.0,-3.4) {\,$90\ \ 95$\,};
  \draw[->] (a.south) -- (d1.north);
  \draw[->] (a.south) -- (d2.north);
  \draw[->] (a.south) -- (d3.north);
  \draw[->] (b.south) -- (d4.north);
  \draw[->] (b.south) -- (d5.north);
  \draw[->] (b.south) -- (d6.north);
  \draw[->] (c.south) -- (d7.north);
  \draw[->] (c.south) -- (d8.north);
  \draw[->] (c.south) -- (d9.north);
\end{tikzpicture}
$$

### Why the height is $O(\log_t n)$

The whole design rationale is the height bound, and it follows directly from the
minimum-occupancy rule.

> **Theorem.** A B-tree of minimum degree $t$ holding $n$ keys has height
> $h \le \log_t \dfrac{n+1}{2}$.

> **Proof.** Count the _minimum_ number of keys a tree of height $h$ can hold,
> which maximizes $h$ for given $n$. The root has at least $1$ key, hence at least
> $2$ children. Every other node has at least $t-1$ keys and at least $t$ children.
> So the number of nodes at depth $1$ is $\ge 2$, at depth $2$ is $\ge 2t$, at
> depth $i$ is $\ge 2t^{i-1}$. Each non-root node carries $\ge t-1$ keys, so
> $$
> n \ \ge\ 1 + (t-1)\sum_{i=1}^{h} 2t^{i-1}
>   \ =\ 1 + 2(t-1)\,\frac{t^{h}-1}{t-1}
>   \ =\ 2t^{h} - 1.
> $$
> Rearranging, $t^{h} \le (n+1)/2$, so $h \le \log_t\parens{(n+1)/2}$. $\qed$

The fan-out $t$ sits in the _base_ of the logarithm, which is the entire point:
**widening the node makes the tree shallower**. The base change is worth spelling
out with numbers. Suppose a disk block is $16$ KB, a key with its child pointer
takes $16$ bytes, so a block holds about $16384 / 16 = 1024$ entries — a fan-out
near $t = 512$. Then

$$
\log_{2}\!\big(10^{9}\big) \approx 30,
\qquad
\log_{512}\!\big(10^{9}\big) = \frac{\log_{2} 10^{9}}{\log_{2} 512}
  = \frac{30}{9} \approx 3.3.
$$

A binary tree of a billion keys is $30$ block reads deep; the B-tree is $3$ or $4$.
Almost all of that reduction is the change of base alone. Better still, the top two
levels — the root and its children, a few thousand blocks — stay pinned in memory
across queries, so in practice only the _bottom_ level or two ever touches the
disk: one or two reads per lookup.[^skiena-btree]

> **Intuition.** A binary tree minimizes _comparisons_; a B-tree minimizes
> _block transfers_. Inside a block, scanning $2t-1$ sorted keys is free
> (it is already in cache); the expensive thing is fetching the block at all. So
> we pack each block as full of keys as it holds and keep the tree as flat as
> possible, paying $\Theta(\log_t n)$ disk reads.

## Search

Searching mirrors a BST, except that at each node we scan its sorted keys to find
the gap the target falls into, then descend into the corresponding child. The
scan within a node is a linear (or binary) search over keys _already in memory_,
so it adds no disk reads; the descent costs one block read per level.

```algorithm
caption: $\textsc{B-Tree-Search}(x, k)$ — find key $k$ at or below node $x$
number: 1
$i \gets 1$
while $i \le n(x)$ and $k > key_i(x)$ do
  $i \gets i + 1$ // scan in-memory keys to the gap holding $k$
if $i \le n(x)$ and $k = key_i(x)$ then
  return $(x, i)$ // found in this node
if $leaf(x)$ then return nil // bottomed out: absent
$\textsc{Disk-Read}(child_i(x))$ // one block read to descend
return $\textsc{B-Tree-Search}(child_i(x), k)$
```

A search visits one node per level, $O(\log_t n)$ disk reads, each followed by an
$O(t)$ in-memory scan — $O(t\log_t n)$ comparisons total, $O(\log_t n)$ I/Os.

$$
% caption: Searching for $44$ in a B-tree of minimum degree $t = 3$. At the root, $44$ falls
%          between $30$ and $60$, so the search descends the middle child (blue path). There
%          $44$ falls between $40$ and $50$, descending again. The leaf scan finds $44$ (green).
%          One block read per level, an in-memory scan inside each node.
\begin{tikzpicture}[
  >=stealth,
  keynode/.style={draw, minimum height=6mm, inner sep=2pt, font=\small},
  onpath/.style={draw=acc, very thick, minimum height=6mm, inner sep=2pt, font=\small, fill=acc!12},
  found/.style={draw=green, very thick, minimum height=6mm, inner sep=2pt, font=\small, fill=green!14}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % root
  \node[onpath] (root) at (0,0) {\,$30\ \ 60$\,};
  % level 1
  \node[keynode] (a) at (-3.4,-1.7) {\,$8\ \ 17$\,};
  \node[onpath]  (b) at (0,-1.7) {\,$40\ \ 50$\,};
  \node[keynode] (c) at (3.4,-1.7) {\,$72\ \ 85$\,};
  \draw[->] (root.south) -- (a.north);
  \draw[acc, very thick, ->] (root.south) -- (b.north);
  \draw[->] (root.south) -- (c.north);
  % level 2 leaves under b
  \node[keynode] (l1) at (-1.1,-3.4) {\,$34$\,};
  \node[found]   (l2) at (0,-3.4) {\,$44$\,};
  \node[keynode] (l3) at (1.1,-3.4) {\,$55$\,};
  \draw[->] (b.south) -- (l1.north);
  \draw[acc, very thick, ->] (b.south) -- (l2.north);
  \draw[->] (b.south) -- (l3.north);
  % key range hints, stacked at the right margin clear of all arrows
  \node[acc, font=\scriptsize, anchor=west] at (4.4,-0.85) {$30 < 44 < 60$};
  \node[acc, font=\scriptsize, anchor=west] at (4.4,-2.55) {$40 < 44 < 50$};
\end{tikzpicture}
$$

## Insertion: split full nodes on the way down

A new key always lands in a **leaf** — but the leaf might already be full, and so
might its ancestors. B-trees handle this with one rule applied on the way down: as you descend
toward the target leaf, **proactively split every full node you pass through**.
That way, whenever you reach a node, its parent is guaranteed to have room to
absorb a key pushed up from a split, and the whole insertion makes a single
top-down pass.

**Splitting a full node.** A full child has $2t-1$ keys. To split it, take its
**median** key (the $t$-th), move that median _up_ into the parent (where it
becomes a new separator), and divide the remaining $2t-2$ keys into two nodes of
$t-1$ keys each — the left half and the right half. The parent gains one key and
one child; since we ensured the parent was not full before descending into it, it
has room.

$$
% caption: Splitting a full child ($t = 3$, so a full node has $2t-1 = 5$ keys). The median
%          $key_3$ rises into the parent as a new separator; the four remaining keys split into
%          two children of $t-1 = 2$ keys. The parent gains one key and one child pointer; the
%          tree grows wider, not taller (unless the root itself splits).
\begin{tikzpicture}[
  >=stealth,
  keynode/.style={draw, minimum height=6mm, inner sep=2pt, font=\small},
  full/.style={draw, minimum height=6mm, inner sep=2pt, font=\small, fill=acc!18, draw=acc, thick}]
  \definecolor{acc}{HTML}{2348F2}
  % --- before ---
  \node[keynode] (p) at (0,0) {\,$P_1\ \ P_2$\,};
  \node[full] (c) at (0,-1.5) {\,$a\ \ b\ \ \mathbf{m}\ \ c\ \ d$\,};
  \draw[->] (p.south) -- (c.north);
  \node[font=\scriptsize, acc, anchor=north] at (0,-2.0) {full: median $m$};
  % arrow
  \draw[->, very thick] (2.5,-0.75) -- node[above, font=\footnotesize] {split} (3.9,-0.75);
  % --- after ---
  \begin{scope}[xshift=64mm]
    \node[keynode] (p2) at (0,0) {\,$P_1\ \ \mathbf{m}\ \ P_2$\,};
    \node[font=\scriptsize, acc, anchor=south] at (0,0.35) {$m$ pushed up};
    \node[keynode] (cl) at (-1.5,-1.5) {\,$a\ \ b$\,};
    \node[keynode] (cr) at (1.5,-1.5) {\,$c\ \ d$\,};
    \draw[->] (p2.south) -- (cl.north);
    \draw[->] (p2.south) -- (cr.north);
  \end{scope}
\end{tikzpicture}
$$

If the **root** itself is full, we first make a brand-new empty root above it and
split the old root into two children. This is the _only_ way a B-tree grows
taller, and it happens at the top — which is precisely why all leaves stay at the
same depth: the tree never lengthens one path without lengthening all of them.[^erickson-btree]

$$
% caption: A full root ($t = 3$) splitting upward. Its median $h$ becomes the sole key of a new
%          root; the remaining keys divide into two children. This is the only event that adds a
%          level, and because it happens at the top, every leaf descends by the same one step —
%          so all leaves stay at equal depth.
\begin{tikzpicture}[
  >=stealth,
  keynode/.style={draw, minimum height=6mm, inner sep=2pt, font=\small},
  full/.style={draw=acc, thick, fill=acc!18, minimum height=6mm, inner sep=2pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % --- before: full root ---
  \node[full] (r) at (0,0) {\,$e\ \ f\ \ \mathbf{h}\ \ k\ \ n$\,};
  \node[font=\footnotesize, acc, anchor=north] at (0,-0.55) {full \texttt{root}: median $h$};
  % arrow
  \draw[->, very thick] (2.7,0) -- node[above, font=\footnotesize] {split} (4.1,0);
  % --- after: new root above two children ---
  \begin{scope}[xshift=66mm, yshift=8mm]
    \node[keynode] (nr) at (0,0) {\,$\mathbf{h}$\,};
    \node[font=\footnotesize, acc, anchor=south] at (0,0.35) {new \texttt{root}};
    \node[keynode] (cl) at (-1.5,-1.6) {\,$e\ \ f$\,};
    \node[keynode] (cr) at (1.5,-1.6) {\,$k\ \ n$\,};
    \draw[->] (nr.south) -- (cl.north);
    \draw[->] (nr.south) -- (cr.north);
  \end{scope}
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{B-Tree-Insert}(T, k)$ — insert key $k$, splitting full nodes top-down
number: 2
$r \gets root(T)$
if $r$ is full then // $2t-1$ keys
  $s \gets$ new empty node; $root(T) \gets s$ // grow upward at the root only
  $child_1(s) \gets r$; $\textsc{Split-Child}(s, 1)$ // split old root under new root
  $\textsc{Insert-Nonfull}(s, k)$
else
  $\textsc{Insert-Nonfull}(r, k)$
```

```algorithm
caption: $\textsc{Insert-Nonfull}(x, k)$ — insert $k$ into non-full node $x$'s subtree
number: 3
$i \gets n(x)$
if $leaf(x)$ then
  shift keys $> k$ right and place $k$ // simple in-block insert
else
  find child $i$ that should hold $k$
  if $child_i(x)$ is full then
    $\textsc{Split-Child}(x, i)$ // pre-split so the child has room
    if $k > key_i(x)$ then $i \gets i + 1$ // median may redirect us
  $\textsc{Insert-Nonfull}(child_i(x), k)$
```

Each split is $O(t)$ in-memory work plus $O(1)$ block writes, and there is at most
one split per level, so an insertion is $O(t\log_t n)$ time and $O(\log_t n)$ disk
I/Os — the same order as a search.

### A worked insertion

Take $t = 2$ (a **2-3-4 tree**: $1$ to $3$ keys per node, a full node has
$2t-1 = 3$ keys) and insert the keys $1, 2, 3, 4, 5, 6$ one at a time into an
empty tree. Small $t$ makes the splits fire often.

- **Insert $1, 2, 3$.** They land in the single leaf, which is also the root:
  the root becomes $[1\ 2\ 3]$, now **full**.
- **Insert $4$.** The insertion starts at the root, sees it is full, and splits it
  _first_: the median $2$ rises into a fresh root, leaving children $[1]$ and
  $[3]$. Now $4 > 2$, so descend right and place it: $[3\ 4]$.
- **Insert $5$.** Root $[2]$ is not full; $5 > 2$ sends us right into $[3\ 4]$,
  which has room, giving $[3\ 4\ 5]$ — now full.
- **Insert $6$.** Descend from root $[2]$; the target child $[3\ 4\ 5]$ is full,
  so pre-split it: median $4$ rises, root becomes $[2\ 4]$, children $[3]$ and
  $[5]$. Then $6 > 4$ sends us to $[5]$, giving $[5\ 6]$.

The tree ends as root $[2\ 4]$ over leaves $[1]$, $[3]$, $[5\ 6]$ — three keys
across the top, all leaves at depth $1$. Ascending inserts, which would drive a
naive BST to a degenerate list of height $6$, keep the B-tree at height $1$.

$$
% caption: Inserting $1,2,3,4,5,6$ into an empty B-tree with $t = 2$ (a 2-3-4 tree). Stage A:
%          the first three keys fill the root leaf. Stage B: inserting $4$ splits the full root,
%          lifting median $2$ into a new root. Stage C: after $5$ and $6$, the child $[3\,4\,5]$
%          splits, lifting $4$. The tree stays at height $1$ though the keys arrived in sorted order.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  kn/.style={draw, minimum height=6mm, inner sep=2.5pt, font=\small},
  full/.style={draw=acc, thick, fill=acc!14, minimum height=6mm, inner sep=2.5pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % --- stage A ---
  \begin{scope}
    \node[full] (a) at (0,0) {\,$1\ \ 2\ \ 3$\,};
    \node[anchor=north, font=\footnotesize] at (0,-0.55) {A: \texttt{root} full};
  \end{scope}
  % --- stage B ---
  \begin{scope}[xshift=34mm]
    \node[kn] (br) at (0,0) {\,$2$\,};
    \node[kn] (bl) at (-0.95,-1.4) {\,$1$\,};
    \node[kn] (bm) at (1.05,-1.4) {\,$3\ \ 4$\,};
    \draw[->] (br.south) -- (bl.north);
    \draw[->] (br.south) -- (bm.north);
    \node[anchor=north, font=\scriptsize] at (0,-2.15) {B: split lifts $2$};
  \end{scope}
  % --- stage C ---
  \begin{scope}[xshift=82mm]
    \node[kn] (cr) at (0,0) {\,$2\ \ 4$\,};
    \node[kn] (cl) at (-1.5,-1.4) {\,$1$\,};
    \node[kn] (cm) at (0,-1.4) {\,$3$\,};
    \node[kn] (cx) at (1.6,-1.4) {\,$5\ \ 6$\,};
    \draw[->] (cr.south) -- (cl.north);
    \draw[->] (cr.south) -- (cm.north);
    \draw[->] (cr.south) -- (cx.north);
    \node[anchor=north, font=\scriptsize] at (0,-2.15) {C: split lifts $4$};
  \end{scope}
\end{tikzpicture}
$$

## Deletion: borrow or merge to stay full enough

Deletion mirrors insertion. The risk is _underflow_: a node dropping
below $t-1$ keys. So as we descend toward the key to delete, we keep every node we
enter at $\ge t$ keys, fixing any child about to fall short _before_ recursing into
it, by one of two repairs:

- **Borrow** (rotate). If an immediate sibling has $\ge t$ keys to spare, move a
  separator key down from the parent into the deficient node and pull the
  sibling's adjacent key up into the parent. The deficient node gains a key; the
  sibling loses one but stays at $\ge t-1$.
- **Merge.** If both siblings sit at the minimum $t-1$, fuse the deficient node
  with a sibling and pull the separating key _down_ from the parent between them —
  producing a single node of $(t-1) + (t-1) + 1 = 2t-1$ keys, exactly full. The
  parent loses one key; if that empties the root, the merged node becomes the new
  root and the tree **shrinks by one level**.

Deleting a key that sits in an _internal_ node is handled by replacing it with its
predecessor or successor (the rightmost key of the left subtree, or leftmost of
the right), recursively, so that the actual removal always happens at a leaf —
just as in a BST. Like insertion, deletion is one root-to-leaf pass with $O(1)$
restructuring per level: $O(t\log_t n)$ time, $O(\log_t n)$ I/Os.

> **Invariant.** Every non-root node holds $\ge t-1$ keys, so it is at least
> half-full. This is what makes the height bound hold and keeps disk blocks from
> wasting space: a B-tree never lets a block dwindle to a handful of keys. Borrow
> and merge exist solely to restore this invariant after a removal.

### A worked deletion

Continue with a $t = 2$ tree — root $[10\ 20]$ over leaves $[4\ 7]$, $[13\ 16]$,
and $[24]$ — and delete keys to exercise both repairs. A non-root leaf must keep
$\ge t-1 = 1$ key.

- **Delete $16$** (borrow from the parent's key store is unnecessary here — the
  leaf $[13\ 16]$ has $2$ keys and drops to $[13]$, still $\ge 1$). No repair.
- **Delete $13$** next. Leaf $[13]$ would underflow to empty. Its left sibling
  $[4\ 7]$ has a spare key ($2 > t-1$), so **borrow**: the separator $10$ rotates
  _down_ from the root into the deficient leaf, and the sibling's largest key $7$
  rotates _up_ to become the new separator. Root becomes $[7\ 20]$, left leaf
  $[4]$, middle leaf $[10]$. Every node is legal again.
- **Delete $10$.** Middle leaf $[10]$ underflows. Now the left sibling $[4]$ sits
  at the minimum ($1$ key, nothing to spare) and so does the right sibling $[24]$,
  so borrowing is impossible — we **merge**. Fuse the middle leaf with its left
  sibling and pull the separator $7$ _down_ between them: the merged leaf is
  $[4\ 7]$ (using the emptied slot), and the root loses $7$, dropping to $[20]$.

$$
% caption: Deletion repairs on a $t = 2$ tree. Left: deleting $13$ underflows a leaf whose left
%          sibling has a spare key, so a BORROW rotates the separator $10$ down and the sibling's
%          $7$ up. Right: deleting $10$ underflows a leaf with only minimal siblings, so a MERGE
%          pulls the separator $7$ down and fuses two leaves into one, shrinking the parent.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  kn/.style={draw, minimum height=6mm, inner sep=2.5pt, font=\small},
  hot/.style={draw=acc, thick, fill=acc!12, minimum height=6mm, inner sep=2.5pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % --- borrow ---
  \begin{scope}
    \node[hot] (r) at (0,0) {\,$7\ \ 20$\,};
    \node[kn] (l) at (-1.5,-1.4) {\,$4$\,};
    \node[green!55!black, draw=green, thick, minimum height=6mm, inner sep=2.5pt, font=\small] (m) at (0,-1.4) {\,$10$\,};
    \node[kn] (x) at (1.5,-1.4) {\,$24$\,};
    \draw[->] (r.south) -- (l.north);
    \draw[->] (r.south) -- (m.north);
    \draw[->] (r.south) -- (x.north);
    \node[anchor=north, font=\footnotesize] at (0,-2.15) {\texttt{borrow}: $10$ down, $7$ up};
  \end{scope}
  % --- merge ---
  \begin{scope}[xshift=64mm]
    \node[hot] (r2) at (0,0) {\,$20$\,};
    \node[green!55!black, draw=green, thick, minimum height=6mm, inner sep=2.5pt, font=\small] (m2) at (-1.1,-1.4) {\,$4\ \ 7$\,};
    \node[kn] (x2) at (1.1,-1.4) {\,$24$\,};
    \draw[->] (r2.south) -- (m2.north);
    \draw[->] (r2.south) -- (x2.north);
    \node[anchor=north, font=\scriptsize] at (0,-2.15) {merge: $7$ down, leaves fused};
  \end{scope}
\end{tikzpicture}
$$

If a merge empties the root — because the root held a single key that was the
separator pulled down — the merged node becomes the new root and the tree loses a
level. That is the exact mirror of a root split: splits add height at the top,
merges remove it at the top, and both keep every leaf at the same depth.

::impl{algo="b_tree"}

## B+-trees: keys up top, data in the leaves

The variant deployed in nearly every database and filesystem is the **B+-tree**.
It differs in two ways. First, **all data records live in the leaves**; internal
nodes hold only **copies of keys as separators**, no payloads. Because separators
are small, an internal block fits _even more_ of them, raising the fan-out $t$ and
flattening the tree further. Second, the **leaves are linked** left-to-right into
a sorted list, so a range query — _"every key in $[l, r]$"_ — descends once to
find $l$, then walks the leaf chain, reading consecutive blocks sequentially
(the access pattern disks are fastest at) until it passes $r$.

$$
% caption: A B+-tree range scan for keys in $[17, 50]$. The internal nodes hold only separator
%          copies; all data sits in the leaves, which are linked left to right. The query
%          descends once to the leaf holding $17$ (blue), then walks the leaf chain reading
%          consecutive blocks (green) until it passes $50$ — the sequential pattern disks favour.
\begin{tikzpicture}[
  >=stealth,
  sep/.style={draw, minimum height=6mm, inner sep=2pt, font=\small},
  onpath/.style={draw=acc, very thick, fill=acc!12, minimum height=6mm, inner sep=2pt, font=\small},
  leaf/.style={draw, minimum height=6mm, inner sep=2pt, font=\footnotesize},
  scan/.style={draw=green, very thick, fill=green!14, minimum height=6mm, inner sep=2pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % internal separator node
  \node[onpath] (root) at (0,0) {\,$30\ \ 60$\,};
  % leaves, linked left to right
  \node[scan] (la) at (-3.2,-1.8) {\,$8\ \ 17$\,};
  \node[scan] (lb) at (0,-1.8) {\,$30\ \ 44$\,};
  \node[leaf] (lc) at (3.2,-1.8) {\,$60\ \ 85$\,};
  \draw[acc, very thick, ->] (root.south) -- (la.north);
  \draw[->] (root.south) -- (lb.north);
  \draw[->] (root.south) -- (lc.north);
  % leaf chain links
  \draw[green, very thick, ->] (la.east) -- (lb.west);
  \draw[->] (lb.east) -- (lc.west);
  % labels
  \node[acc, font=\scriptsize, anchor=south east] at (la.north west) {reach $17$};
  \node[green, font=\scriptsize, anchor=north] at (-1.6,-2.4) {walk leaf chain};
  \node[font=\scriptsize, anchor=north] at (0,-2.7) {stop after $50$};
\end{tikzpicture}
$$

$$
% caption: Where the data lives. In a plain B-tree (left) a key carries its data record wherever
%          it sits, so a record can appear in an internal node and stop a search early — the dots
%          mark stored records. In a B+-tree (right) internal nodes hold only separator copies;
%          every data record sits in a leaf, so the key $30$ appears twice: once as a bare
%          separator up top, once as a dotted record in a leaf. Leaves are linked left to right.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  kn/.style={draw, minimum height=6mm, inner sep=2.5pt, font=\small},
  dat/.style={draw=acc, fill=acc!10, minimum height=6mm, inner sep=2.5pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % a stored data record marker: small filled dot above-right of a key
  \newcommand{\rec}[1]{\fill[acc] ([shift={(0.02,0.12)}]#1) circle (1.4pt);}
  % --- plain B-tree: data everywhere ---
  \begin{scope}
    \node[dat] (r) at (0,0) {\,$30\ \ \ 60$\,};
    \node[dat] (l1) at (-1.7,-1.5) {\,$10$\,};
    \node[dat] (l2) at (0,-1.5) {\,$45$\,};
    \node[dat] (l3) at (1.7,-1.5) {\,$80$\,};
    \draw[->] (r.south) -- (l1.north);
    \draw[->] (r.south) -- (l2.north);
    \draw[->] (r.south) -- (l3.north);
    \rec{r.center}\rec{$(r.center)+(0.62,0)$}
    \rec{l1.center}\rec{l2.center}\rec{l3.center}
    \node[anchor=north, font=\footnotesize] at (0,-2.1) {B-tree: records at every \texttt{node}};
  \end{scope}
  % --- B+-tree: separators up, data in leaves ---
  \begin{scope}[xshift=74mm]
    \node[kn] (r2) at (0,0) {\,$30\ \ 60$\,};
    \node[dat] (a) at (-2.1,-1.5) {\,$10\ \ 30$\,};
    \node[dat] (b) at (0,-1.5) {\,$45$\,};
    \node[dat] (c) at (2.1,-1.5) {\,$60\ \ 80$\,};
    \draw[->] (r2.south) -- (a.north);
    \draw[->] (r2.south) -- (b.north);
    \draw[->] (r2.south) -- (c.north);
    \draw[->] (a.east) -- (b.west);
    \draw[->] (b.east) -- (c.west);
    \rec{$(a.center)+(0.38,0)$}\rec{b.center}\rec{$(c.center)+(-0.38,0)$}
    \node[anchor=north, font=\footnotesize] at (0,-2.1) {B+-tree: records only in \texttt{linked} leaves};
  \end{scope}
\end{tikzpicture}
$$

On the left, $30$ and $60$ carry their records in the root, so a lookup for either
finishes at the top. On the right, the same keys appear as bare separators up top
and again _with_ their records down in the leaves; every lookup runs the full
descent, but the leaves form a sorted linked list a range scan can walk.

> **Remark.** A plain B-tree can answer a point lookup slightly faster, since a
> key found high in the tree stops the descent early. The B+-tree gives that up in
> exchange for uniform leaf-depth lookups, denser internal nodes, and
> **efficient range scans** — the trade databases overwhelmingly prefer, because
> ordered scans and range predicates dominate their workloads.

::impl{algo="b_plus_tree"}

## B-trees run the storage world

The B-tree (Bayer and McCreight, 1972) is arguably the most consequential data
structure in software: essentially every relational database and filesystem stores
its indexes as a B+-tree, and the ideas around it are still evolving.

**The default index.** MySQL's InnoDB stores each table as a **clustered
B+-tree** keyed on the primary key, so the table _is_ its index; secondary indexes
are separate B+-trees pointing back at it. PostgreSQL's default index is a
B+-tree, and its concurrency comes from **Lehman-Yao B-link trees** (1981), which
add a right-sibling pointer at each level so readers never block on a concurrent
split. The leaf-linked-list range scan this lesson describes is what makes
`WHERE x BETWEEN a AND b` and `ORDER BY x` fast.

**The write-optimized challengers.** A B-tree's weakness is _write
amplification_: updating one key can rewrite a whole page. The **LSM-tree**
(log-structured merge tree) trades read speed for write speed by buffering updates
in memory and merging sorted runs to disk in the background, which is why
write-heavy stores (RocksDB, Cassandra, LevelDB) prefer it, each on-disk run
carrying the [Bloom filter](/algorithms/data-structures/skip-lists-and-probabilistic-structures)
that keeps negative lookups cheap. A middle path, the **B$^\varepsilon$-tree**
(and its "fractal tree" implementation in TokuDB), buffers pending updates inside
each internal node, getting near-B-tree reads with much better write throughput.

**Copy-on-write for crash safety.** Modern filesystems, **Btrfs** and **ZFS**,
store metadata in **copy-on-write B-trees**: an update copies the changed path to
new blocks rather than overwriting in place, so a crash always leaves a consistent
older tree, the persistence trick from balanced BSTs, applied to on-disk
storage.[^btb-btree]

## Takeaways

- On disk, the dominant cost is **block transfers**, paid per node touched. A
  binary tree of a billion keys is $\approx 30$ reads deep; a B-tree is $2$–$3$.
- A **B-tree of minimum degree $t$** holds $t-1$ to $2t-1$ keys per node
  (root: $\ge 1$), with $k+1$ children for $k$ keys, and **all leaves at one
  depth**.
- Minimum occupancy forces height $h \le \log_t\frac{n+1}{2} = O(\log_t n)$;
  the fan-out $t$ is the **base** of the log, so wide nodes mean shallow trees.
- **Insertion** descends once, **splitting every full node** it passes — push the
  median up, divide the rest into two half-full nodes. The tree grows taller only
  when the **root** splits, keeping all leaves level.
- **Deletion** descends once, keeping nodes $\ge t$ keys by **borrowing** from a
  rich sibling or **merging** two minimal siblings (which can shrink the tree).
- A **B+-tree** keeps all data in **linked leaves** with internal nodes as pure
  separators — higher fan-out and fast **range scans**, the structure databases
  and filesystems rely on.

[^clrs-btree]: **CLRS**, Ch. 18 — B-Trees: the minimum-degree definition, the $O(\log_t n)$ height bound, and split-on-descent insertion that minimizes disk transfers.
[^skiena-btree]: **Skiena**, §3.4 — Balanced Search Trees: B-trees as the on-disk balanced index trading binary depth for high fan-out.
[^erickson-btree]: **Erickson**, Ch. — Balanced Search Trees: multiway balanced trees and the all-leaves-at-one-depth invariant maintained by splitting and merging.
[^btb-btree]: Bayer & McCreight, "Organization and maintenance of large ordered indexes" (1972); Lehman & Yao, "Efficient locking for concurrent operations on B-trees" (B-link trees, 1981); O'Neil, Cheng, Gawlick & O'Neil, "The log-structured merge-tree" (1996); Brodal & Fagerberg, "Lower bounds for external memory dictionaries" (B$^\varepsilon$-trees, 2003).