New file organization based on dynamic hashing

ABSTRACT

New file organizations based on hashing and suitable for data whose volume may vary rapidly recently appeared in the literature. In the three schemes which have been independently proposed, rehashing is avoided, storage space is dynamically adjusted to the number of records actually stored, and there are no overflow records. Two of these techniques employ an index to the data file. Retrieval is fast and storage utilization is low. In order to increase storage utilization, we introduce two schemes based on a similar idea and analyze the performance of the second scheme. Both techniques use an index of much smaller size. In both schemes, overflow records are accepted. The price which has to be paid for the improvement in storage utilization is a slight access cost degradation.

REFERENCES

• 1: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 2: KEEHN, D.G., AND LACY. J.O. VSAM data set design parameters. IBM Syst. J., 3 (1974), 186- 212.
• 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. Dynamic hashing. BIT 18 (1978), 184-201.
• 5: LITWIN, W. Virtual hashing: A dynamically changing hashing. Proc. 4th Conf. Very Large Data Bases, West Berlin, Sept. 1978, pp. 517-523.
• 6: LITWIN, W. Hachage virtuel: Une nouveUe technique d'adressage de m~moires. Th~se de Doctorat d'Etat ~s Sciences Math~matiques, Univ. Pierre et Marie Curie, Paris, France, March 1979.
• 7: NAKAMURA, T., AND MIZOGUCHI, T. An analysis of storage utilization factor in block split data structuring scheme. Proc. 4th Conf. Very Large Data Bases, West Berlin, Sept. 1978, pp. 489- 495.
• 8: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 9: VAN DER POOL, J.A. Optimum storage allocation for initial loading of a foe. IBM J. Res. Dev. (Nov. 1972), 579-586.
• 10: YAo, A.C. On random 2-3 trees. Acta Inf., 9 (1978), 159-170.

INDEX TERMS

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

General Terms:
Design

Keywords:
data structure, dynamic hashing, file organization, hashing, linear splitting