Insert 10, 20, 30, 40, 50, 60, 70 into an empty 2-3 tree. A node holds up to 2 keys in order and one more child than it has keys. Every key goes into a leaf, and a node that ends up with 3 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 7 keys into a 2-3 tree.
Insert 10. The root is a leaf, so the key goes straight in: 10.
Insert 10 into leaf 10.
Insert 20. The root is a leaf, so the key goes straight in: 10 20.
Insert 20 into leaf 10 20.
Insert 30. The root is a leaf, so the key goes straight in: 10 20 30. That is 3 keys, one too many.
Insert 30 into leaf 10 20 30.
10 20 30 has 3 keys and the limit is 2, so it splits. The middle key, 20, 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 around 20.
The root split, so there is no parent to receive 20: a new root holding just 20 is created above 10 and 30. 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 20. Height 2.
Insert 40. From the root, at each node take the child between the keys that surround 40, down to the leaf 30, and slot it in order: 30 40.
Insert 40 into leaf 30 40.
Insert 50. From the root, at each node take the child between the keys that surround 50, down to the leaf 30 40, and slot it in order: 30 40 50. That is 3 keys, one too many.
Insert 50 into leaf 30 40 50.
30 40 50 has 3 keys and the limit is 2, so it splits. The middle key, 40, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 30 40 50 around 40.
30 stays as the left node, 50 is the new right node, and 40 joins the parent, now 20 40, between them.
Split done. Parent is 20 40.
Insert 60. From the root, at each node take the child between the keys that surround 60, down to the leaf 50, and slot it in order: 50 60.
Insert 60 into leaf 50 60.
Insert 70. From the root, at each node take the child between the keys that surround 70, down to the leaf 50 60, and slot it in order: 50 60 70. That is 3 keys, one too many.
Insert 70 into leaf 50 60 70.
50 60 70 has 3 keys and the limit is 2, so it splits. The middle key, 60, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 50 60 70 around 60.
50 stays as the left node, 70 is the new right node, and 60 joins the parent, now 20 40 60, between them. The parent overflows in turn.
Split done. Parent is 20 40 60.
20 40 60 has 3 keys and the limit is 2, so it splits. The middle key, 40, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 20 40 60 around 40.
The root split, so there is no parent to receive 40: a new root holding just 40 is created above 20 and 60. This is the only way the tree gets taller, and every leaf moved down together, so they are still all at depth 3.
New root 40. Height 3.
7 keys in 7 nodes, height 3, after 4 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 3 after 4 splits.