Home | PSI RAS | RCIS | S-Tree Lib

Indexing is a usual way of optimizing retrieval of information in a database, which allows proceeding from the exhaustive search in the database to an efficient search in a specified index by a key. Any database programming system provides means for creating, and maintaining indexes, and most implementations of indexes are based on balanced trees. This clarifies the importance of balanced trees in practice, and explains the interest of researchers in the problem.

A number of variants of balanced trees are known: AVL-trees, 2-3-trees, red-black-trees, etc. But from the practical view point B-trees, together with all its modifications, like B⁺-trees, B^*-trees, (a,b)-trees, are considered to be the most common data structure for representing indexes in external memory. Unfortunately, the B-trees have a serious disadvantage that restricts their implementation for storing variable length keys, since in the case B-trees can lead to an exhaustive waste of memory.

We introduce a new type of balanced trees, called S(B)-trees, which contrary to the B-trees provide optimal packing of keys of variable length, while the data access time remains the same as for B-trees.