Editing B+ tree (section)

=== Deletion ===
The purpose of the delete algorithm is to remove the desired entry node from the tree structure. We [[Recursive definition|recursively]] call the delete algorithm on the appropriate node until no node is found. For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root.

At entry L that we wish to remove:
* If L is at least half-full, done
* If L has only d-1 entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L).{{pb}}After the re-distribution of two sibling nodes happens, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key.
* If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L.

Note: merge could propagate to root, which means decreasing height.<ref>{{Cite book |last=Ramakrishnan |first=Raghu |title=Database management systems |date=2003 |publisher=McGraw-Hill |author2=Johannes Gehrke |isbn=0-07-246563-8 |edition=3rd |location=Boston |oclc=49977005}}</ref>
[[File:B+-tree-remove-61.png|thumb|B+ tree deletion|none]]