Computer Science

B-Tree Visualization

Visualize B-Tree node splitting, key insertion, and tree balancing with customizable degree parameters.

By Riano · Published · Updated · Report a correction

B-Tree

Concept Overview

A B-Tree is a self-balancing multi-way search tree in which each node stores multiple sorted keys and can branch to more than two children. By grouping up to 2t − 1 keys inside a single node and splitting full nodes preemptively on the way down during insertion, a B-Tree keeps all leaves at the exact same depth and bounds tree height to O(logt n), minimizing block reads in storage engines and databases.

Mathematical Definition

A B-Tree of minimum degree t (where t ≥ 2) satisfies the following structural invariants:

Every node contains at most 2t − 1 keys (and at most 2t children).
Every non-root node contains at least t − 1 keys (and at least t children if internal).
Every internal node with k keys has exactly k + 1 children.
All leaf nodes appear at the same depth.

Height h of a B-Tree storing n ≥ 1 keys satisfies:
h ≤ logt((n + 1) / 2)

Worked Example: Root & Child Splits at Minimum Degree t = 2

When t = 2 (a 2-3-4 tree), every node holds between t − 1 = 1 and 2t − 1 = 3 keys. Inserting the sequence 10, 20, 30, 40, 50, 60 demonstrates how preemptive splitting maintains uniform leaf depth:

  1. Insert 10, 20, 30: All three keys fit into the single root leaf in sorted order: [10 | 20 | 30] (size 3 = 2t − 1, now full).
  2. Insert 40 (root split): Because the root [10 | 20 | 30] has 2t − 1 = 3 keys, it splits before descending. The median key 20 (at index t − 1 = 1) is promoted to a new root [20] with left child [10] and right child [30]. Key 40 is then inserted into the right leaf, yielding root [20] over [10] and [30 | 40].
  3. Insert 50: The root [20] is not full, and its right child [30 | 40] has only 2 keys, so 50 is added directly to the right leaf: [30 | 40 | 50] (now full with 3 keys).
  4. Insert 60 (internal child split): Descending from root [20] toward the full right child [30 | 40 | 50] triggers a preemptive split of that child: median 40 is promoted into the root to form [20 | 40], splitting the right child into [30] and [50]. Finally, 60 is inserted into the rightmost leaf, producing root [20 | 40] with three leaves [10], [30], and [50 | 60].

Interactive Experiment: What to Enter and Observe

Open the B-Tree Visualization module to reproduce the split trace above and compare how minimum degree t controls tree height:

  1. Move the Minimum Degree (t) slider from 3 to 2. Check the Properties card at the bottom of the panel: Min keys/node: 1 and Max keys/node: 3.
  2. Type 10, 20, and 30 into the Insert key (e.g. 42) input (pressing Enter or the Insert key + button after each). Observe all three keys packed inside a single root node [10 | 20 | 30].
  3. Insert 40. Observe the full root immediately split around median 20 into a two-level tree with root [20] and children [10] and [30 | 40].
  4. Insert 50 and then 60. Watch [30 | 40 | 50] split on the 60 insertion, promoting 40 into the root [20 | 40] while keeping all three leaf nodes on the exact same horizontal level.
  5. Drag Minimum Degree (t) to 3 (which resets the tree and raises Max keys/node to 5) and click Random Insert six times: notice the first 5 keys stay in one root node and the 6th insertion triggers the first root split around the 3rd sorted key.

Assumptions & Limitations

This visualization implements Cormen et al.'s single-pass top-down preemptive split insertion, which splits any full node (2t − 1 keys) encountered on the search path from the root even if the eventual leaf split alone would not have cascaded all the way up. Duplicate keys are ignored so each key slot remains distinct on the canvas, and changing Minimum Degree (t) clears the tree because existing node capacities under a previous degree need not satisfy the new occupancy bounds [t − 1, 2t − 1]. Furthermore, standard B-Trees store keys and payloads in both internal and leaf nodes; production relational database indices typically use B+ Trees, which store all record payloads in linked leaf pages to optimize sequential range scans.

References

Bayer and McCreight introduced B-Trees for external block storage in 1972, and Pat Morin's Open Data Structures provides an open textbook analysis of B-Tree node splitting, height bounds, and external-memory I/O complexity:

Experience it interactively

Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive B-Tree Visualization module.

Try B-Tree Visualization on Riano →

More in Computer Science