-
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.
-
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
(Figure 11.13).
- Sometimes the pointers must be redistributed to keep the tree balanced.
- Deleting ``Perryridge'' from Figure 11.11 produces Figure 11.14.
-
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.
