Performance of B/sup +/-trees with partial expansions
- 1 June 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 1 (2) , 248-257
- https://doi.org/10.1109/69.87964
Abstract
The authors mathematically analyze the behavior of B/sup +/-trees with partial expansions file structure under random insertions, focusing on the expected storage utilization and the expected cost of insertions. The model can be used for studying both the asymptotic and dynamic behavior. The accuracy of the model is confirmed by simulation. Disk space management is found to be more difficult than for standard B/sup +/-trees. Two simple space-management schemes specifically designed for handling buckets of two different sizes are investigated. It is found that an overall storage utilization of 81% can be achieved in practice.<>Keywords
This publication has 7 references indexed in Scilit:
- Expected behaviour of B+-trees under random insertionsActa Informatica, 1989
- Partial expansions for file organizations with an indexACM Transactions on Database Systems, 1987
- Performance analysis of linear hashing with partial expansionsACM Transactions on Database Systems, 1982
- The theory of fringe analysis and its application to 23 trees and b-treesInformation and Control, 1982
- Kantorovich-Type InequalitiesThe American Mathematical Monthly, 1982
- Ubiquitous B-TreeACM Computing Surveys, 1979
- On random 2?3 treesActa Informatica, 1978