File Organization: On the Selection of Random Access Index Points for Sequential Files

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

File Organization: On the Selection of Random Access Index Points for Sequential Files

Full text

Pdf (861 KB)

Source

Journal of the ACM (JACM) archive
Volume 16 , Issue 4 (October 1969) table of contents

Pages: 569 - 579

Year of Publication: 1969

ISSN:0004-5411

Authors

S. P. Ghosh	IBM Thomas J. Watson Research Center, Yorktown Heights, New York
M. E. Senko	IBM Thomas J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 33, Citation Count: 12

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321541.321546 What is a DOI?

ABSTRACT

The construction of a hierarchy of indexes (the indexed sequential access method) is one means of providing rapid random access to sequential files. An examination is made of the consequences of partially or completely replacing one or more index levels by linear interpolation procedures. For all possible configurations of the several types of key distributions investigated, linear interpolation on the average provides significant performance improvements. Typically, the two accesses required to obtain track index and data are reduced to 1.1 to 1.7 accesses per record. Extremely unusual key distribution will, however, raise the number of accesses required above 2.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

MOOD, A.M. Introduction to the Theory of Statistics. McGraw-Hill, New York, 1963.

CITED BY 12

	Yehoshua Perl , Alon Itai , Haim Avni, Interpolation search—a log logN search, Communications of the ACM, v.21 n.7, p.550-553, July 1978
	D. G. Severance , J. V. Carlis, A Practical Approach to Selecting Record Access Paths, ACM Computing Surveys (CSUR), v.9 n.4, p.259-272, Dec. 1977
	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
	Gary D. Knott, A balanced tree storage and retrieval algorithm, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland
	Per-Åke Larson, Analysis of index-sequential files with overflow chaining, ACM Transactions on Database Systems (TODS), v.6 n.4, p.671-680, Dec. 1981
	J. Gerry Purdy, A graduate course in database management, ACM SIGMOD Record, v.7 n.1, p.10-15, 1975
	Leslie L. Miller , Tyne Liang, The role of parellelism in file organization, Proceedings of the 1985 ACM thirteenth annual conference on Computer Science, p.381-388, March 1985, New Orleans, Louisiana, United States
	J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974
	Walter A. Burkhard, Interpolation-based index maintenance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	David B. Lomet, A simple bounded disorder file organization with good performance, ACM Transactions on Database Systems (TODS), v.13 n.4, p.525-551, Dec. 1988
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	C. P. Wang , V. Y. Lum, Quantitative evaluation of design tradeoffs in file systems, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland