B-Trees · study.

Red-black and AVL 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 $1 0^{9}$ keys has height $\approx 30$ , so a search is up to $30$ block reads — thirty trips to the disk for one lookup.¹

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 \geq 2$ is a search tree whose nodes hold a range of keys and children rather than just one key and two children.

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.

A B-tree of minimum degree

t = 3

(so

2

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.

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.

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} (1 0^{9}) \approx 30, log_{512} (1 0^{9}) = \frac{log _{2} 1 0 ^{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.²

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 1:

\textsc{B-Tree-Search}(x, k)

— find key

k

at or below node

x

1
$i \gets 1$
2
while $i \le n(x)$ and $k > key_i(x)$ do
3
$i \gets i + 1$
scan in-memory keys to the gap holding $k$
4
if $i \le n(x)$ and $k = key_i(x)$ then
5
return $(x, i)$
found in this node
6
if $leaf(x)$ then return nil
bottomed out: absent
7
$\textsc{Disk-Read}(child_i(x))$
one block read to descend
8
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.

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.

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 $2 t - 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 $2 t - 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.

Splitting a full child (

t = 3

, so a full node has

2 t - 1 = 5

keys). The median

k e y_{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).

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.³

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.

Algorithm 2:

\textsc{B-Tree-Insert}(T, k)

— insert key

k

, splitting full nodes top-down

1
$r \gets root(T)$
2
if $r$ is full then
$2t-1$ keys
3
$s \gets$ new empty node; $root(T) \gets s$
grow upward at the root only
4
$child_1(s) \gets r$ ; $\textsc{Split-Child}(s, 1)$
split old root under new root
5
$\textsc{Insert-Nonfull}(s, k)$
6
else
7
$\textsc{Insert-Nonfull}(r, k)$

Algorithm 3:

\textsc{Insert-Nonfull}(x, k)

— insert

k

into non-full node

x

's subtree

1
$i \gets n(x)$
2
if $leaf(x)$ then
3
shift keys $> k$ right and place $k$
simple in-block insert
4
else
5
find child $i$ that should hold $k$
6
if $child_i(x)$ is full then
7
$\textsc{Split-Child}(x, i)$
pre-split so the child has room
8
if $k > key_i(x)$ then $i \gets i + 1$
median may redirect us
9
$\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 $2 t - 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 $[123]$ , 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: $[34]$ .
Insert $5$ . Root $[2]$ is not full; $5 > 2$ sends us right into $[34]$ , which has room, giving $[345]$ — now full.
Insert $6$ . Descend from root $[2]$ ; the target child $[345]$ is full, so pre-split it: median $4$ rises, root becomes $[24]$ , children $[3]$ and $[5]$ . Then $6 > 4$ sends us to $[5]$ , giving $[56]$ .

The tree ends as root $[24]$ over leaves $[1]$ , $[3]$ , $[56]$ — 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$ .

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

[345]

splits, lifting

4

. The tree stays at height

1

though the keys arrived in sorted order.

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 $\geq 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 $\geq 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 $\geq 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 = 2 t - 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.

A worked deletion

Continue with a $t = 2$ tree — root $[1020]$ over leaves $[47]$ , $[1316]$ , and $[24]$ — and delete keys to exercise both repairs. A non-root leaf must keep $\geq t - 1 = 1$ key.

Delete $16$ (borrow from the parent's key store is unnecessary here — the leaf $[1316]$ has $2$ keys and drops to $[13]$ , still $\geq 1$ ). No repair.
Delete $13$ next. Leaf $[13]$ would underflow to empty. Its left sibling $[47]$ 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 $[720]$ , 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 $[47]$ (using the emptied slot), and the root loses $7$ , dropping to $[20]$ .

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.

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.

b_tree.pypython

from bisect import bisect_left, insort
from collections.abc import Iterator
from typing import Generic, Optional, TypeVar

from comparable import Comparable

Key = TypeVar("Key", bound=Comparable)

class BTreeNode(Generic[Key]):
  """
    One node of a B-tree: its sorted keys, its child links, and a flag\n
    marking whether it is a leaf. A node with k keys has k+1 children when\n
    it is internal and none when it is a leaf.\n
  """

  def __init__(self, is_leaf: bool) -> None:
    self.keys: list[Key] = []
    self.children: list[BTreeNode[Key]] = []
    self.is_leaf: bool = is_leaf

  def __repr__(self) -> str:
    return f"BTreeNode(keys={self.keys!r}, leaf={self.is_leaf})"

class BTree(Generic[Key]):
  """
    An ordered multiset-free set of comparable keys kept on disk-shaped\n
    nodes of minimum degree t. Supports membership, insertion, deletion,\n
    and an in-order traversal that yields the keys in sorted order.\n
  """

  def __init__(self, minimum_degree: int = 2) -> None:
    """
      Build an empty B-tree of the given minimum degree t (t >= 2).\n
      Every non-root node will hold between t-1 and 2t-1 keys.\n
    """
    if minimum_degree < 2:
      raise ValueError("minimum degree of a B-tree must be at least 2")
    self.minimum_degree: int = minimum_degree
    self.root: BTreeNode[Key] = BTreeNode(is_leaf=True)
    self.size: int = 0

  def __len__(self) -> int:
    return self.size

  def __contains__(self, key: Key) -> bool:
    return self._search(self.root, key) is not None

  def __iter__(self) -> Iterator[Key]:
    yield from self._in_order(self.root)

  @property
  def _max_keys(self) -> int:
    """
      The most keys a node may hold, 2t-1; a node at this count is full.\n
    """
    return 2 * self.minimum_degree - 1

  def _search(
    self, node: BTreeNode[Key], key: Key
  ) -> Optional[tuple[BTreeNode[Key], int]]:
    """
      The (node, index) pair where `key` lives at or below `node`, or\n
      None if it is absent. Each level scans the node's sorted keys for\n
      the gap holding the target, then descends the matching child.\n
    """
    current: BTreeNode[Key] = node
    while True:
      # binary-search the in-memory keys for the gap holding `key`.
      position: int = bisect_left(current.keys, key)
      if position < len(current.keys) and not (key < current.keys[position]):
        return current, position  # exact match in this node

      # not here: stop at a leaf, else descend the child at the gap.
      if current.is_leaf:
        return None
      current = current.children[position]

  def _split_child(self, parent: BTreeNode[Key], index: int) -> None:
    """
      Split the full child at `parent.children[index]` (it has 2t-1 keys).\n
      Its median rises into `parent` as a new separator, and the remaining\n
      2t-2 keys divide into two siblings of t-1 keys each. The parent gains\n
      one key and one child; it must not already be full.\n
    """
    # spin up a right sibling beside the full child and pick its median.
    degree: int = self.minimum_degree
    full_child: BTreeNode[Key] = parent.children[index]
    right_sibling: BTreeNode[Key] = BTreeNode(is_leaf=full_child.is_leaf)
    median_key: Key = full_child.keys[degree - 1]

    # the upper t-1 keys move to the new right sibling.
    right_sibling.keys = full_child.keys[degree:]
    full_child.keys = full_child.keys[: degree - 1]

    # an internal node hands off its upper t children too.
    if not full_child.is_leaf:
      right_sibling.children = full_child.children[degree:]
      full_child.children = full_child.children[:degree]

    # the median rises into the parent, with the sibling on its right.
    parent.keys.insert(index, median_key)
    parent.children.insert(index + 1, right_sibling)

  def insert(self, key: Key) -> bool:
    """
      Add `key` to the tree, splitting full nodes on the way down.\n
      Returns False (and leaves the tree unchanged) if the key is present.\n
    """
    if key in self:
      return False

    root: BTreeNode[Key] = self.root

    # a full root must split first — the only way the tree grows taller.
    if len(root.keys) == self._max_keys:
      new_root: BTreeNode[Key] = BTreeNode(is_leaf=False)
      new_root.children.append(root)
      self._split_child(new_root, 0)
      self.root = new_root
      root = new_root

    # descend into a guaranteed-non-full root and slot the key in.
    self._insert_nonfull(root, key)
    self.size += 1
    return True

  def _insert_nonfull(self, node: BTreeNode[Key], key: Key) -> None:
    """
      Insert `key` into the subtree at `node`, which is guaranteed not\n
      full. Leaves take the key directly; internal nodes pre-split a full\n
      target child so the recursion always meets a node with room.\n
    """
    if node.is_leaf:
      insort(node.keys, key)  # simple in-block insert into the sorted keys
      return

    # find the child that should hold `key`, pre-splitting it if full.
    position: int = bisect_left(node.keys, key)
    if len(node.children[position].keys) == self._max_keys:
      self._split_child(node, position)
      # the risen median may redirect us to the new right sibling.
      if node.keys[position] < key:
        position += 1

    self._insert_nonfull(node.children[position], key)

  def delete(self, key: Key) -> bool:
    """
      Remove `key` from the tree, borrowing or merging to keep every node\n
      visited at least t keys (so a child is never left underfull).\n
      Returns False if the key was not present.\n
    """
    if key not in self:
      return False

    self._delete(self.root, key)

    # a delete may empty the root; promote its lone child as the new root.
    if not self.root.is_leaf and len(self.root.keys) == 0:
      self.root = self.root.children[0]

    self.size -= 1
    return True

  def _delete(self, node: BTreeNode[Key], key: Key) -> None:
    """
      Delete `key` from the subtree rooted at `node`, assuming `node` has\n
      at least t keys (or is the root). Mirrors CLRS's three cases: removal\n
      from a leaf, replacement of an internal key by a predecessor or\n
      successor, and a guaranteeing fill before descending.\n
    """
    # locate `key` (or its gap) among this node's separators.
    degree: int = self.minimum_degree
    position: int = bisect_left(node.keys, key)

    # an exact hit needs the gap to land on a real, equal key.
    found_here: bool = position < len(node.keys) and not (
      key < node.keys[position]
    )

    if found_here and node.is_leaf:
      # case 1: the key sits in a leaf — just drop it.
      node.keys.pop(position)
      return

    if found_here:
      # case 2: the key sits in an internal node.
      self._delete_from_internal(node, position)
      return

    if node.is_leaf:
      return  # absent below this leaf (guarded by the membership check)

    # case 3: ensure child `position` has >= t keys before descending.
    last_child: bool = position == len(node.keys)
    if len(node.children[position].keys) < degree:
      self._fill_child(node, position)
      # a merge can shrink the key list, redirecting the descent.
      if last_child and position > len(node.keys):
        position -= 1

    self._delete(node.children[position], key)

  def _delete_from_internal(self, node: BTreeNode[Key], index: int) -> None:
    """
      Delete the key at `node.keys[index]` from an internal node by\n
      swapping in its predecessor or successor (whichever subtree is rich\n
      enough) and deleting that leaf key, or merging the two children when\n
      both are minimal.\n
    """
    # the key to remove and the two children flanking it.
    degree: int = self.minimum_degree
    key: Key = node.keys[index]
    left_child: BTreeNode[Key] = node.children[index]
    right_child: BTreeNode[Key] = node.children[index + 1]

    if len(left_child.keys) >= degree:
      # replace with the predecessor (rightmost key of the left subtree).
      predecessor: Key = self._max_key(left_child)
      node.keys[index] = predecessor
      self._delete(left_child, predecessor)
    elif len(right_child.keys) >= degree:
      # replace with the successor (leftmost key of the right subtree).
      successor: Key = self._min_key(right_child)
      node.keys[index] = successor
      self._delete(right_child, successor)
    else:
      # both children are minimal: fuse them around the key, then recurse.
      self._merge_children(node, index)
      self._delete(left_child, key)

  def _fill_child(self, node: BTreeNode[Key], index: int) -> None:
    """
      Ensure `node.children[index]` has at least t keys before a descent,\n
      by borrowing a key from an immediate sibling with one to spare, or\n
      else merging with a sibling.\n
    """
    degree: int = self.minimum_degree

    if index > 0 and len(node.children[index - 1].keys) >= degree:
      self._borrow_from_left(node, index)
    elif (
      index < len(node.keys)
      and len(node.children[index + 1].keys) >= degree
    ):
      self._borrow_from_right(node, index)
    elif index < len(node.keys):
      self._merge_children(node, index)
    else:
      # the deficient child is the last one: merge it into its left sibling.
      self._merge_children(node, index - 1)

  def _borrow_from_left(self, node: BTreeNode[Key], index: int) -> None:
    """
      Rotate a key right: the separator at `index-1` drops into the\n
      deficient child, and the left sibling's last key rises to replace it.\n
      The sibling's last child (if any) moves under the deficient child.\n
    """
    child: BTreeNode[Key] = node.children[index]
    left_sibling: BTreeNode[Key] = node.children[index - 1]

    # separator drops into the child; sibling's last key rises in its place.
    child.keys.insert(0, node.keys[index - 1])
    node.keys[index - 1] = left_sibling.keys.pop()
    if not left_sibling.is_leaf:
      child.children.insert(0, left_sibling.children.pop())

  def _borrow_from_right(self, node: BTreeNode[Key], index: int) -> None:
    """
      Rotate a key left: the separator at `index` drops into the deficient\n
      child, and the right sibling's first key rises to replace it. The\n
      sibling's first child (if any) moves under the deficient child.\n
    """
    child: BTreeNode[Key] = node.children[index]
    right_sibling: BTreeNode[Key] = node.children[index + 1]

    # separator drops into the child; sibling's first key rises in its place.
    child.keys.append(node.keys[index])
    node.keys[index] = right_sibling.keys.pop(0)
    if not right_sibling.is_leaf:
      child.children.append(right_sibling.children.pop(0))

  def _merge_children(self, node: BTreeNode[Key], index: int) -> None:
    """
      Merge `node.children[index]` with its right sibling, pulling the\n
      separating key at `index` down between them into one node of 2t-1\n
      keys. The parent loses that key and the now-empty right child link.\n
    """
    left_child: BTreeNode[Key] = node.children[index]
    right_child: BTreeNode[Key] = node.children[index + 1]

    # pull the separator down, append the right sibling, drop its link.
    left_child.keys.append(node.keys.pop(index))
    left_child.keys.extend(right_child.keys)
    left_child.children.extend(right_child.children)
    node.children.pop(index + 1)

  def _min_key(self, node: BTreeNode[Key]) -> Key:
    """
      The smallest key in the subtree at `node` (its leftmost leaf key).\n
    """
    current: BTreeNode[Key] = node
    while not current.is_leaf:
      current = current.children[0]
    return current.keys[0]

  def _max_key(self, node: BTreeNode[Key]) -> Key:
    """
      The largest key in the subtree at `node` (its rightmost leaf key).\n
    """
    current: BTreeNode[Key] = node
    while not current.is_leaf:
      current = current.children[-1]
    return current.keys[-1]

  def minimum(self) -> Optional[Key]:
    """
      The smallest key in the tree, or None if the tree is empty.\n
    """
    return self._min_key(self.root) if self.size > 0 else None

  def maximum(self) -> Optional[Key]:
    """
      The largest key in the tree, or None if the tree is empty.\n
    """
    return self._max_key(self.root) if self.size > 0 else None

  def height(self) -> int:
    """
      The height of the tree in edges, with -1 for an empty tree. Because\n
      all leaves share a depth, one descent down the leftmost spine suffices.\n
    """
    if self.size == 0:
      return -1

    # all leaves share a depth, so count levels down the leftmost spine.
    levels: int = 0
    current: BTreeNode[Key] = self.root
    while not current.is_leaf:
      levels += 1
      current = current.children[0]

    return levels

  def _in_order(self, node: BTreeNode[Key]) -> Iterator[Key]:
    """
      Yield the keys of the subtree at `node` in ascending order, weaving\n
      each child between consecutive separator keys.\n
    """
    if node.is_leaf:
      yield from node.keys
      return

    # interleave each separator with the child subtree to its left.
    for index, key in enumerate(node.keys):
      yield from self._in_order(node.children[index])
      yield key

    yield from self._in_order(node.children[len(node.keys)])

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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$ .

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.

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.

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.

b_plus_tree.pypython

from bisect import bisect_left, bisect_right
from collections.abc import Iterator
from typing import Any, Generic, Optional, Protocol, TypeVar

class Comparable(Protocol):
  """
    Anything that supports a strict ordering, i.e. the `<` operator.\n
    The argument is position-only so built-ins (int, str, …), whose\n
    `__lt__` takes a position-only operand, satisfy the protocol.\n
  """

  def __lt__(self, other: Any, /) -> bool: ...

Key = TypeVar("Key", bound=Comparable)
Value = TypeVar("Value")

class BPlusInternalNode(Generic[Key, Value]):
  """
    An internal B+-tree node: separator keys and one more child than keys.\n
    Its keys are copies used only to route a search; the real data never\n
    lives here. The separator at index i is the smallest key reachable in\n
    `children[i + 1]`.\n
  """

  def __init__(self) -> None:
    self.keys: list[Key] = []
    self.children: list[
      BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value]
    ] = []
    self.is_leaf: bool = False

  def __repr__(self) -> str:
    return f"BPlusInternalNode(keys={self.keys!r})"

class BPlusLeafNode(Generic[Key, Value]):
  """
    A leaf B+-tree node: the actual (key, value) records in sorted order,\n
    plus a `next_leaf` link threading every leaf into one left-to-right\n
    sorted list for sequential range scans.\n
  """

  def __init__(self) -> None:
    self.keys: list[Key] = []
    self.values: list[Value] = []
    self.next_leaf: Optional[BPlusLeafNode[Key, Value]] = None
    self.is_leaf: bool = True

  def __repr__(self) -> str:
    return f"BPlusLeafNode(keys={self.keys!r})"

class BPlusTree(Generic[Key, Value]):
  """
    An ordered key-to-value map kept on a B+-tree of order t. Keys are\n
    unique; re-inserting an existing key overwrites its value. Supports\n
    point lookup, insertion, deletion, an in-order item traversal, and an\n
    inclusive range scan that walks the linked leaves.\n
  """

  def __init__(self, order: int = 4) -> None:
    """
      Build an empty B+-tree of the given order t (t >= 3). A node holds at\n
      most t-1 keys and, when it splits, divides around its median.\n
    """
    if order < 3:
      raise ValueError("order of a B+-tree must be at least 3")
    self.order: int = order
    self.root: BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value] = (
      BPlusLeafNode()
    )
    self.size: int = 0

  def __len__(self) -> int:
    return self.size

  def __contains__(self, key: Key) -> bool:
    return self.get(key) is not None

  def __iter__(self) -> Iterator[Key]:
    """
      Yield every stored key in ascending order by walking the leaf chain.\n
    """
    leaf: Optional[BPlusLeafNode[Key, Value]] = self._leftmost_leaf()
    while leaf is not None:
      yield from leaf.keys
      leaf = leaf.next_leaf

  @property
  def _max_keys(self) -> int:
    """
      The most keys any node may hold before it must split, t-1.\n
    """
    return self.order - 1

  def _find_leaf(self, key: Key) -> BPlusLeafNode[Key, Value]:
    """
      The leaf that would hold `key`, found by routing through separators.\n
    """
    node: BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value] = self.root
    while isinstance(node, BPlusInternalNode):
      # descend the child just right of the last separator <= key.
      position: int = bisect_right(node.keys, key)
      node = node.children[position]
    return node

  def get(self, key: Key) -> Optional[Value]:
    """
      The value stored under `key`, or None if the key is absent.\n
    """
    # route to the leaf, then check the slot bisect would place the key in.
    leaf: BPlusLeafNode[Key, Value] = self._find_leaf(key)
    position: int = bisect_left(leaf.keys, key)
    if position < len(leaf.keys) and not (key < leaf.keys[position]):
      return leaf.values[position]
    return None

  def _leftmost_leaf(self) -> BPlusLeafNode[Key, Value]:
    """
      The first leaf in the chain (head of the sorted leaf list).\n
    """
    node: BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value] = self.root
    while isinstance(node, BPlusInternalNode):
      node = node.children[0]
    return node

  def insert(self, key: Key, value: Value) -> None:
    """
      Store `value` under `key`, overwriting any existing value. A leaf\n
      that overflows splits and propagates a separator up, growing the tree\n
      taller only when the root itself splits.\n
    """
    split: Optional[
      tuple[Key, BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value]]
    ] = self._insert(self.root, key, value)

    if split is not None:
      # the root split: build a new root above the two halves.
      separator_key, right_node = split
      new_root: BPlusInternalNode[Key, Value] = BPlusInternalNode()
      new_root.keys.append(separator_key)
      new_root.children.append(self.root)
      new_root.children.append(right_node)
      self.root = new_root

  def _insert(
    self,
    node: BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value],
    key: Key,
    value: Value,
  ) -> Optional[
    tuple[Key, BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value]]
  ]:
    """
      Insert `(key, value)` into the subtree at `node`. Returns None if it\n
      fit, or `(separator, right)` describing a split that the parent must\n
      absorb: `right` is the new right node and `separator` routes to it.\n
    """
    if isinstance(node, BPlusLeafNode):
      return self._insert_into_leaf(node, key, value)

    position: int = bisect_right(node.keys, key)
    split = self._insert(node.children[position], key, value)
    if split is None:
      return None

    # a child split: weave the new separator and right child into place.
    separator_key, right_node = split
    node.keys.insert(position, separator_key)
    node.children.insert(position + 1, right_node)
    if len(node.keys) > self._max_keys:
      return self._split_internal(node)
    return None

  def _insert_into_leaf(
    self, leaf: BPlusLeafNode[Key, Value], key: Key, value: Value
  ) -> Optional[tuple[Key, BPlusLeafNode[Key, Value]]]:
    """
      Place `(key, value)` in a leaf, overwriting a duplicate, and split\n
      the leaf if it overflows. A leaf split copies (does not move) the new\n
      right leaf's first key up as the separator.\n
    """
    position: int = bisect_left(leaf.keys, key)
    if position < len(leaf.keys) and not (key < leaf.keys[position]):
      leaf.values[position] = value  # overwrite an existing key
      return None

    leaf.keys.insert(position, key)
    leaf.values.insert(position, value)
    self.size += 1

    if len(leaf.keys) <= self._max_keys:
      return None

    # the upper half moves to a fresh right leaf; the lower half stays.
    midpoint: int = len(leaf.keys) // 2
    right_leaf: BPlusLeafNode[Key, Value] = BPlusLeafNode()
    right_leaf.keys = leaf.keys[midpoint:]
    right_leaf.values = leaf.values[midpoint:]
    leaf.keys = leaf.keys[:midpoint]
    leaf.values = leaf.values[:midpoint]

    # splice the new leaf into the chain and copy its first key up.
    right_leaf.next_leaf = leaf.next_leaf
    leaf.next_leaf = right_leaf
    return right_leaf.keys[0], right_leaf

  def _split_internal(
    self, internal: BPlusInternalNode[Key, Value]
  ) -> tuple[Key, BPlusInternalNode[Key, Value]]:
    """
      Split an overfull internal node around its median key, which moves\n
      up (not copied) as the separator; its left children stay, its right\n
      children go to the new right node. Returns `(separator, right)`.\n
    """
    # the median key moves up; everything above it goes to the right node.
    midpoint: int = len(internal.keys) // 2
    separator_key: Key = internal.keys[midpoint]

    right_internal: BPlusInternalNode[Key, Value] = BPlusInternalNode()
    right_internal.keys = internal.keys[midpoint + 1:]
    right_internal.children = internal.children[midpoint + 1:]

    # the left node keeps the keys below the median and their children.
    internal.keys = internal.keys[:midpoint]
    internal.children = internal.children[: midpoint + 1]
    return separator_key, right_internal

  def range(self, low: Key, high: Key) -> Iterator[tuple[Key, Value]]:
    """
      Yield every `(key, value)` with low <= key <= high in ascending\n
      order. Descends once to the leaf holding `low`, then walks the linked\n
      leaf chain reading consecutive leaves until a key exceeds `high`.\n
    """
    # descend once to the leaf holding `low`, then walk the leaf chain.
    leaf: Optional[BPlusLeafNode[Key, Value]] = self._find_leaf(low)
    start: int = bisect_left(leaf.keys, low)
    while leaf is not None:
      for index in range(start, len(leaf.keys)):
        key: Key = leaf.keys[index]
        if high < key:
          return
        yield key, leaf.values[index]
      leaf = leaf.next_leaf
      start = 0

  def items(self) -> Iterator[tuple[Key, Value]]:
    """
      Yield every stored `(key, value)` in ascending key order.\n
    """
    leaf: Optional[BPlusLeafNode[Key, Value]] = self._leftmost_leaf()
    while leaf is not None:
      yield from zip(leaf.keys, leaf.values)
      leaf = leaf.next_leaf

  def delete(self, key: Key) -> bool:
    """
      Remove `key` and its value. Returns False if the key was absent.\n
      Leaves may fall below half capacity here; this implementation keeps\n
      them in the chain and re-balances lazily on the next structural pass,\n
      preserving correct ordering and the sorted leaf list.\n
    """
    # locate the leaf that would hold the key, and bail if it is absent.
    leaf: BPlusLeafNode[Key, Value] = self._find_leaf(key)
    position: int = bisect_left(leaf.keys, key)
    if position >= len(leaf.keys) or key < leaf.keys[position]:
      return False

    # remove the record in place.
    leaf.keys.pop(position)
    leaf.values.pop(position)
    self.size -= 1

    # collapse a degenerate root that lost its last separator.
    root: BPlusInternalNode[Key, Value] | BPlusLeafNode[Key, Value] = self.root
    while isinstance(root, BPlusInternalNode) and len(root.keys) == 0:
      root = root.children[0]
    self.root = root
    return True

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 that keeps negative lookups cheap. A middle path, the B $^{ε}$ -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.⁴

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 $2 t - 1$ keys per node (root: $\geq 1$ ), with $k + 1$ children for $k$ keys, and all leaves at one depth.
Minimum occupancy forces height $h \leq 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 $\geq 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, 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, §3.4 — Balanced Search Trees: B-trees as the on-disk balanced index trading binary depth for high fan-out. ↩
Erickson, Ch. — Balanced Search Trees: multiway balanced trees and the all-leaves-at-one-depth invariant maintained by splitting and merging. ↩
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 $^{ε}$ -trees, 2003). ↩