Page 550 Exercise 15
This problem is virtually identical to the one described in
Exercise 17. Therefore, I'll describe and illustrate the splitting technique, and develop the splitting equations in this problem. In problem 16, we develop the algorithm.
Example : Assume that we have a Btree of order 4. The splitting
values would be:
P = ⌊ (2·2)/3⌋ = 2
Q = ⌊ (2·4-1)/3⌋ = 2
R = ⌊ (2·4)/3⌋ = 2
We want to insert 25 into the Btree which appears below.
|
The easiest, but not necessarily the most efficient, approach would "stuff" the values of P and Q, the Parent's i'th key, and the new value into an array in sorted order. This would give the following array of keys: 10, 15, 20, 25, 30, 35, 40, 45. The array's indices range from 1..2m. We now need to develop formulas to redistribute these values among P, Q, R, Parent's i'th key, and the Parent's i'th +1 key. These formulas are as follows:
(1) Place into P the values from Key 1 .. ⌊ (2m-2)/3⌋
(2) Place into Parenti the value in Key ⌊ (2m+1)/3 ⌋
(3) Place into Q the values from key m .. (m + ⌊ (2m-2)/3 ⌋ -1)
(4) Place into Parenti+1 the value in key (2m - ⌊ 2m/3 ⌋ )
(5) Place into R the values from Key (2m - ⌊ 2m/3⌋ +1) .. 2m
The results of splitting our original Btree appear below:
 |