SKIP TREES, AN ALTERNATIVE DATA STRUCTURE TO SKIP LISTS IN A CONCURRENT APPROACH

We present a new type of search trees, called Skip trees, which are a generalization of Skip lists. To be precise, there is a one-to-one map ping between the two data types which commutes with the sequential upd ate algorithms. A Skip list is a data structure used to manage data ba ses which stores values in a sorted way and in which it is insured tha t the form of the Skip list is independent of the order of updates by using randomization techniques Skip trees inherit all the proeprties o f Skip lists, including the time bounds of sequential algorithms. The algorithmic improvement of the Skip tree type is that a concurrent alg orithm on the fly approach can be designed Among other advantages this algorithm is more compressive than the one designed by Pugh for Skip lists and accepts a higher degree of concurrence because it is based o n a set of local updates. From a practical point of view, although the Skip list should be in the main memory Skip trees can be registered i nto a secondary or external storage. Therefore we analyse the ability of Skip trees to manage data bases in comparison with B-trees.