B-Trees

A red-black tree on the same keys needs about 30 levels. Explore the exact minimal-node-count tree the proof constructs (each • is a key; the highlighted level is the one being counted):

The height bound as code, computed instead of quoted: the loop adds up the fewest keys a height-h tree can have (the same count the proof makes), it is compared with the closed form 2th − 1, and maxHeight inverts it to ⌊logt((n+1)/2)⌋ with exact integers (the floating-point log version is shown only to warn you):

Input size → what is feasible. n = 10¹² keys, t = 2 → h ≤ 38; t = 10³ → h ≤ 3; maxHeight runs at most ~40 loop steps, so it is O(log_t n) for any n that fits in a 64-bit int (keep (n+1)·t < 9.2·10¹⁸).

2. Basic operations

Three conventions run through every algorithm below: the root is always assumed to already be in memory (no diskRead needed to reach it, but a diskWrite is still needed whenever it changes); every node passed as a parameter has already been read from disk by its caller; and every algorithm makes a single downward pass from the root — it never has to back up and revisit a node it already left, which is exactly what keeps disk accesses to O(h).

bTreeCreate(t)

Input size → what is feasible. t is any integer from 2 to 10⁵: one node allocation and one diskWrite regardless of t, so Θ(1) — a tree for n = 10⁹ starts exactly like a tree for n = 1.

bTreeCreate runs the same 4 rows no matter how big t is or how many keys will eventually be inserted — it is O(1) disk operations and O(1) CPU time, period. Three players: t = 2 (smallest legal degree), t = 1000 (a realistic disk-page-sized branching factor) and your own t. Each takes exactly 4 frames and 1 diskWrite, which shows CREATE is independent of t and n.

bTreeSearch(x, k)

Example 2 — the key is not in the tree. Watch what happens when the scan reaches a leaf and no key matches: there is nowhere left to descend, so the search reports the key is absent.

Example 3 — your own tree and target key. Build any tree and search it:

Running time. The scan inside one node costs O(t) CPU time (up to 2t − 1 keys, scanned linearly), and the search visits O(h) = O(logt n) nodes — one disk access per node beyond the (already-in-memory) root. Total: O(t · logt n) CPU time, O(logt n) disk accesses.

Input size → what is feasible. n = 10⁹, t = 1001 → at most 2 page reads and 2 · 2002 = 4004 key comparisons per lookup; t = 2 → at most 29 reads. A linear scan of all n keys (10⁹ steps ≈ 10 s) is only acceptable for n up to about 10⁴ keys.

bTreeSplitChild(x, i)

Example 1 — splitting a full leaf.

Example 2 — splitting a full internal node (notice the child pointers get redistributed too, not just the keys):

Example 3 — your own node to split:

Input size → what is feasible. t ≤ 1001: a split copies at most 2t − 1 = 2001 keys (Θ(t) CPU) but always costs exactly 3 diskWrites, and a single INSERT splits at most once per level (h ≤ 40).

bTreeSplitChild assumes x is not full but its child y = x.children[i] is full (exactly 2t − 1 keys). It creates a new node z, moves y's largest t − 1 keys (and, if internal, its largest t children) into z, shrinks y down to its smallest t − 1 keys, and inserts the one median key (plus a pointer to z) into x. Cost: Θ(t) CPU time (copying up to t keys/pointers) and exactly 3 disk writes (y, z, x) — O(1) disk operations.

bTreeInsert(tree, k) and bTreeInsertNonFull(x, k)

Example 1 — a mixed 19-key sequence: insert 40, 15, 70, 25, 90, 5, 60, 35, 80, 10, 55, 30, 95, 20, 65, 45, 85, 50, 75 one at a time into an empty B-tree with t = 2 and watch proactive splitting happen live:

Example 2 — ascending keys, t = 3. Inserting 1, 2, 3, … in increasing order always lands in the rightmost leaf, which fills up and splits over and over; every left half is left only minimally full (t−1 keys). Watch the height grow when the root fills:

Example 3 — your own minimum degree and key sequence:

bTreeInsert first checks only the root: if it's full, a brand-new empty root is created above it, and the (only) way a B-tree ever grows in height happens right here — the old root gets split as the new root's first (and, for a moment, only) child. Either way, bTreeInsertNonFull is then called, and it is a genuinely non-full node every single time it recurses — because any full child it is about to step into gets split first, bTreeInsertNonFull rows 18-19 — before the recursive call on row 22.

Running time. Exactly like search, both procedures do O(h) disk accesses (at most one diskRead per level going down, one diskWrite for the leaf, and 3 diskWrites per split, at most one split per level) and O(t · h) = O(t · logt n) CPU time (each level does O(t) work: a linear scan plus, sometimes, a split). Because bTreeInsertNonFull is tail-recursive (and directly usable in practice), it can be rewritten as a plain loop needing only O(1) pages in memory at any instant — never the whole root-to-leaf path at once.

Input size → what is feasible. n = 10⁶ keys inserted one by one with 2 ≤ t ≤ 16 → about 10⁸ simple steps (fine for ~1 s); one insert is at most h page reads and 3h + 1 page writes (checked above); inserting into a sorted array would cost up to n/2 = 5·10⁵ shifts per key instead.

3. Deleting a key

