It is possible to modify the B+-tree insertion algorithm to delay the case where a new level is produced by checking for a possible redistribution of values among the leaf nodes. Figure 17.17 illustrates how this could be done for our example in Figure 17.12; rather than splitting the leftmost leaf node when 12 is inserted, we do a left redistribution by moving 7 to the leaf node to its left (if there is space in this node). Figure 17.17 shows how the tree would look when redistribution is considered. It is also possible to consider right redistribution. Try to modify the B⁺-tree insertion algorithm to take redistribution into account.

Figure 17.17

Figure 17.12

10 30 50 70 80 -Insert 12: overflow (left redistribution) 3 7 1030 - 5 0 70 80 12 0 Insert 9: overflow (new level) 7 3 10 30 5|0|| 0 80 9 12 Insert 6: overflow (split) 7 3 6 9 30 50 60 70 - 30 90 - 12 0 8|0 Figure 17.17 B*-tree insertion with left redistribution.