1. Insertions and Deletions:
Insertion and deletion are more complicated, as they may require splitting or combining nodes to keep the tree balanced. If splitting or combining are not required, insertion works as follows:
- Find leaf node where search key value should appear.
- If value is present, add new record to the bucket.
- If value is not present, insert value in leaf node (so that search keys are still in order).
- Create a new bucket and insert the new record.If splitting or combining are not required, deletion works as follows:
- Deletion: Find record to be deleted, and remove it from the bucket.
- If bucket is now empty, remove search key value from leaf node.
2. Insertions Causing Splitting:
When insertion causes a leaf node to be too large, we split that node. In Figure 11.8, assume we wish to insert a record with a bname value of "Clearview".
- There is no room for it in the leaf node where it should appear.
- We now have n values (the n - 1 search key values plus the new one we wish to insert).
- We put the first [n/2] values in the existing node, and the remainder into a new node.
- Figure 11.10 shows the result.
- The new node must be inserted into the B+-tree.
- We also need to update search key values for the parent (or higher) nodes of the split leaf node. (Except if the new node is the leftmost one)
- Order must be preserved among the search key values in each node.
- If the parent was already full, it will have to be split.
- When a non-leaf node is split, the children are divided among the two new nodes.
- In the worst case, splits may be required all the way up to the root. (If the root is split, the tree becomes one level deeper.)
- Note: when we start a B+-tree, we begin with a single node that is both the root and a single leaf.
When it gets full and another insertion occurs, we split it into two leaf nodes, requiring a new root.
3. Deletions Causing Combining:
Deleting records may cause tree nodes to contain too few pointers. Then we must combine nodes.
- If we wish to delete "Downtown" from the B+-tree of Figure 11.11, this occurs.
- In this case, the leaf node is empty and must be deleted.
- If we wish to delete "Perryridge" from the B+-tree of Figure 11.11, the parent is left with only one pointer, and must be coalesced with a sibling node.
- Sometimes higher-level nodes must also be coalesced.
- If the root becomes empty as a result, the tree is one level less deep (Figure 11.13).
- Sometimes the pointers must be redistributed to keep the tree balanced.
- Deleting "Perryridge" from Figure 11.11 produces Figure 11.14.
4. To summarize:
- Insertion and deletion are complicated, but require relatively few operations
- Number of operations required for insertion and deletion is proportional to logarithm of number of search keys.
- B+-trees are fast as index structures for database.
>