ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Digital B-Trees.

David B. Lomet: Digital B-Trees. VLDB 1981: 333-344
@inproceedings{DBLP:conf/vldb/Lomet81,
  author    = {David B. Lomet},
  title     = {Digital B-Trees},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {333-344},
  ee        = {db/conf/vldb/Lomet81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new tree index organization for files, capable of efficiently supporting both random and sequential access, is introduced. The organization, called digital B-tree (DB-tree), is similar in many aspects to B-trees. Its advantage is that it permits much larger fanout per node, thus reducing the height of the tree for a given file size. The effect of this is to reduce the cost of a random access to the file. The fanout of DB-tree nodes is increased substantially by permitting multiple page nodes. The unique advantage of DB-trees is that only one page of the node need ever be examined for each data access. This is accomplished by using the bits of the key to compute which page of the node is desired, in a way similar to the technique used in extendible hashing, but without performing a hashing operation. The DB-tree organization is described and analyzed. Particular algorithms are suggested for searching, building, and maintaining DB-trees.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David B. Lomet: Multi-Table Search for B-Tree Files. SIGMOD Conference 1979: 35-42 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:56 2010 by Michael Ley (ley@uni-trier.de)