Dense multiway trees

Abstract

B-trees of order m are a “balanced” class of m -ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced m -ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order m . Surprisingly, we are able to demonstrate that weakly dense multiway trees have an Ο (log ₂ N ) insertion algorithm. We also show that inserting m ^h - 1 keys in ascending order into an initially empty dense multiway tree yields the complete m -ary tree of height h , and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense m -ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”