File organization: implementation of a method guaranteeing retrieval in one access

ABSTRACT

A new file organization method that guarantees retrieval of any record in one access is tested on two existing files, producing empirical results that compare favorably with theoretical predictions. The description of the method includes the algorithms used for implementing the required hashing and signature functions.

REFERENCES

• 1: Gaston H. Gonnet , Per Åke Larson, External hasing with limited internal storage, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588153]
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: Larson, P.-A. Further analysis of external hashing with fixed-length separators. Rep. CS-83-18, Univ. of Waterloo, Waterloo, Ont., Canada, 1983. A continuation of {1}. An analysis of the insertion costs of the method studied in this paper.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
file organization, hashing, searching