The definition of a B-tree stipulates that the nodes have to be half full, and the definition of a B*-tree increases this requirement to two-thirds. The reason for these requirements is to achieve reasonably good disk space utilization. However, it may be claimed that B-trees can perform very well requiring only that they include no empty nodes. To distinguish between these two cases, the B-trees discussed in this chapter are called merge-at-half B-trees, and the other type, when nodes must have at least one element, are called free-at-empty B-trees. It turns out, for example, that after free-at-empty B-tree is built and then each insertion is followed by deletion, the space utilization is about 39% (Johnson and Shasha 1993), which is not bad considering the fact that this type of tree can have very small space utilization ( 1 m % for a tree of order m), whereas a merge-at-half B-tree has at least 50% utilization. Therefore, it may be expected that if the number of insertions outweighs the number of deletions, the gap between merge-at-half and free-at-empty B-trees will be bridged. Write a simulation program to check the contention. First build a large B-tree, and then run a simulation for this tree treating it is a merge-at-half B-tree and then as a free-at-empty B-tree for different ratios of number i of insertions to number d of deletions so that i d 1 ; that is, the number of insertions is not less than the number of deletions (the case when deletions outweigh insertions is not interesting, because eventually the tree disappears). Compare the space utilization for the different cases. For what ratio i d is the space utilization between these two types of B-trees sufficiently close (say, within 5-10% difference)? After how many deletions and insertions is this similar utilization accomplished? One advantage of using free-at-empty trees would be to decrease the probability of tree restructuring. In all cases, compare the tree restructuring rate for both types of B-trees.