Quelles sont les structures de données sous-jacentes utilisées pour Redis?

J'essaie de répondre à deux questions dans une liste définitive:

1. Quelles sont les structures de données sous-jacentes utilisées pour Redis?
2. Et quels sont les principaux avantages / inconvénients / cas d'utilisation pour chaque type?

J'ai donc lu que les listes Redis sont réellement implémentées avec des listes liées. Mais pour d'autres types, je ne suis pas en mesure de trouver des informations. De plus, si quelqu'un devait tomber sur cette question et ne pas avoir un résumé de haut niveau des avantages et des inconvénients de la modification ou de l'accès à différentes structures de données, il disposerait d'une liste complète des meilleurs moyens d'utiliser des types spécifiques pour y faire référence.

Plus précisément, je cherche à décrire tous les types: chaîne, liste, ensemble, zset et hachage.

Oh, j'ai regardé ces articles, entre autres, jusqu'à présent:

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

Je vais essayer de répondre à votre question, mais je vais commencer par quelque chose qui peut sembler étrange au premier abord: si vous n'êtes pas intéressé par les internes de Redis, vous ne devriez pas vous soucier de la façon dont les types de données sont implémentés en interne. C'est pour une raison simple: pour chaque opération Redis, vous trouverez la complexité temporelle dans la documentation et, si vous avez l'ensemble des opérations et la complexité temporelle, la seule autre chose dont vous avez besoin est un indice sur l'utilisation de la mémoire (et parce que nous faisons de nombreuses optimisations qui peuvent varier en fonction des données, la meilleure façon d'obtenir ces derniers chiffres est de faire quelques tests triviaux dans le monde réel).

Mais comme vous l'avez demandé, voici l'implémentation sous-jacente de chaque type de données Redis.

• Les chaînes sont implémentées à l'aide d'une bibliothèque de chaînes dynamiques C afin que nous ne payions pas (de manière asymptotique) les allocations dans les opérations d'ajout. De cette façon, nous avons O (N) ajoute, par exemple, au lieu d'avoir un comportement quadratique.
• Les listes sont implémentées avec des listes chaînées.
• Les ensembles et les hachages sont implémentés avec des tables de hachage.
• Les ensembles triés sont implémentés avec des listes de sauts (un type particulier d'arbres équilibrés).

Mais lorsque les listes, les ensembles et les ensembles triés sont petits en nombre d'éléments et en taille des plus grandes valeurs, un codage différent et beaucoup plus compact est utilisé. Cet encodage diffère pour différents types, mais présente la particularité d'être un blob compact de données qui force souvent un balayage O (N) pour chaque opération. Puisque nous utilisons ce format uniquement pour les petits objets, ce n'est pas un problème; l'analyse d'une petite goutte O (N) est inconsciente du cache, donc pratiquement parlant, elle est très rapide, et lorsqu'il y a trop d'éléments, l'encodage est automatiquement basculé sur l'encodage natif (liste chaînée, hachage, etc.).

Mais votre question ne concernait pas seulement les internes, votre point était quel type utiliser pour accomplir quoi? .

Cordes

Il s'agit du type de base de tous les types. C'est l'un des quatre types, mais c'est également le type de base des types complexes, car une liste est une liste de chaînes, un ensemble est un ensemble de chaînes, etc.

Une chaîne Redis est une bonne idée dans tous les scénarios évidents où vous souhaitez stocker une page HTML, mais aussi lorsque vous voulez éviter de convertir vos données déjà encodées. Ainsi, par exemple, si vous avez JSON ou MessagePack, vous pouvez simplement stocker des objets sous forme de chaînes. Dans Redis 2.6, vous pouvez même manipuler ce type de serveur d'objets à l'aide de scripts Lua.

Une autre utilisation intéressante des chaînes est les bitmaps, et en général les tableaux d'octets à accès aléatoire, car Redis exporte des commandes pour accéder à des plages aléatoires d'octets, voire à des bits uniques. Par exemple, consultez ce bon article de blog: les mesures en temps réel Fast Easy en utilisant Redis .

Listes

Les listes sont bonnes lorsque vous ne touchez que les extrêmes de la liste: près de la queue ou près de la tête. Les listes ne sont pas très bonnes pour paginer des trucs, car l'accès aléatoire est lent, O (N). Les bonnes listes de listes sont donc de simples files d'attente et piles, ou le traitement d'éléments en boucle à l'aide de RPOPLPUSH avec la même source et destination pour «faire tourner» un anneau d'éléments.

Les listes sont également utiles lorsque nous voulons simplement créer une collection plafonnée de N éléments où généralement nous accédons uniquement aux éléments supérieurs ou inférieurs, ou lorsque N est petit.

Ensembles

Les ensembles sont une collecte de données non ordonnée, ils sont donc bons à chaque fois que vous avez une collection d'articles et il est très important de vérifier l'existence ou la taille de la collection d'une manière très rapide. Une autre chose intéressante à propos des ensembles est la prise en charge de la lecture ou de l'éclatement d'éléments aléatoires (commandes SRANDMEMBER et SPOP).

Les ensembles sont également bons pour représenter les relations, par exemple, "Quels sont les amis de l'utilisateur X?" et ainsi de suite. Mais d'autres bonnes structures de données pour ce genre de choses sont des ensembles triés comme nous le verrons.

Les ensembles prennent en charge des opérations complexes telles que les intersections, les unions, etc.

Les petits ensembles sont encodés de manière très efficace.

Hashs

Les hachages sont la structure de données parfaite pour représenter des objets, composée de champs et de valeurs. Les champs de hachage peuvent également être incrémentés atomiquement à l'aide de HINCRBY. Lorsque vous avez des objets tels que des utilisateurs, des articles de blog ou tout autre type d' élément , les hachages sont probablement la voie à suivre si vous ne souhaitez pas utiliser votre propre encodage comme JSON ou similaire.

Cependant, gardez à l'esprit que les petits hachages sont encodés très efficacement par Redis, et vous pouvez demander à Redis d'obtenir GET, SET ou d'incrémenter des champs individuels de manière très rapide.

Les hachages peuvent également être utilisés pour représenter des structures de données liées, à l'aide de références. Par exemple, vérifiez la mise en œuvre de lamernews.com des commentaires.

Ensembles triés

Les ensembles triés sont les seules autres structures de données, outre les listes, à conserver les éléments ordonnés . Vous pouvez faire un certain nombre de trucs sympas avec des ensembles triés. Par exemple, vous pouvez avoir toutes sortes de listes Top Something dans votre application Web. Les meilleurs utilisateurs par score, les meilleurs messages par pages vues, le top quoi que ce soit, mais une seule instance Redis prendra en charge des tonnes d'opérations d'insertion et d'obtention des éléments par seconde.

Les ensembles triés, comme les ensembles réguliers, peuvent être utilisés pour décrire les relations, mais ils vous permettent également de paginer la liste des éléments et de mémoriser l'ordre. Par exemple, si je me souviens d'amis de l'utilisateur X avec un ensemble trié, je peux facilement me souvenir d'eux par ordre d'amitié acceptée.

Les ensembles triés conviennent aux files d'attente prioritaires.

Les ensembles triés sont comme des listes plus puissantes où l'insertion, la suppression ou l'obtention de plages à partir du milieu de la liste est toujours rapide. Mais ils utilisent plus de mémoire et sont des structures de données O (log (N)).

Conclusion

J'espère avoir fourni quelques informations dans cet article, mais il est préférable de télécharger le code source de lamernews sur http://github.com/antirez/lamernews et de comprendre comment cela fonctionne. De nombreuses structures de données de Redis sont utilisées dans Lamer News, et il existe de nombreux indices sur ce qu'il faut utiliser pour résoudre une tâche donnée.

Désolé pour les fautes de grammaire, il est minuit ici et trop fatigué pour revoir le post;)

La plupart du temps, vous n'avez pas besoin de comprendre les structures de données sous-jacentes utilisées par Redis. Mais un peu de connaissances vous aide à faire des compromis CPU v / s Memory. Il vous aide également à modéliser vos données de manière efficace.

En interne, Redis utilise les structures de données suivantes:

1. Chaîne
2. dictionnaire
3. Liste doublement liée
4. Ignorer la liste
5. Liste Zip
6. Ensembles Int
7. Zip Maps (obsolète en faveur de la liste des zip depuis Redis 2.6)

Pour trouver l'encodage utilisé par une clé particulière, utilisez la commande object encoding <key>.

1. Cordes

Dans Redis, les chaînes sont appelées chaînes dynamiques simples ou SDS . C'est un petit wrapper sur un char *qui vous permet de stocker la longueur de la chaîne et le nombre d'octets libres en tant que préfixe.

Étant donné que la longueur de la chaîne est stockée, strlen est une opération O (1). De plus, comme la longueur est connue, les chaînes Redis sont binaires. Il est parfaitement légal qu'une chaîne contienne le caractère nul .

Les chaînes sont la structure de données la plus polyvalente disponible dans Redis. Une chaîne est l' ensemble des éléments suivants:

1. Une chaîne de caractères pouvant stocker du texte. Voir les commandes SET et GET .
2. Un tableau d'octets qui peut stocker des données binaires.
3. Un longqui peut stocker des numéros. Voir les commandes INCR , DECR , INCRBY et DECRBY .
4. Un tableau (de chars, ints, longsou tout autre type de données) qui peuvent permettre un accès aléatoire efficace. Voir les commandes SETRANGE et GETRANGE .
5. Un tableau de bits qui vous permet de définir ou d'obtenir des bits individuels. Voir les commandes SETBIT et GETBIT .
6. Un bloc de mémoire que vous pouvez utiliser pour créer d'autres structures de données. Il est utilisé en interne pour créer des ziplists et des inetsets, qui sont des structures de données compactes et économes en mémoire pour un petit nombre d'éléments. Plus d'informations ci-dessous.

2. Dictionnaire

Redis utilise un dictionnaire pour les éléments suivants:

1. Pour mapper une clé à sa valeur associée, où la valeur peut être une chaîne, un hachage, un ensemble, un ensemble trié ou une liste.
2. Pour mapper une clé à son horodatage d'expiration.
3. Pour implémenter les types de données Hash, Set et Sorted Set.
4. Pour mapper les commandes Redis aux fonctions qui gèrent ces commandes.
5. Pour mapper une clé Redis à une liste de clients bloqués sur cette clé. Voir BLPOP .

Les dictionnaires Redis sont implémentés à l'aide de tables de hachage . Au lieu d'expliquer la mise en œuvre, je vais simplement expliquer les choses spécifiques à Redis:

1. Les dictionnaires utilisent une structure appelée dictTypepour étendre le comportement d'une table de hachage. Cette structure a des pointeurs de fonction et les opérations suivantes sont donc extensibles: a) fonction de hachage, b) comparaison de clés, c) destructeur de clés et d) destructeur de valeurs.
2. Les dictionnaires utilisent le murmurhash2 . (Auparavant, ils utilisaient la fonction de hachage djb2 , avec seed = 5381, mais ensuite la fonction de hachage a été commutée sur murmur2 . Voir cette question pour une explication de l'algorithme de hachage djb2 .)
3. Redis utilise le hachage incrémentiel, également connu sous le nom de redimensionnement incrémentiel . Le dictionnaire a deux tables de hachage. Chaque fois que le dictionnaire est touché , un compartiment est migré de la première (plus petite) table de hachage vers la seconde. De cette façon, Redis empêche une opération de redimensionnement coûteuse.

La Setstructure de données utilise un dictionnaire pour garantir qu'il n'y a pas de doublons. Le Sorted Setutilise un dictionnaire pour mapper un élément à sa partition, c'est pourquoi ZSCORE est une opération O (1).

3. Listes doublement liées

Le listtype de données est implémenté à l'aide de listes doublement liées . L'implémentation de Redis est directement issue du manuel de l'algorithme. Le seul changement est que Redis stocke la longueur dans la structure de données de la liste. Cela garantit que LLEN a une complexité O (1).

4. Ignorer les listes

Redis utilise Skip Lists comme structure de données sous-jacente pour les ensembles triés. Wikipedia a une bonne introduction. L'article de William Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees a plus de détails.

Les ensembles triés utilisent à la fois une liste de saut et un dictionnaire. Le dictionnaire stocke le score de chaque élément.

L'implémentation de Skip List de Redis est différente de l'implémentation standard des manières suivantes:

1. Redis autorise les scores en double. Si deux nœuds ont le même score, ils sont triés par ordre lexicographique .
2. Chaque nœud a un pointeur arrière au niveau 0. Cela vous permet de parcourir les éléments dans l'ordre inverse de la partition.

5. Liste Zip

Une liste Zip est comme une liste doublement liée, sauf qu'elle n'utilise pas de pointeurs et stocke les données en ligne.

Chaque nœud dans une liste doublement liée a au moins 3 pointeurs - un pointeur avant, un pointeur arrière et un pointeur pour référencer les données stockées sur ce nœud. Les pointeurs nécessitent de la mémoire (8 octets sur un système 64 bits), et donc pour les petites listes, une liste doublement liée est très inefficace.

Une liste Zip stocke les éléments de manière séquentielle dans une chaîne Redis. Chaque élément a un petit en-tête qui stocke la longueur et le type de données de l'élément, le décalage vers l'élément suivant et le décalage vers l'élément précédent. Ces décalages remplacent les pointeurs avant et arrière. Étant donné que les données sont stockées en ligne, nous n'avons pas besoin d'un pointeur de données.

La liste Zip est utilisée pour stocker de petites listes, des ensembles triés et des hachages. Les ensembles triés sont aplatis dans une liste similaire [element1, score1, element2, score2, element3, score3]et stockés dans la liste Zip. Les hachages sont aplatis dans une liste comme [key1, value1, key2, value2]etc.

Avec Zip Lists, vous avez le pouvoir de faire un compromis entre CPU et mémoire. Les listes Zip sont économes en mémoire, mais elles utilisent plus de CPU qu'une liste liée (ou table de hachage / Skip List). Trouver un élément dans la liste zip est O (n). L'insertion d'un nouvel élément nécessite une réallocation de mémoire. Pour cette raison, Redis utilise cet encodage uniquement pour les petites listes, les hachages et les ensembles triés. Vous pouvez modifier ce comportement en modifiant les valeurs de <datatype>-max-ziplist-entrieset <datatype>-max-ziplist-value>dans redis.conf. Voir Redis Memory Optimization, section "Encodage spécial des petits types de données agrégées" pour plus d'informations.

Les commentaires sur ziplist.c sont excellents, et vous pouvez comprendre complètement cette structure de données sans avoir à lire le code.

6. Int Sets

Les ensembles Int sont un nom de fantaisie pour «tableaux entiers triés».

Dans Redis, les ensembles sont généralement implémentés à l'aide de tables de hachage. Pour les petits ensembles, une table de hachage est inefficace en termes de mémoire. Lorsque l'ensemble est composé uniquement d'entiers, un tableau est souvent plus efficace.

Un ensemble Int est un tableau trié d'entiers. Pour trouver un élément, un algorithme de recherche binaire est utilisé. Cela a une complexité de O (log N). L'ajout de nouveaux entiers à ce tableau peut nécessiter une réallocation de mémoire, ce qui peut devenir coûteux pour les grands tableaux entiers.

Pour une optimisation supplémentaire de la mémoire, les Int Sets sont disponibles en 3 variantes avec différentes tailles entières: 16 bits, 32 bits et 64 bits. Redis est suffisamment intelligent pour utiliser la bonne variante en fonction de la taille des éléments. Lorsqu'un nouvel élément est ajouté et dépasse la taille actuelle, Redis le migre automatiquement vers la taille suivante. Si une chaîne est ajoutée, Redis convertit automatiquement l'ensemble Int en un ensemble basé sur une table de hachage standard.

Les ensembles Int sont un compromis entre le processeur et la mémoire. Les ensembles Int sont extrêmement efficaces en mémoire et, pour les petits ensembles, ils sont plus rapides qu'une table de hachage. Mais après un certain nombre d'éléments, le temps de récupération O (log N) et le coût de réallocation de mémoire deviennent trop importants. Sur la base d'expériences, le seuil optimal pour basculer vers une table de hachage standard s'est avéré être 512. Cependant, vous pouvez augmenter ce seuil (le diminuer n'a pas de sens) en fonction des besoins de votre application. Voir set-max-intset-entriesdans redis.conf.

7. Cartes Zip

Les Zip Maps sont des dictionnaires aplatis et stockés dans une liste. Ils sont très similaires aux listes Zip.

Les cartes Zip sont obsolètes depuis Redis 2.6 et les petits hachages sont stockés dans les listes Zip. Pour en savoir plus sur cet encodage, reportez-vous aux commentaires dans zipmap.c .

Redis stocke les clés pointant vers des valeurs. Les clés peuvent avoir n'importe quelle valeur binaire jusqu'à une taille raisonnable (l'utilisation de courtes chaînes ASCII est recommandée à des fins de lisibilité et de débogage). Les valeurs sont l'un des cinq types de données Redis natifs.

1. chaînes - une séquence d'octets sécurisés binaires jusqu'à 512 Mo

2. hashes - une collection de paires de valeurs clés

3. listes - une collection de chaînes dans l'ordre d'insertion

4. ensembles - une collection de chaînes uniques sans commande

5. ensembles triés - une collection de chaînes uniques triées par score défini par l'utilisateur

Cordes

Une chaîne Redis est une séquence d'octets.

Les chaînes de Redis sont binaires (ce qui signifie qu'elles ont une longueur connue non déterminée par des caractères de terminaison spéciaux), vous pouvez donc stocker n'importe quoi jusqu'à 512 mégaoctets dans une chaîne.

Les cordes sont le concept canonique de «magasin de valeur clé». Vous avez une clé pointant vers une valeur, où clé et valeur sont du texte ou des chaînes binaires.

Pour toutes les opérations possibles sur les chaînes, consultez le http://redis.io/commands/#string

Hashs

Un hachage Redis est une collection de paires de valeurs clés.

Un hachage Redis contient de nombreuses paires de valeurs clés, où chaque clé et valeur est une chaîne. Les hachages Redis ne prennent pas directement en charge les valeurs complexes (ce qui signifie que vous ne pouvez pas avoir un champ de hachage avoir une valeur d'une liste ou d'un ensemble ou un autre hachage), mais vous pouvez utiliser des champs de hachage pour pointer vers d'autres valeurs complexes de niveau supérieur. La seule opération spéciale que vous pouvez effectuer sur les valeurs de champ de hachage est l'incrémentation / décrémentation atomique du contenu numérique.

Vous pouvez penser à un hachage Redis de deux manières: comme une représentation d'objet directe et comme un moyen de stocker de nombreuses petites valeurs de manière compacte.

Les représentations d'objets directs sont simples à comprendre. Les objets ont un nom (la clé du hachage) et une collection de clés internes avec des valeurs. Voir l'exemple ci-dessous pour, bien, un exemple.

Le stockage de nombreuses petites valeurs à l'aide d'un hachage est une technique intelligente de stockage de données massives de Redis. Lorsqu'un hachage a un petit nombre de champs (~ 100), Redis optimise le stockage et l'efficacité d'accès de tout le hachage. L'optimisation du stockage de petit hachage de Redis soulève un comportement intéressant: il est plus efficace d'avoir 100 hachages chacun avec 100 clés et valeurs internes plutôt que d'avoir 10 000 clés de niveau supérieur pointant vers des valeurs de chaîne. L'utilisation de hachages Redis pour optimiser votre stockage de données de cette façon nécessite une surcharge de programmation supplémentaire pour suivre où les données finissent, mais si votre stockage de données est principalement basé sur des chaînes, vous pouvez économiser beaucoup de mémoire en utilisant cette astuce étrange.

Pour toutes les opérations possibles sur les hachages, voir les documents de hachage

Listes

Les listes Redis agissent comme des listes liées.

Vous pouvez insérer, supprimer et parcourir des listes à partir de la tête ou de la fin d'une liste.

Utilisez des listes lorsque vous devez conserver les valeurs dans l'ordre où elles ont été insérées. (Redis vous donne la possibilité d'insérer dans n'importe quelle position de liste arbitraire si vous en avez besoin, mais vos performances d'insertion se dégraderont si vous insérez loin de votre position de départ.)

Les listes Redis sont souvent utilisées comme files d'attente des producteurs / consommateurs. Insérez des éléments dans une liste, puis faites apparaître des éléments de la liste. Que se passe-t-il si vos consommateurs essaient de sortir d'une liste sans éléments? Vous pouvez demander à Redis d'attendre qu'un élément apparaisse et de vous le renvoyer immédiatement lorsqu'il est ajouté. Cela transforme Redis en un système de file d'attente de messages / événements / tâches / tâches / notifications en temps réel.

Vous pouvez supprimer de manière atomique des éléments à l'une ou l'autre des extrémités d'une liste, permettant à toute liste d'être traitée comme une pile ou une file d'attente.

Vous pouvez également gérer des listes de longueur fixe (collections plafonnées) en réduisant votre liste à une taille spécifique après chaque insertion.

Pour toutes les opérations possibles sur les listes, voir la documentation des listes

Ensembles

Les ensembles Redis sont, enfin, des ensembles.

Un ensemble Redis contient des chaînes Redis uniques non ordonnées où chaque chaîne n'existe qu'une fois par ensemble. Si vous ajoutez le même élément dix fois à un ensemble, il n'apparaîtra qu'une seule fois. Les ensembles sont parfaits pour s'assurer que quelque chose existe paresseusement au moins une fois sans se soucier des éléments en double accumulant et gaspillant de l'espace. Vous pouvez ajouter la même chaîne autant de fois que vous le souhaitez sans avoir besoin de vérifier si elle existe déjà.

Les ensembles sont rapides pour la vérification d'appartenance, l'insertion et la suppression de membres dans l'ensemble.

Les ensembles ont des opérations d'ensemble efficaces, comme vous vous en doutez. Vous pouvez prendre l'union, l'intersection et la différence de plusieurs ensembles à la fois. Les résultats peuvent être renvoyés à l'appelant ou les résultats peuvent être stockés dans un nouvel ensemble pour une utilisation ultérieure.

Les ensembles ont un accès à temps constant pour les vérifications d'appartenance (contrairement aux listes), et Redis a même la suppression et le retour des membres aléatoires ("pop un élément aléatoire de l'ensemble") ou les membres aléatoires retournant sans remplacement ("donnez-moi 30 utilisateurs uniques aléatoires) ") ou avec remplacement (" donnez-moi 7 cartes, mais après chaque sélection, remettez la carte afin qu'elle puisse éventuellement être échantillonnée à nouveau ").

Pour toutes les opérations possibles sur les ensembles, consultez la documentation des ensembles .

Ensembles triés

Les ensembles triés Redis sont des ensembles dont l'ordre est défini par l'utilisateur.

Pour simplifier, vous pouvez considérer un ensemble trié comme un arbre binaire avec des éléments uniques. (Les ensembles triés Redis sont en fait des listes à ignorer .) L'ordre de tri des éléments est défini par le score de chaque élément.

Les ensembles triés sont toujours des ensembles. Les éléments ne peuvent apparaître qu'une seule fois dans un ensemble. Un élément, à des fins d'unicité, est défini par son contenu de chaîne. L'insertion de l'élément "pomme" avec le score de tri 3, puis l'insertion de l'élément "pomme" avec le score de tri 500 entraîne un élément "pomme" avec le score de tri 500 dans votre ensemble trié. Les ensembles ne sont uniques qu'en fonction des données, et non en fonction des paires (score, données).

Assurez-vous que votre modèle de données repose sur le contenu de la chaîne et non sur le score de l'élément pour l'unicité. Les scores peuvent être répétés (ou même zéro), mais, une dernière fois, les éléments d'ensemble ne peuvent exister qu'une seule fois par ensemble trié. Par exemple, si vous essayez de stocker l'historique de chaque connexion utilisateur sous la forme d'un ensemble trié en faisant du score l'époque de la connexion et la valeur de l'ID utilisateur, vous finirez par stocker uniquement la dernière époque de connexion pour tous vos utilisateurs. Votre ensemble atteindrait la taille de votre base d'utilisateurs et non la taille souhaitée de vos connexions à la base d'utilisateurs *.

Des éléments sont ajoutés à votre ensemble avec des scores. Vous pouvez mettre à jour le score de n'importe quel élément à tout moment, il suffit d'ajouter à nouveau l'élément avec un nouveau score. Les scores sont représentés par des doubles à virgule flottante, vous pouvez donc spécifier la granularité des horodatages de haute précision si nécessaire. Plusieurs éléments peuvent avoir le même score.

Vous pouvez récupérer des éléments de différentes manières. Puisque tout est trié, vous pouvez demander des éléments commençant par les scores les plus bas. Vous pouvez demander des éléments en commençant par les scores les plus élevés ("à l'envers"). Vous pouvez demander des éléments par leur score de tri dans l'ordre naturel ou inverse.

Pour toutes les opérations possibles sur les ensembles triés, consultez la documentation des ensembles triés.