Insert 15, 3, 27, 8, 40, 12, 33, 19, 45, 5, 22, 38 into an empty B-tree with up to 4 keys per node. A node holds up to 4 keys in order and one more child than it has keys. Every key goes into a leaf, and a node that ends up with 5 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 12 keys into a B-tree with up to 4 keys per node.
Insert 15. The root is a leaf, so the key goes straight in: 15.
Insert 15 into leaf 15.
Insert 3. The root is a leaf, so the key goes straight in: 3 15.
Insert 3 into leaf 3 15.
Insert 27. The root is a leaf, so the key goes straight in: 3 15 27.
Insert 27 into leaf 3 15 27.
Insert 8. The root is a leaf, so the key goes straight in: 3 8 15 27.
Insert 8 into leaf 3 8 15 27.
Insert 40. The root is a leaf, so the key goes straight in: 3 8 15 27 40. That is 5 keys, one too many.
Insert 40 into leaf 3 8 15 27 40.
3 8 15 27 40 has 5 keys and the limit is 4, so it splits. The middle key, 15, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 3 8 15 27 40 around 15.
The root split, so there is no parent to receive 15: a new root holding just 15 is created above 3 8 and 27 40. 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 15. Height 2.
Insert 12. From the root, at each node take the child between the keys that surround 12, down to the leaf 3 8, and slot it in order: 3 8 12.
Insert 12 into leaf 3 8 12.
Insert 33. From the root, at each node take the child between the keys that surround 33, down to the leaf 27 40, and slot it in order: 27 33 40.
Insert 33 into leaf 27 33 40.
Insert 19. From the root, at each node take the child between the keys that surround 19, down to the leaf 27 33 40, and slot it in order: 19 27 33 40.
Insert 19 into leaf 19 27 33 40.
Insert 45. From the root, at each node take the child between the keys that surround 45, down to the leaf 19 27 33 40, and slot it in order: 19 27 33 40 45. That is 5 keys, one too many.
Insert 45 into leaf 19 27 33 40 45.
19 27 33 40 45 has 5 keys and the limit is 4, so it splits. The middle key, 33, moves up to the parent. The keys below it form the left node and the keys above it the right node.
Split 19 27 33 40 45 around 33.
19 27 stays as the left node, 40 45 is the new right node, and 33 joins the parent, now 15 33, between them.
Split done. Parent is 15 33.
Insert 5. From the root, at each node take the child between the keys that surround 5, down to the leaf 3 8 12, and slot it in order: 3 5 8 12.
Insert 5 into leaf 3 5 8 12.
Insert 22. From the root, at each node take the child between the keys that surround 22, down to the leaf 19 27, and slot it in order: 19 22 27.
Insert 22 into leaf 19 22 27.
Insert 38. From the root, at each node take the child between the keys that surround 38, down to the leaf 40 45, and slot it in order: 38 40 45.
Insert 38 into leaf 38 40 45.
12 keys in 4 nodes, height 2, after 2 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 2 splits.