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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" 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/vldb7588 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

Printed Edition

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

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)
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[3]: Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977)
[4]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[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)
[6]: ...
[7]: Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978)
[8]: Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523
[9]: David B. Lomet: Multi-Table Search for B-Tree Files. SIGMOD Conference 1979: 35-42
[10]: ...
[11]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978)