Home | PSI RAS | RCIS | S-Tree Lib

A utilization D(T) for S(b)-trees is the ratio of the total weight of the tree M(T), that is the sum of weights of keys stored in the tree, to the maximal possible weight of an n-node S(b)-tree of rank p:

We prove that for any linearly ordered weighted finite key set K, and for any e > 0 the three parameters b, q, and p can be chosen in such a way that for any S(b)-tree of order q, and rank p containing keys from K the following bound for its utilization holds

 D(T) > 1 - e