Compact 0-Complete Trees.

@inproceedings{DBLP:conf/vldb/OrlandicP88,
  author    = {Ratko Orlandic and
               John L. Pfaltz},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Compact 0-Complete Trees},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {372-381},
  ee        = {db/conf/vldb/OrlandicP88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, a novel approach to ordered retrieval in very large files is developed. The method employs a B-tree like search algorithm that is independent of key type or key length because all keys in index blocks are encoded by a log₂M bit surrogate, where M is the maximal key length. For example, keys of length less than 32 bytes can be represented by a single byte in the index. This ensures a maximal possible fan out and greatly reduces the storage overhead of maintaining access indices.

Initially, retrieval in a binary trie structure is developed. With the aid of a fairly complex recurrence relation, the rather scraggly binary trie is transformed into a compact multi-way search tree. Then the recurrence relation itself is replaced by an unusually simple search algorithm. Finally, a specific access scheme, appropriate for secondary indexing, is presented.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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

• 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

References

[BaM72]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[BaU77]

Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX

[Com79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[dTv87]

Wiebren de Jonge, Andrew S. Tanenbaum, Reind P. van de Riet: Two Access Methods Using Compact Binary Trees. IEEE Trans. Software Eng. 13(7): 799-810(1987) BibTeX

[Fae79]

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

[Fre60]

...

[Lar80]

Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX

[Lit80]

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX

[Lit81]

Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX

[LiL87]

Witold Litwin, David B. Lomet: A New Method for Fast Data Searches with Keys. IEEE Software 4(2): 16-24(1987) BibTeX

[Lom81]

David B. Lomet: Digital B-Trees. VLDB 1981: 333-344 BibTeX

[OrP88]

...

[Yao78]

Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

1. John L. Pfaltz, James C. French: Scientific Database Management with ADAMS. IEEE Data Eng. Bull. 16(1): 14-18(1993)
2. Chris Clifton, Hector Garcia-Molina: Indexing in a Hypertext Database. VLDB 1990: 36-49
3. John L. Pfaltz, James C. French: Implementing Subscripted Identifiers in Scientific Databases. SSDBM 1990: 80-91