Binary search trees - Data Structures and Problem Solving Using Java - page 759

The remaining issue is how to add and remove items from the B-tree. In
the ideas sketched, note that many themes presented earlier recur.

We begin by examining insertion. Suppose that we want to insert 57 into the
B-tree shown in Figure 19.84. A search down the tree reveals that 57 is not
already in the tree. We can add 57 to the leaf as a fifth item, but we may have to
reorganize all the data in the leaf to do so. However, the cost is negligible com-
pared to that of the disk access, which in this case also includes a disk write.

If the leaf contains
room for a new
item, we insert it
and are done.

That procedure was relatively painless because the leaf was not already
full. Suppose that we now want to insert 55. Figure 19.85 shows a problem:
The leaf where 55 should go is already full. The solution is simple: We now
have L + 1 items, so we split them into two leaves, both guaranteed to have the
minimum number of data records needed. Hence we form two leaves with
three items each. Two disk accesses are required to write these leaves and a
third disk access is required to update the parent. Note that in the parent, both
keys and branches change, but they do so in a controlled way that can easily
be calculated. The resulting B-tree is shown in Figure 19.86. Although split-
ting nodes is time consuming because it requires at least two additional disk
writes, it is a relatively rare occurrence. If L is 32, for example, when a node is
split two leaves with 16 and 17 items, respectively, are created. For the leaf
with 17 items, we can perform 15 more insertions without another split. Put
another way, for every split, there are roughly L / 2 nonsplits.
The node splitting in the preceding example worked because the parent
did not have its full complement of children. But what would happen if it did?
Suppose that we insert 40 into the B-tree shown in Figure 19.86. We must
split the leaf containing the keys 35 through 39 and now 40 into two leaves.
But doing so would give the parent six children, and it is allowed only five.
The solution is to split the parent, the result of which is shown in
Figure 19.87. When the parent is split, we must update the values of the keys

If the leaf is full, we
can insert a new
item by splitting the
leaf and forming
two half-empty
nodes.

41 66 87

8 18 26 35 48 51 54 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
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.85
The B-tree after insertion of 57 in the tree shown in Figure 19.84.