|
|
|
@article{DBLP:journals/tods/CulikOW81,
author = {Karel Culik II and
Thomas Ottmann and
Derick Wood},
title = {Dense Multiway Trees},
journal = {ACM Trans. Database Syst.},
volume = {6},
number = {3},
year = {1981},
pages = {486-512},
ee = {http://doi.acm.org/10.1145/319587.319612, db/journals/tods/CulikOW81.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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 O(log2 N) insertion algorithm. We also show that inserting mh-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."
Copyright © 1981 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.