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

The paper studies balanced trees with variable length records. It genealizes the concept of B-tree with unfixed key length. 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.