Insert 50, 20, 70, 10, 30, 60, 80, 40, 90, 25 into an empty 2-3-4 tree. A node holds up to 3 keys in order and one more child than it has keys. Every key goes into a leaf, and a node that ends up with 4 keys splits in two around its middle key, which moves up to the parent. All leaves stay at the same depth, so the tree grows only when the root itself splits.
Inserting 10 keys into a 2-3-4 tree.
Insert 50. The root is a leaf, so the key goes straight in: 50.
Insert 50 into leaf 50.
Insert 20. The root is a leaf, so the key goes straight in: 20 50.
Insert 20 into leaf 20 50.
Insert 70. The root is a leaf, so the key goes straight in: 20 50 70.
Insert 70 into leaf 20 50 70.
Insert 10. The root is a leaf, so the key goes straight in: 10 20 50 70. That is 4 keys, one too many.
Insert 10 into leaf 10 20 50 70.
10 20 50 70 has 4 keys and the limit is 3, so it splits. The middle key, 50, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 10 20 50 70 around 50.
The root split, so there is no parent to receive 50: a new root holding just 50 is created above 10 20 and 70. This is the only way the tree gets taller, and every leaf moved down together, so they are still all at depth 2.
New root 50. Height 2.
Insert 30. From the root, at each node take the child between the keys that surround 30, down to the leaf 10 20, and slot it in order: 10 20 30.
Insert 30 into leaf 10 20 30.
Insert 60. From the root, at each node take the child between the keys that surround 60, down to the leaf 70, and slot it in order: 60 70.
Insert 60 into leaf 60 70.
Insert 80. From the root, at each node take the child between the keys that surround 80, down to the leaf 60 70, and slot it in order: 60 70 80.
Insert 80 into leaf 60 70 80.
Insert 40. From the root, at each node take the child between the keys that surround 40, down to the leaf 10 20 30, and slot it in order: 10 20 30 40. That is 4 keys, one too many.
Insert 40 into leaf 10 20 30 40.
10 20 30 40 has 4 keys and the limit is 3, so it splits. The middle key, 30, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 10 20 30 40 around 30.
10 20 stays as the left node, 40 is the new right node, and 30 joins the parent, now 30 50, between them.
Split done. Parent is 30 50.
Insert 90. From the root, at each node take the child between the keys that surround 90, down to the leaf 60 70 80, and slot it in order: 60 70 80 90. That is 4 keys, one too many.
Insert 90 into leaf 60 70 80 90.
60 70 80 90 has 4 keys and the limit is 3, so it splits. The middle key, 80, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 60 70 80 90 around 80.
60 70 stays as the left node, 90 is the new right node, and 80 joins the parent, now 30 50 80, between them.
Split done. Parent is 30 50 80.
Insert 25. From the root, at each node take the child between the keys that surround 25, down to the leaf 10 20, and slot it in order: 10 20 25.
Insert 25 into leaf 10 20 25.
10 keys in 5 nodes, height 2, after 3 splits. Every leaf is at the same depth, which is the guarantee: a lookup reads one node per level, and with hundreds of keys per node a real B-tree holds millions of keys at height three, which is why databases and file systems use it. The 2-3 and 2-3-4 trees are the same structure at the smallest sizes, and a 2-3-4 tree is a red-black tree drawn differently.
Height 2 after 3 splits.