Performance analysis of file organizations that use multibucket data leaves with partial expansions

ABSTRACT

We present an exact performance analysis, under random insertions, of file organizations that use multibucket data leaves and perform partial expansions before splitting. We evaluate the expected disk space utilization of the file and show how the expected search and insert costs can be estimated. The analytical results are confirmed by simulations. The analysis can be used to investigate both the dynamic and the asymptotic behaviors.

REFERENCES

• 1: R. A. Baeza-Yates , P. -A. Larson, Performance of B±Trees with Partial Expansions, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.248-257, June 1989 [doi>10.1109/69.87964]
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: CLAUSING A. Kantorovich-type inequahties. Amer. Math. Monthly 89 (1982), 314 330
• 4: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 5: EISENBARTH, t3., ZIVIANI, N., GONNET, G. H., MEHLHORN, K., ,m\'D WOOD, D. The theory of fringe analysis and its application to 2-3 trees and 13-trees Inf. Control .55 (1982), 125-174.
• 6: 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]
• 7: David B. Lomet, Partial expansions for file organizations with an index, ACM Transactions on Database Systems (TODS), v.12 n.1, p.65-84, March 1987 [doi>10.1145/12047.12049]
• 8: David B. Lomet, A simple bounded disorder file organization with good performance, ACM Transactions on Database Systems (TODS), v.13 n.4, p.525-551, Dec. 1988 [doi>10.1145/49346.50067]
• 9: David B. Lomet , Betty Salzberg, A Robust Multi-Attribute Search Structure, Proceedings of the Fifth International Conference on Data Engineering, p.296-304, February 06-10, 1989
• 10: Gabriel Matsliach, Performance analysis of file organizations that use multi-bucket data leaves, Information Processing Letters, v.36 n.6, p.301-310, Dec. 15, 1990 [doi>10.1016/0020-0190(90)90043-W]
• 11: MATSLIACH, G. Using multi-bucket data leaves with overflow chains performance analysis. Inf. Syst. 16, 5 (1991), 497 508.
• 12: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 13: RAMAKaISHNA, M V. Computing the probability of hash table/urn overflow. Commun Stat Theor. Meth. 16, 11 (1987), 3343-3353.
• 14: M. V. Ramakrishna , P. Mukhopadhyay, Analysis of bounded disorder file organization, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-125, March 1988, Austin, Texas, United States [doi>10.1145/308386.308424]
• 15: YAO, A. A.C. On random 2-3 trees Acta Inf 9, 2 (1978), 159-170.

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

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:
Performance, Theory, Verification

Keywords:
bounded disorder files, multibucket data leaves, partial expansion, performance analysis, search structures