When inserting a new key into an M-way search tree, if a node becomes full and needs to split, what happens to the median key?

When inserting a new key into an M-way search tree, if a node becomes full and needs to split, the median key is promoted to the parent node. Here are the steps:

1. Insert the new key into the appropriate node.
2. If the node is not full (i.e., has fewer than M-1 keys), you're done.
3. If the node is full (i.e., has M-1 keys), find the median key in the node.
4. Split the node into two nodes. The keys less than the median key go to the left node, and the keys greater than the median key go to the right node.
5. Promote the median key to the parent node. If the parent node is full, repeat the process from step 3.
6. If the root node is the one being split and it becomes full, create a new root and increase the height of the tree.

This process ensures that the M-way search tree remains balanced, with all leaf nodes at the same depth.