The Bounded Disorder Access Method.

@inproceedings{DBLP:conf/icde/LitwinL86,
  author    = {Witold Litwin and
               David B. Lomet},
  title     = {The Bounded Disorder Access Method},
  booktitle = {Proceedings of the Second International Conference on Data Engineering,
               February 5-7, 1986, Los Angeles, California, USA},
  publisher = {IEEE Computer Society},
  year      = {1986},
  isbn      = {0-8186-0655-X},
  pages     = {38-48},
  ee        = {db/conf/icde/LitwinL86.html},
  crossref  = {DBLP:conf/icde/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

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/An2-6 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

[1]

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

[2]

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

[3]

Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX

[4]

Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX

[5]

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

[6]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX

[7]

Sakti P. Ghosh, Michael E. Senko: File Organization: On the Selection of Random Access Index Points for Sequential Files. J. ACM 16(1): 569-579(1969) BibTeX

[8]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[9]

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

[10]

Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX

[11]

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

[12]

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

[13]

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

[14]

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX

[15]

David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133 BibTeX

[16]

...

[17]

Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 BibTeX

[18]

Markku Tamminen: Order Preserving Extendible Hashing and Bucket Tries. BIT 21(4): 419-435(1981) BibTeX

Referenced by

1. David B. Lomet: B-tree Page Size When Caching is Considered. SIGMOD Record 27(3): 28-32(1998)
2. Bernhard Seeger, Per-Åke Larson: Multi-Disk B-trees. SIGMOD Conference 1991: 436-445
3. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
4. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
5. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
6. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
7. Dina Bitton, Maria Hanrahan, Carolyn Turbyfill: Performance of Complex Queries in Main Memory Database Systems. ICDE 1987: 72-81