Analysis of Index-Sequential Files with Overflow Chaining.

Per-Åke Larson: Analysis of Index-Sequential Files with Overflow Chaining. ACM Trans. Database Syst. 6(4): 671-680(1981)

@article{DBLP:journals/tods/Larson81,
  author    = {Per-{\AA}ke Larson},
  title     = {Analysis of Index-Sequential Files with Overflow Chaining},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {4},
  year      = {1981},
  pages     = {671-680},
  ee        = {http://doi.acm.org/10.1145/319628.319665, db/journals/tods/Larson81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The gradual performance deterioration caused by deletions from and insertions into an index-sequential file after loading is analyzed. The model developed assumes that overflow records are handled by chaining. Formulas for computing the expected number of overflow records and the expected number of additional accesses caused by the overflow records for both successful and unsuccessful searches are derived.

Copyright © 1981 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 ...

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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

BibTeX

References

[1]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[2]: James A. Behymer, Robert A. Ogilive, Alan G. Merten: Analysis of Indexed Sequential and Direct Access File Organizations. SIGMOD Workshop, Vol. 1 1974: 389-417 BibTeX
[3]: ...
[4]: ...
[5]: 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
[6]: Daniel G. Keehn, John O. Lacy: VSAM Data Set Design Parameters. IBM Systems Journal 13(3): 186-212(1974) BibTeX
[7]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[8]: James K. Mullin: An Improved Index Sequential Access Method Using Hashed Overflow. Commun. ACM 15(5): 301-307(1972) BibTeX
[9]: Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495 BibTeX
[10]: Konrad H. Quitzow, Manfred R. Klopprogge: Space utilization and access path length in B-trees. Inf. Syst. 5(1): 7-16(1980) BibTeX
[11]: ...
[12]: ...
[13]: ...
[14]: ...
[15]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
Stavros Christodoulakis, Daniel Alexander Ford: Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs. SIGMOD Conference 1989: 306-314
Robert B. Cooper, Martin K. Solomon: The Average Time Until Bucket Overflow. ACM Trans. Database Syst. 9(3): 392-408(1984)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]