Time- and space-optimality in B-trees

ABSTRACT

A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and compared with that of noncompact B-trees and with (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. The utility of initializing a B-tree to be compact (which initialization can be done in time linear in the number of keys if the keys are presorted) is demonstrated by comparing the space utilization of a compact tree that has been augmented by random insertions with that of a tree that has been grown entirely by random insertions. Even after increasing the number of keys by a modest amount, the effects of compact initialization are still felt. Once the tree has grown so large that these effects are no longer discernible, the tree can be expeditiously compacted in place using an algorithm presented here; and the benefits of compactness resume.

REFERENCES

• 1: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), 173-189.
• 2: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: MILLER, R.E., PIPPENGER, N., ROSENBERG, A.L., AND SNYDER, L. Optimal 2,3 trees. SIAM J. Cornput. 8, 1 (1979), 42-59.
• 5: ROSENBERG, A.L., AND SNYDER, L. Minimal comparison 2,3 trees. SIAM J. Comput. 7, 4 {1978), 465-480.
• 6: SNYDER, L. On uniquely represented data structures. Proc. 18th Annu. Conf. Foundations of Computer Science, 1977, pp. 412-417.
• 7: YAO, A.C. On random 2,3 trees. Acta Informatica 9, 3 (1978), 159-170.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Design

Keywords:
2, 3-tree, B-tree, bushy B-tree, compact B-tree, node-visit cost, space utilization