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
If splitting or combining are not required, deletion 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.
- Deletion: Find record to be deleted, and remove it from the bucket.
- If bucket is now empty, remove search key value from leaf node.
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 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.
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
- Sometimes the pointers must be redistributed to keep the tree balanced.
- Deleting ``Perryridge'' from Figure 11.11 produces Figure 11.14.
- Insertion and deletion are complicated, but require relatively few
- 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.