An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees.

David M. Arnow, Aaron M. Tenenbaum: An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees. SIGMOD Conference 1984: 33-46

@inproceedings{DBLP:conf/sigmod/ArnowT84,
  author    = {David M. Arnow and
               Aaron M. Tenenbaum},
  editor    = {Beatrice Yormark},
  title     = {An Empirical Comparison of B-Trees, Compact B-Trees and Multiway
               Trees},
  booktitle = {SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts,
               June 18-21, 1984},
  publisher = {ACM Press},
  year      = {1984},
  pages     = {33-46},
  ee        = {http://doi.acm.org/10.1145/602259.602265, db/conf/sigmod/ArnowT84.html},
  crossref  = {DBLP:conf/sigmod/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

It is well-known that the B-tree data structure yields excellent worst-case search costs and for that reason is widely employed in the organization of external files and in the implementation of data bases. In this paper, we examine general B-trees empirically and compare them with a less restrictive structure, the general multiway tree, and a more restrictive structure, the compact B-tree. We compare search costs, insertion costs, and space costs of these three structures for both small and large orders and indicate their relative utility for large and small data sets. Although there are cases when general multiway trees are more effective than B-trees, this is not the case for most practical situations. Compact B-trees are also shown to degrade rapidly in the presence of insertions and are therefore only useful for static data sets.

Copyright © 1984 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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/aDVD1 or /dvd

BibTeX

Printed Edition

Beatrice Yormark (Ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press 1984 BibTeX , SIGMOD Record 14(2)
Contents

Online Edition: ACM Digital Library

References

[1]: ...
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[4]: ...
[5]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[6]: Arnold L. Rosenberg, Lawrence Snyder: Minimal-Comparison 2, 3-Trees. SIAM J. Comput. 7(4): 465-480(1978) BibTeX
[7]: Arnold L. Rosenberg, Lawrence Snyder: Time- and Space-Optimality in B-Trees. ACM Trans. Database Syst. 6(1): 174-193(1981) BibTeX
[8]: Edward H. Sussenguth Jr.: Use of Tree Structures for Processing Files. Commun. ACM 6(5): 272-279(1963) BibTeX
[9]: ...
[10]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

BibTeX

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