David M. Arnow
Abstract
It is well-known that the B-tree data structure yields excellent worst-case search costs and for that reason is widely employed in the organization of external files and in the implementation of data bases. In this paper, we examine general B-trees empirically and compare them with a less restrictive structure, the general multiway tree, and a more restrictive structure, the compact B-tree. We compare search costs, insertion costs, and space costs of these three structures for both small and large orders and indicate their relative utility for large and small data sets. Although there are cases when general multiway trees are more effective than B-trees, this is not the case for most practical situations. Compact B-trees are also shown to degrade rapidly in the presence of insertions and are therefore only useful for static data sets.
- Adelson-Velskii, G. M., Landis, E. M.: An information organization algorithm. DANSSSR, 146, (1962) 263-266.Google Scholar
- Bayer, R. and McCreight, E. Organization and maintenance of large ordered indexes Acta Informatica 1,3 (1972), 173-189.Google ScholarDigital Library
- Comer. D. The ubiquitous B-tree Computing Surveys 11,2 (1978), 121-138 Google ScholarDigital Library
- Foster, C. C. Information storage and retrieval using AVL trees. Proc. ACM 20th National Conf. (1965) 192-205. Google ScholarDigital Library
- Knuth, D. E. The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, Mass. (1973) Google ScholarDigital Library
- Rosenberg, A. L. and Snyder, L. Minimal comparison 2,3 trees. SIAM J. Computing 7,4 (1978). 465-480Google ScholarCross Ref
- Rosenberg, A. L. and Snyder, L. Time- and space-optimality in B-trees. ACM Transactions on Database Systems 6,1 (1981), 174-193. Google ScholarDigital Library
- Sussenguth, E. H., Jr.: The use of tree structures for processing files. Comm. ACM 6,5 (1963) Google ScholarDigital Library
- Wirth, N. Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, N.J. (1976) Google ScholarDigital Library
- Yao, A. C. On random 2,3 trees. Acta Informatica 9,3 (1978), 159-170.Google ScholarDigital Library
Index Terms
- An empirical comparison of B-trees, compact B-trees and multiway trees
Recommendations
An empirical comparison of B-trees, compact B-trees and multiway trees
SIGMOD '84: Proceedings of the 1984 ACM SIGMOD international conference on Management of dataIt is well-known that the B-tree data structure yields excellent worst-case search costs and for that reason is widely employed in the organization of external files and in the implementation of data bases. In this paper, we examine general B-trees ...
Compressed B+-trees
The B+-tree and its variants have been reported as the good index structures for retrieving data. Database systems frequently establish the B+-tree style indices for fast access to data records. However, traditional B+-tree index could be a performance ...
Dense multiway trees
B-trees of order m are a “balanced” class of m-ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion ...
Comments