The strengthened invariant is the key idea: whenever bTreeDelete recurses into a node x, it guarantees x has at least t keys — one more than the bare minimum — so that even if we end up removing a key from x, it will never drop below the legal minimum of t − 1. This is arranged in two places: when the key to delete is found in an internal node (cases 2a/2b/2c), and when the key must be found by descending further (case 3, the "cases 3a/3b" preparation step below).

Deleting from a leaf — Case 1

Deleting a key found in an internal node — Cases 2a, 2b, 2c

Three fresh, independent trees below — each one isolates exactly ONE of the three cases so you can see it without any other case obscuring it:

Each case is one small function; the dispatcher deleteFrom further down calls them. Cases 2a and 2b first find the predecessor / successor; 2c and 3b share mergeChildren.

Descending through an underfull child — Cases 3a, 3b

Two more fresh, independent trees — one isolating case 3a (borrowing), one isolating case 3b (merging) and, immediately after, a second deletion on that same tiny tree that makes the ROOT itself disappear — the only way a B-tree's height ever decreases:

Example 4 — your own tree, minimum degree, and deletions (delete several keys in a row and watch the case label change live):

A five-step worked example. Starting from a t = 3 tree of 23 keys under the root [100], the player deletes 45, 80, 30, 10 and 70 in turn. Each step triggers a different case — 1, 2a, 2c, 3b (which also makes the root disappear) and 3a — and the scene label names the case the captions must agree with:

All six cases wired together — the whole bTreeDelete as one downward pass:

Running time. Exactly like insertion: O(h) disk accesses (the strengthened invariant needs at most one extra look at a sibling per level) and O(t · h) = O(t · logt n) CPU time.

Input size → what is feasible. n = 10⁶ deletions with 2 ≤ t ≤ 16 → about 10⁸ simple steps; each delete does at most about 4(h + 1) page reads and writes (the random test above measures a worst case below 4(h + 1)), where h ≤ 18 for t = 2.

4. From pseudocode to working Dart

The pseudocode in this lesson is already 0-indexed, exactly like Dart's List: x.keys[i] and x.children[i] mean the same thing in both. The invariant children.length == keys.length + 1 holds for every internal node, and when you scan with an index i, the child before keys[i] is children[i] and the child after it is children[i + 1]. Here is the complete, generic implementation (full source, exercised by 220 randomized trials plus every worked example above, lives in verify/c18.dart):

class BTreeNode<K extends Comparable> {
  BTreeNode(this.leaf);
  bool leaf;
  List<K> keys = [];
  List<BTreeNode<K>> children = [];
}

class BTree<K extends Comparable> {
  BTree(this.t) {
    if (t < 2) throw ArgumentError('minimum degree t must be >= 2');
  }
  final int t;
  BTreeNode<K>? root;
  int diskReads = 0;
  int diskWrites = 0;

  int get maxKeys => 2 * t - 1;
  int get minKeys => t - 1;

  // bTreeSearch(x, k)
  bool contains(K k) => root == null ? false : _search(root!, k, true);
  bool _search(BTreeNode<K> x, K k, bool isRoot) {
    if (!isRoot) diskReads++;
    var i = 0;
    while (i < x.keys.length && k.compareTo(x.keys[i]) > 0) {
      i++;
    }
    if (i < x.keys.length && k.compareTo(x.keys[i]) == 0) return true;
    if (x.leaf) return false;
    return _search(x.children[i], k, false);
  }

  // bTreeCreate + bTreeInsert
  void insert(K k) {
    if (root == null) {
      root = BTreeNode<K>(true); // bTreeCreate
      diskWrites++; // its diskWrite
    }
    final r = root!;
    if (r.keys.length == maxKeys) {
      final s = BTreeNode<K>(false);
      s.children.add(r);
      root = s;
      _splitChild(s, 0);
      _insertNonFull(s, k);
    } else {
      _insertNonFull(r, k);
    }
  }

  // bTreeSplitChild(x, i) — 0-indexed i, splits the FULL child x.children[i]
  void _splitChild(BTreeNode<K> x, int i) {
    final y = x.children[i];
    final z = BTreeNode<K>(y.leaf);
    z.keys = y.keys.sublist(t);
    if (!y.leaf) z.children = y.children.sublist(t);
    final median = y.keys[t - 1];
    y.keys = y.keys.sublist(0, t - 1);
    if (!y.leaf) y.children = y.children.sublist(0, t);
    x.children.insert(i + 1, z);
    x.keys.insert(i, median);
    diskWrites += 3; // y, z, x
  }

  // bTreeInsertNonFull(x, k)
  void _insertNonFull(BTreeNode<K> x, K k) {
    var i = x.keys.length - 1;
    if (x.leaf) {
      x.keys.add(k); // grow by one slot, then shift into place
      while (i >= 0 && k.compareTo(x.keys[i]) < 0) {
        x.keys[i + 1] = x.keys[i];
        i--;
      }
      x.keys[i + 1] = k;
      diskWrites++;
    } else {
      while (i >= 0 && k.compareTo(x.keys[i]) < 0) {
        i--;
      }
      i++;
      diskReads++;
      if (x.children[i].keys.length == maxKeys) {
        _splitChild(x, i);
        if (k.compareTo(x.keys[i]) > 0) i++;
      }
      _insertNonFull(x.children[i], k);
    }
  }
}

The full verify/c18.dart file also includes delete(k) (all six cases, plus the root-shrink check), inorder(), and checkInvariants() — the exact same logic this page's JavaScript animation engine runs, just translated line-for-line into 0-indexed Dart.

Quiz

Interview questions

Cheat sheet