STORAGE OVERHEAD OF O-TREES, B-TREES AND PREFIX B-TREES: A COMPARATIVE ANALYSIS
Ratko Orlandić, Hosam M. Mahmoud · International Journal of Foundations of Computer Science · 1996
The O-tree is an indexing mechanism closely related to B-trees and Prefix B-trees. In this paper we derive the expected storage overhead of O-Trees under the standard Bernoulli model of randomness, compare the results with the expected overhead of B-trees and Prefix B-trees under the same conditions, and assess the expected relative improvements.