How to use the B-Tree Insertion Visualizer
- 1. Enter the keysNumbers or letters in insertion order, separated by spaces or commas.
- 2. Pick the orderOrder m (max m − 1 keys per node) or Cormen's minimum degree t (max 2t − 1 keys).
- 3. Follow the stepsEach step lists where the key went, any overflow and split, and shows the tree with the new key highlighted.
B-tree insertion rules
In a B-tree of order m every node has at most m children and m − 1 keys, every node except the root has at least ⌈m/2⌉ − 1 keys, and all leaves are at the same depth.
- Search down to the leaf where the key belongs and insert it in sorted order.
- If the leaf now has m keys, split it: the middle key moves up to the parent, and the keys on either side become two nodes.
- If the parent overflows, split it the same way. A split at the root makes a new root, which is the only way the tree gets taller.
Cormen (CLRS) uses minimum degree t and splits any full node on the way down, so a parent always has room.
Worked example: order 5
Insert C N G A H E K Q M F W L T Z D P R X Y S with m = 5 (at most 4 keys per node).
- C, N, G, A fill one leaf: [A C G N].
- H makes [A C G H N], 5 keys. The middle key G moves up: root [G], leaves [A C] and [H N].
- E, K, Q give [A C E] and [H K N Q]. M overflows that leaf and moves up: root [G M].
After all 20 keys the tree has height 2: root [M], then [D G] and [Q T], then leaves [A C] [E F] [H K L] [N P] [R S] [W X Y Z].
Frequently asked questions
Which middle key moves up when m is even?
With m = 4 an overflowing node has 4 keys and two middles. Books differ, so the tool lets you choose left or right middle.
Why do CLRS answers differ from my textbook?
CLRS splits full nodes on the way down, before inserting. Many textbooks split only after a node overflows. Both give valid B-trees, but the shapes can differ.
What happens with duplicate keys?
They are skipped and listed under the steps, since a B-tree used as an index stores each key once.