Editing B-tree (section)

====Rebalancing after deletion====
Rebalancing starts from a leaf and proceeds toward the root until the tree is balanced. If deleting an element from a node has brought it under the minimum size, then some elements must be redistributed to bring all nodes up to the minimum. Usually, the redistribution involves moving an element from a sibling node that has more than the minimum number of nodes. That redistribution operation is called a '''rotation'''. If no sibling can spare an element, then the deficient node must be '''merged''' with a sibling. The merge causes the parent to lose a separator element, so the parent may become deficient and need rebalancing. The merging and rebalancing may continue all the way to the root. Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem. The algorithm to rebalance the tree is as follows:
* If the deficient node's right sibling exists and has more than the minimum number of elements, then rotate left
*# Copy the separator from the parent to the end of the deficient node (the separator moves down; the deficient node now has the minimum number of elements)
*# Replace the separator in the parent with the first element of the right sibling (right sibling loses one node but still has at least the minimum number of elements)
*# The tree is now balanced
* Otherwise, if the deficient node's left sibling exists and has more than the minimum number of elements, then rotate right
*# Copy the separator from the parent to the start of the deficient node (the separator moves down; deficient node now has the minimum number of elements)
*# Replace the separator in the parent with the last element of the left sibling (left sibling loses one node but still has at least the minimum number of elements)
*# The tree is now balanced
* Otherwise, if both immediate siblings have only the minimum number of elements, then merge with a sibling sandwiching their separator taken off from their parent
*# Copy the separator to the end of the left node (the left node may be the deficient node or it may be the sibling with the minimum number of elements)
*# Move all elements from the right node to the left node (the left node now has the maximum number of elements, and the right node – empty)
*# Remove the separator from the parent along with its empty right child (the parent loses an element)
*#* If the parent is the root and now has no elements, then free it and make the merged node the new root (tree becomes shallower)
*#* Otherwise, if the parent has fewer than the required number of elements, then rebalance the parent<ref>{{cite web |url=https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf |archive-date=2022-10-09 |url-status=live |title=Deletion in a B-tree |website=cs.rhodes.edu |access-date=24 May 2022}}</ref>

:<small>'''Note''': The rebalancing operations are different for B+ trees (e.g., rotation is different because parent has copy of the key) and B<sup>*</sup>-tree (e.g., three siblings are merged into two siblings).</small>