Self-organizing scheme for file storage

ABSTRACT

The B-tree data structure of Bayer and McCreight is an effective method of organizing an external file when the operations of searching, insertion, and deletion must be supported since these operations on B-tree require at most logarithmic time of the file size. The performance of B-trees can be improved by reorganizing file storage, as the environment of a file changes. Three parameters are used, in order to reorganize file storage and adapt to the changing environment of a file. The space utilization of B-trees and the number of disk accesses are analyzed by dynamically adjusting three parameters. The simulation results are given which indicate that the performance of B-trees is significantly improved by increasing the space utilization to some degree, especially when the file is static. Also when a file is highly dynamic, the improvement in the performance of B-trees is discernible as two sensitivity factors are increased from 0 to the range of 0.05 - 0.1. A near optimal range for each parameter is proposed to maintain a high performance as the environment of a file changes.

REFERENCES

• Dat86: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Fag79: 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]
• Hor83: Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
• Knu73: 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
• Lit78: Litwin, W. Linear I-Ia. shing: A new tool for files and tables addressing. In Proc. 4th Conf. Very Large Data Base (Berlin, 1978), 517-523.
• Ore83: Jack A. Orenstein, A Dynamic Hash File for Random and Sequential Accessing, Proceedings of the 9th International Conference on Very Large Data Bases, p.132-141, October 31-November 02, 1983
• Ram84: K Ramamohanarao , R Sacks-Davis, Recursive linear hashing, ACM Transactions on Database Systems (TODS), v.9 n.3, p.369-391, Sept. 1984 [doi>10.1145/1270.1285]
• Ros81: Arnold L. Rosenberg , Lawrence Snyder, Time- and space-optimality in B-trees, ACM Transactions on Database Systems (TODS), v.6 n.1, p.174-193, March 1981 [doi>10.1145/319540.319565]
• Sch81: Michel Scholl, New file organization based on dynamic hashing, ACM Transactions on Database Systems (TODS), v.6 n.1, p.194-211, March 1981 [doi>10.1145/319540.319564]
• Sun87: Yuan Y. Sung, Sensitivity problem in dynamic file organization, Proceedings of the 15th annual conference on Computer Science, p.149-153, February 1987, St. Louis, Missouri, United States [doi>10.1145/322917.322941]
• Ull82: Ullman, J.D. Ihinciple Of Database Systems. 2rid Edition, Pitman, 1982.

INDEX TERMS

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

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

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

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory