ACM SIGMOD Anthology TODS dblp.uni-trier.de

Partial Expansions for File Organizations with an Index.

David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
@article{DBLP:journals/tods/Lomet87,
  author    = {David B. Lomet},
  title     = {Partial Expansions for File Organizations with an Index},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {1},
  year      = {1987},
  pages     = {65-84},
  ee        = {http://doi.acm.org/10.1145/12047.12049, db/journals/tods/Lomet87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A new way to increase file space in dynamically growing files is introduced in which substantial improvement in file utilization can be achieved. It makes use of partial expansions in which, instead of doubling the space associated with some part of the file, the space grows at a slower rate. Unlike previous versions of partial expansion in which the number of buckets involved in tile growth is increased by less than a factor of two, the new method expands file space by increasing bucket size via "elastic buckets." This permits partial expansions to be used with a wide range of indexed files, including B-trees. The results of using partial expansions are analyzed, and the analysis confirmed by a simulation study. The analysis and simulation demonstrate that the file utilization gains are substantial and that fears of excessive insertion cost resulting from more frequent file growth are unfounded.

Copyright © 1987 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]
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
[3]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[4]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[5]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[6]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[7]
Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48 BibTeX
[8]
David B. Lomet: Digital B-Trees. VLDB 1981: 333-344 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: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988) BibTeX
[12]
...
[13]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

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: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
  4. 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)
  5. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
  6. 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)
  7. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  8. Ricardo A. Baeza-Yates: An Adaptive Overflow Technique for B-trees. EDBT 1990: 16-28
  9. Ricardo A. Baeza-Yates, Per-Åke Larson: Performance of B+-Trees with Partial Expansions. IEEE Trans. Knowl. Data Eng. 1(2): 248-257(1989)
  10. David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324
  11. Stavros Christodoulakis, Daniel Alexander Ford: Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs. SIGMOD Conference 1989: 306-314
  12. David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304
  13. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
  14. David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988)
  15. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
  16. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
  17. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363
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:01 2008