Which element is the 'middle' in a B-Tree of even order?

Question

If I have an B-Tree of order 4 with the following data in it...

and I need to add 2 to the tree; do I...

1. add the 2 to the node (making it invalid, as it now has 4 keys), then split the node, taking the value 2 as the middle value and propagating it up

OR

2. do I not add the 2, take 3 as the middle value, propagate 3 up, then add 2 into the correct node?

Excuse the poor diagram.

Answer 1

You perform the first option. For a B-tree of any order you always add the node then perform splits that propagate upwards. For a great interactive demonstration of a variety of basic (insert, delete, search) operations on data structures, there is a useful algorithm visualization page I go to located here. Find the B-tree page and you will find that it performs option 1.