B+Tree DELETION ALGORITHM: Rewritten by ad-at+di ** B+ Nodes maintain n-1 key values and n pointers 1. Find the entry to be deleted. 2. Delete entry from leaf. If this leaf, call it Z, is left with less than the required # of entries go to 3. Otherwise, Exit. 3. If neither the right nor the left sibling of Z (off the same parent) has more than ceil[(n-1)/2] then GoTo 4. Otherwise, redistribute the entries from ONE sibling with those in Z, so that half of the total are in sibling and half in Z. * If one of the siblings has more records than the other use it. * If both have the same # of keys, use the left one (arbitrary choice) Change the new distinguishing key of Z (from its sibling) in the parent and Exit. 4. Combine the entries of one sibling with those in Z. /* this happens only when BOTH ADJACENT siblings have exactly ceil[n/2] entries; u may choose the left sibling if there is one */ Delete from parent the distinguishing key of Z (from its siblings ) and delete the address of Z. If the parent is left with less than the necessary entries (sparse) GoTo 5. Otherwise, Exit. If the parent is the root, it cannot become sparse unless no value is left. In this case, the present node with the records of Z and its sibling, become the root which is now the entire tree. 5. Internal Node Redistribution: If an internal node is left sparse, temporarily concatanate this internal node with the larger of its siblings (or left if both are of equal size) ALONG WITH the key distinguishing it from its sibling. If there are exactly (n-1) keys in this concatanation GoTo 6. Otherwise (there are more than [n-1] keys), redistribute values by placing the new middle value in the parent in the place of the previous distinguishing value and Exit. 6. The (n-1) keys are now merged to become one internal node. The key and addresses in the parent are deleted. If the parent is too sparse GoTo 5. Otherwise, Exit.