ACM SIGMOD Anthology TODS dblp.uni-trier.de

A Simple Bounded Disorder File Organization with Good Performance.

David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988)
@article{DBLP:journals/tods/Lomet88,
  author    = {David B. Lomet},
  title     = {A Simple Bounded Disorder File Organization with Good Performance},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {4},
  year      = {1988},
  pages     = {525-551},
  ee        = {http://doi.acm.org/10.1145/49346.50067, db/journals/tods/Lomet88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A bounded-disorder (BD) file is one in which data are organized into nodes that are indexed, e.g., by means of a B-tree. The data nodes are multibucket nodes that are accessed by hashing. In this paper we present two important improvements to the BD organization as originally described. First, records in a data node that overflow their designated primary bucket are stored in a single overflow bucket which is itself a bucket of the data node. Second, when file space needs to be increased, partial expansions are used that employ elastic buckets. Analysis and simulation results demonstrate that this variant of the BD organization has utilization, random access performance, and file growth performance that can be competitive with good extendible hashing methods, while supporting high-performance sequential access. The simplicity of the organization results in simple algorithms for realizing the organization.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

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: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179 BibTeX
[4]
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
[5]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[6]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[7]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[8]
Witold Litwin, David B. Lomet: A New Method for Fast Data Searches with Keys. IEEE Software 4(2): 16-24(1987) BibTeX
[9]
David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX
[10]
David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133 BibTeX
[11]
David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987) BibTeX
[12]
...

Referenced by

  1. June S. Park, V. Sridhar: Probabilistic Model and Optimal Reorganization of B+-Tree with Physical Clustering. IEEE Trans. Knowl. Data Eng. 9(5): 826-832(1997)
  2. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
  3. Gabriel Matsliach, Oded Shmueli: A Combined Method for Maintaining Large Indices in Multiprocessor Multidisk Environments. IEEE Trans. Knowl. Data Eng. 6(3): 479-496(1994)
  4. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
  5. Nabil I. Hachem, P. Bruce Berra: New Order Preserving Access Methods for Very Large Files Derived From Linear Hashing. IEEE Trans. Knowl. Data Eng. 4(1): 68-82(1992)
  6. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
  7. 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)
  8. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  9. M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989)
  10. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
  11. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
  12. M. V. Ramakrishna: An Exact Probability Model for Finite Hash Tables. ICDE 1988: 362-368
  13. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:05 2008