Java Reference
In-Depth Information
41
66
87
8
18
26
35
48
51
54
57
57
72
78
83
92
97
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
31
32
35
36
37
38
39
41
42
44
46
48
49
50
51
52
53
54
55
56
57
58
59
66
68
69
70
72
73
74
76
78
79
81
83
84
85
87
89
90
92
93
95
97
98
99
figure 19.86
Insertion of 55 in the B-tree shown in Figure 19.85 causes a split into two leaves.
Node splitting cre-
ates an extra child
for the leaf's parent.
If the parent already
has a full number of
children, we split
the parent.
and also the parent's parent, incurring an additional two disk writes (so this
insertion costs five disk writes). Again, however, the keys change in a very
controlled manner, although the code is certainly not simple because of the
number of cases involved.
When a nonleaf node is split, as here, its parent gains a child. What if the
parent already has reached its limit of children? Then we continue splitting
nodes up the tree until we find a parent that does not need to be split or we
reach the root. Note that we introduced this idea in bottom-up red-black trees
and AA-trees. If we split the root, we have two roots, but obviously, this out-
come is unacceptable. However, we can create a new root that has the split
roots as its two children, which is why the root is granted the special two-
child minimum exemption. It is also the only way that a B-tree gains height.
Needless to say, splitting all the way up to the root is an exceptionally rare
event because a tree with four levels indicates that the root has been split two
times throughout the entire sequence of insertions (assuming that no deletions
have occurred). In fact, splitting of any nonleaf node is also quite rare.
There are other ways to handle the overflowing of children. One tech-
nique is to put a child up for adoption should a neighbor have room. To insert
29 in the B-tree shown in Figure 19.87, for example, we could make room by
moving 32 to the next leaf. This technique requires a modification of the par-
ent because the keys are affected. However, it tends to keep nodes fuller and
saves space in the long run.
We can perform deletion by finding the item that needs to be removed and
removing it. The problem is that, if the leaf it was in had the minimum num-
ber of data items, it is now below the minimum. We can rectify the situation
by adopting a neighboring item, if the neighbor is not itself at its minimum. If
We may have to con-
tinue splitting all the
way up the tree
(though this possibil-
ity is unlikely). In the
worst case, we split
the root, creating a
new root with two
children.
Search WWH ::
Custom Search