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 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:
- 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). - Insert 40 (root split): Because the root
[10 | 20 | 30]has 2t − 1 = 3 keys, it splits before descending. The median key20(at index t − 1 = 1) is promoted to a new root[20]with left child[10]and right child[30]. Key40is then inserted into the right leaf, yielding root[20]over[10]and[30 | 40]. - Insert 50: The root
[20]is not full, and its right child[30 | 40]has only 2 keys, so50is added directly to the right leaf:[30 | 40 | 50](now full with 3 keys). - Insert 60 (internal child split): Descending from root
[20]toward the full right child[30 | 40 | 50]triggers a preemptive split of that child: median40is promoted into the root to form[20 | 40], splitting the right child into[30]and[50]. Finally,60is 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:
- Move the Minimum Degree (t) slider from
3to2. Check the Properties card at the bottom of the panel:Min keys/node: 1andMax keys/node: 3. - Type
10,20, and30into 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]. - Insert
40. Observe the full root immediately split around median20into a two-level tree with root[20]and children[10]and[30 | 40]. - Insert
50and then60. Watch[30 | 40 | 50]split on the60insertion, promoting40into the root[20 | 40]while keeping all three leaf nodes on the exact same horizontal level. - Drag Minimum Degree (t) to
3(which resets the tree and raisesMax keys/nodeto5) 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:
- Bayer, R., & McCreight, E. M. (1972). Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1(3), 173–189.
- Morin, P. Open Data Structures, Chapter 14: B-Trees.
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 →