Distributing a search tree among a growing number of processors

ABSTRACT

Databases are growing steadily, and distributed computer systems are more and more easily available. This provides an opportunity to satisfy the increasingly tighter efficiency requirements by means of distributed data structures. The design and analysis of these structures under efficiency aspects, however, has not yet been studied sufficiently. To our knowledge, a single scalable, distributed data structure has been proposed so far. It is a distributed variant of linear hashing with uncontrolled splits, and, as a consequence, performs efficiently for data distributions that are close to uniform, but not necessarily for others. In addition, it does not support queries that refer to the linear order of keys, such as nearest neighbor or range queries. We propose a distributed search tree that avoids these problems, since it inherits desirable properties from non-distributed trees. Our experiments show that our structure does indeed combine a guarantee for good storage space utilization with high query efficiency. Nevertheless, we feel that further research in the area of scalable, distributed data structures is dearly needed; it should eventually lead to a body of knowledge that is comparable with the non-distributed, classical data structures field.

REFERENCES

• 1: F. B. Bastani , S. S. Iyengar , I-Ling Yen, Concurrent maintenance of data systems for telecommunications, The Computer Journal, v.31 n.2, p.165-174, April, 1988 [doi>10.1093/comjnl/31.2.165]
• 2: C.S. Ellis: Distributed data structures: A case study. IEEE Transactions on Computing, Vol. C-34, No. 12, 1985, 1178- 1185.
• 3: E. Gudes, E. Shapiro: A parallel B-tree process structure, The Weizmann Institute, Rehovot, Israel Technical Report CS 89-06, 1989.
• 4: M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.197-206, March 14-16, 1990, Seattle, Washington, United States
• 5: Theodore Johnson , Padmashree Krishna, Lazy updates for distributed search structure, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.337-346, May 25-28, 1993, Washington, D.C., United States
• 6: 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
• 7: Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.43-57, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93399]
• 8: Witold Litwin , Marie-Anne Neimat , Donovan A. Schneider, LH: Linear Hashing for distributed files, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.327-336, May 25-28, 1993, Washington, D.C., United States
• 9: Gabriel Matsliach , Oded Shmueli, Maintaining bounded disorder files in multiprocessor multi-disk environments, Proceedings of the third international conference on database theory on Database theory, p.109-125, November 1990, Paris, France
• 10: Gabriel Matsliach , Oded Shmueli, An efficient method for distributing search structures, Proceedings of the first international conference on Parallel and distributed information systems, p.159-167, December 1991, Miami, Florida, United States
• 11: Sakti Pramanik , Myoung Ho Kim, Parallel Processing of large node B-trees, IEEE Transactions on Computers, v.39 n.9, p.1208-1212, September 1990 [doi>10.1109/12.57061]
• 12: H. Sehwetman: CSIM Reference Manual, Revision 16, Technical Report, MCC, Austin, Texas, USA. 1992
• 13: W. E. Weihl, P. Wang: Multi-version memory: Software cache management for concurrent B-trees, Proc. 2nd IEE-# Symp. Parallel and Distributed Processing, 650

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Experimentation