Abstract:
|
We present a new type of search trees isomorphic to Skip-lists, i.e.,
there is a one-to-one mapping that commutes with the update
algorithms. Moreover, as Skip-trees inherit all the race properties
from Skip-lists, they can be selected as well as Skip-lists. We
design a concurrent algorithm on the fly approach to update
skip-trees. Among other advantages, this algorithm is more compressive
than the one designed by Pugh for Skip-lists. It is based on the
closest relationship between Skip-trees and the family of B-trees that
allows the translation of local rules between them. From a practical
point of view, although the Skip-list should be in main memory, the
Skip-trees can be registered into secondary external storage,
therefore it can be likely to analyse its ability to manage Databases. |