Time- and Space-Optimality in B-Trees.

Arnold L. Rosenberg, Lawrence Snyder: Time- and Space-Optimality in B-Trees. ACM Trans. Database Syst. 6(1): 174-193(1981)

@article{DBLP:journals/tods/RosenbergS81,
  author    = {Arnold L. Rosenberg and
               Lawrence Snyder},
  title     = {Time- and Space-Optimality in B-Trees},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {1},
  year      = {1981},
  pages     = {174-193},
  ee        = {http://doi.acm.org/10.1145/319540.319565, db/journals/tods/RosenbergS81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Discussion

Jürgen Klonk: Comments on Optimality of B-Trees. SIGMOD Record 13(2): 35-38(1983) BibTeX

References

[1]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[2]: Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX
[3]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[4]: Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder: Optimal 2, 3-Trees. SIAM J. Comput. 8(1): 42-59(1979) BibTeX
[5]: Arnold L. Rosenberg, Lawrence Snyder: Minimal-Comparison 2, 3-Trees. SIAM J. Comput. 7(4): 465-480(1978) BibTeX
[6]: Lawrence Snyder: On Uniquely Represented Data Structures (Extended Abstract). FOCS 1977: 142-146 BibTeX
[7]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

Scott T. Leutenegger, David M. Nicol: Efficient Bulk-Loading of Gridfiles. IEEE Trans. Knowl. Data Eng. 9(3): 410-420(1997)
Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506
Jianzhong Li, Doron Rotem, Jaideep Srivastava: Algorithms for Loading Parallel Grid Files. SIGMOD Conference 1993: 347-356
Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
Shou-Hsuan Stephen Huang: Height-Balanced Trees of Order (beta,gamma,delta). ACM Trans. Database Syst. 10(2): 261-284(1985)
David M. Arnow, Aaron M. Tenenbaum: An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees. SIGMOD Conference 1984: 33-46
Jürgen Klonk: Comments on Optimality of B-Trees. SIGMOD Record 13(2): 35-38(1983)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]