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}
}
BibTeX

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 ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX

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) BibTeX
[2]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]
Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX
[4]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[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) BibTeX
[6]
...
[7]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[8]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[9]
David B. Lomet: Multi-Table Search for B-Tree Files. SIGMOD Conference 1979: 35-42 BibTeX
[10]
...
[11]
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]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Wed Aug 20 20:14:22 2008