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 a new key is inserted into an M-way search tree and a node becomes full, causing it to split, the median key is moved up to the parent node.

Here are the steps:

1. Insert the new key into the appropriate node.
2. If the node is not full after the insertion, then the process stops.
3. If the node is full after the insertion (i.e., it now contains M keys), then it must be split.
4. Find the median key in the node. If M is even, the median key is the M/2-th key. If M is odd, the median key is the (M+1)/2-th key.
5. Move the median key up to the parent node. If the parent node is full, then it will also split, and its median key will move up to its parent node. This process continues until a parent node is found that does not need to split.
6. The keys to the left of the median key form a new node and become the left child of the median key in the parent node. The keys to the right of the median key form another new node and become the right child of the median key in the parent node.
7. If the median key was the root of the tree (i.e., the tree height increases), then a new root is created with the median key as its only key and the two new nodes as its children.