Space saving generalization of B-trees with 2/3 utilization

The paper studies balanced trees with variable length records. It generalizes the concept of B-tree with unfixed key length introduced in [1] and S(1)-tree of [2]. The main property of the new trees, called S(b)-trees, is their local incompressibility. That is, any sequence consisting of b + 1 neighboring nodes of the tree cannot be compressed into a b well formed node. The case of S(2)-trees is studied in detail. For these trees, 2/3 − utilization lower bound is proven, where is inversely proportional to the tree branching. Logarithmic running time algorithms for search, insertion, and deletion are presented.