An experimental study of insertion schemes for classes of multiway search trees

Abstract

Insertion schemes for various classes of multiway search trees have been implemented in PASCAL and experimentally studied. While the original B-tree insertion scheme does not consider brothers the dense m-ary-tree insertion scheme considers all brothers before splitting an overflowing node. There are many possible schemes in between these two extremes. We study the influence of the number of considered brothers, the splitting of an overflowing node with respect to the storage utilization and the number of input/output operations per insertion.

Keywords:

• Multiway
• search trees
• storage utilization

C.R. Categories:

• 3.73
• 3.74
• 4.34
• 5.25