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

Referenced by

  1. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
  2. David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)
  3. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
  4. Ratko Orlandic, John L. Pfaltz: Compact 0-Complete Trees. VLDB 1988: 372-381
  5. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
  6. Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588
  7. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  8. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363
  9. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
  10. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
  11. Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27
  12. T. V. Prabhakar, H. V. Sahasrabuddhe: Towards an Optimal Data-Structure: CB-trees. VLDB 1984: 235-244
  13. David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983)
  14. David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133
  15. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
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: Sat May 16 23:45:13 2009