No CrossRef data available.
Article contents
Toward a Formal Derivation of the Expected Behavior of Prefix B-Trees
Published online by Cambridge University Press: 27 July 2009
Abstract
Via order statistics we analyze the average length of all separators in random Prefix B-trees. From this result we draw some conclusions and conjectures concerning the average overall storage of random Prefix B-trees.
- Type
- Research Article
- Information
- Probability in the Engineering and Informational Sciences , Volume 9 , Issue 2 , April 1995 , pp. 183 - 192
- Copyright
- Copyright © Cambridge University Press 1995
References
1.Baeza-Yates, R.A. (1989). Expected behavior of B+-trees under random insertions. Acta Informatica 26: 439–471.Google Scholar
2.Bayer, R. & McCreight, E. (1972). Organization and maintenance of large ordered indexes. Acta Informatica 1: 173–189.Google Scholar
3.Bayer, R. & Unterauer, K. (1977). Prefix B-trees. ACM Transactions on Database Systems 2: 11–26.Google Scholar
5.Fagin, R., Nievergelt, J., Pippenger, N., & Strong, H.R. (1979). Extendible hashing: A fast access method for dynamic files. ACM Transactions on Database Systems 4: 315–344.Google Scholar
6.Ferguson, D.E. (1992). A data structure for fast file processing. Communications of the ACM 35: 114–120.CrossRefGoogle Scholar
7.Flajolet, P. & Richmond, B. (1992). Generalized digital trees and their difference-differential equations. Random Structures and Algorithms 3: 305–320.Google Scholar
8.Hoshi, M. & Flajolet, P. (1992). Page usage in quadtree indexes. BIT 32: 384–402.CrossRefGoogle Scholar
9.Knuth, D.E. (1973). The art of computer programming: Sorting and searching. Vol. 3. Reading, MA: Addison-Wesley.Google Scholar
10.Lew, W. & Mahmoud, H.M. (1994). The jointd distribution of elastic buckets in multiway search trees. SIAM Journal on Computing 23: 1050–1074.CrossRefGoogle Scholar
11.Litwin, W. (1980). Linear virtual hashing: A new tool for files and tables implementation. Proceedings of the 6th International Conference on Very Large Data Bases. Montreal, Que.: VLDB Endowment, pp. 212–223.Google Scholar
13.Mahmoud, H.M. & Papadakis, T. (1992). A probabilistic analysis of fixed and elastic buckets in tries and PATRICIA trees. Proceedings of the 30th Annual Allerton Conference on Communication, Control, and Computing. Monticello, IL: University of Illinois at Urbana-Champaign, pp. 874–883.Google Scholar
14.Orlandić, R. & Pfaltz, J.L. (1988). Compact O-complete trees. Proceedings of the 14th International Conference on Very Large Data Bases. Long Beach, CA: VLDB Endowment, pp. 372–381.Google Scholar
15.Orlandić, R. & Pfaltz, J.L. (1989). Analysis of compact O-complete trees: A new access method to large databases. Proceedings of the 7th FCT Conference, Szeged, Hungary. Published in Lecture Notes in Computer Science 380: 362–371.Google Scholar