Concurrency in linear hashing

ABSTRACT

Concurrent access to complex shared data structures, particularly structures useful as database indices, has long been of interest in the database community. In dynamic databases, tree structures such as B-trees have been used as indices because of their ability to handle growth; whereas hashing has been used for fast access in relatively static databases. Recently, a number of techniques for dynamic hashing have appeared. They address the major deficiency of traditional hashing when applied to databases that experience significant change in the amount of data being stored. This paper presents a solution that allows concurrency in one of these dynamic hashing data structures, namely linear hash files. The solution is based on locking protocols and minor modifications in the data structures.

REFERENCES

• 1: BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9 (1977), 1-21.
• 2: ELLIS, C. Concurrent search and insertion in 2-3 trees. Acta Inf. 14 (1980), 63-86.
• 3: ELLIS, C. Concurrent search and insertion in AVL trees. IEEE Trans. Comput. C-29, 9 (Sept. 1980), 811-817.
• 4: Carla Schlatter Ellis, Extendible hashing for concurrent operations and distributed data, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588072]
• 5: Carla Schlatter Ellis, Concurrency and linear hashing, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-7, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325406]
• 6: ELLIS, C. Distributed data structures: A case study. IEEE Trans. Comput. C-34, 12 (Dec. 1985), pp. 1178-1185.
• 7: 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]
• 8: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 9: KWONG, Y. S., AND WOOD, D. New method for concurrency in B-trees. IEEE Trans. Softw. Eng. SE-8, 3 (May 1982) 211-222.
• 10: LARSON, P. Dynamic hashing. BIT 17 (1978), 184-201.
• 11: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 12: LITWIN, W. Linear hashing: A new tool for file and table addressing. In Proceedings o~ the 6th Conference on Very Large Data Bases (Montreal, 1980), 212-223.
• 13: David B. Lomet, Bounded index exponential hashing, ACM Transactions on Database Systems (TODS), v.8 n.1, p.136-165, March 1983 [doi>10.1145/319830.319837]
• 14: Udi Manbar , Richard E. Ladner, Concurrency control in a dynamic search structure, ACM Transactions on Database Systems (TODS), v.9 n.3, p.439-455, Sept. 1984 [doi>10.1145/1270.318576]
• 15: MILLER, R., AND SNYDER, L. Multiple access to B-trees. In Proceedings o~ Con/erence on Information Sciences & Systems (Baltimore, Md., Mar. 1978), (preliminary report).
• 16: Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
• 17: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• 18: Wu, C. T., AND BURKHARD, W.A. Concurrency in linear and interpolation hashing. Unpublished manuscript. Northwestern University, Evanston, Ill., (1983).

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

  E. Data

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms