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

摘要

Nous présentons un nouveau type d'arbres, que nous appelons Skip trees, lesquels sont une généralisation des Skip lists. Concrètement, il existe un isomorphe entre eux qui commute avec les algorithmes. Une Skip list est une structure de données ordonnées qui sert pour manager des bases de données. Une propriété intéressante est que la configuration des Skip lists ne résulte pas de l'ordre d'introduction des données parce qu'on utilise des techniques aléatoires. Des Skip trees héritent toutes les propriétés des Skip lists, surtout les bornes des algorithmes séquentiels. Mieux encore, l'utilisation des Skip trees nous permet de construire un algorithme concurrent on the fly. Cette solution offre de grands avantages : l'algorithme est plus compréhensible que celui construit par Pugh pour les Skip lists, et il accepte plus de concurrence parce que les transformations sont locales. D'un point de vue pratique, malgré que les Skip lists doivent être enregistrées en mémoire centrale, les Skip trees peuvent être stockés sur un support secondaire. En conséquence, nous étudions l'habilité des Skip trees pour indexer des bases de données en comparaison avec les B-trees.%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 mapping between the two data types which commutes with the sequential update algorithms. A Skip list is a data structure used to manage data bases which stores values in a sorted way and in which it is insured that the form of the Skip list is independent of the order of updates by using randomization techniques. Skip trees inherit all the proeprties of Skip lists, including the time bounds of sequential algorithms. The algorithmic improvement of the Skip tree type is that a concurrent algorithm 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 on 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 into a secondary or external storage. Therefore we analyse the ability of Skip trees to manage data bases in comparison with B-trees.