B-tree plus rapide qu'AVL ou RedBlack-Tree ?[fermé]

https://stackoverflow.com/questions/647537

22-07-2019
|

Question

Je sais que les performances ne sont jamais en noir et blanc, souvent une implémentation est plus rapide dans le cas X et plus lente dans le cas Y, etc.mais en général, les B-trees sont-ils plus rapides que AVL ou RedBlack-Trees ?Ils sont considérablement plus complexes à mettre en œuvre que les arbres AVL (et peut-être même les arbres RedBlack ?), mais sont-ils plus rapide (leur complexité est-elle payante) ?

Modifier: Je voudrais également ajouter que s'ils sont plus rapides que l'arborescence AVL/RedBlack équivalente (en termes de nœuds/contenu) - pourquoi sont-ils plus rapides ?

La solution

Le message de Sean (celui actuellement accepté) contient plusieurs affirmations incorrectes.Désolé Sean, je ne veux pas être impoli ;J'espère pouvoir vous convaincre que ma déclaration est fondée sur des faits.

Leurs cas d'utilisation sont totalement différents, il n'est donc pas possible de faire une comparaison.

Ils sont tous deux utilisés pour conserver un ensemble d'éléments totalement ordonnés avec une recherche, une insertion et une suppression rapides.Ils ont la même interface et la même intention.

Les arbres RB sont généralement des structures en mémoire utilisées pour fournir un accès rapide (idéalement O(logN)) aux données.[...]

toujours O (log n)

Les arbres B sont généralement des structures basées sur disque et sont donc intrinsèquement plus lents que les données en mémoire.

Absurdité.Lorsque vous stockez des arbres de recherche sur disque, vous utilisez généralement des arbres B.C’est vrai.Lorsque vous stockez des données sur disque, leur accès est plus lent que celui des données en mémoire.Mais un arbre rouge-noir stocké sur disque est aussi plus lent qu’un arbre rouge-noir stocké en mémoire.

Vous comparez ici des pommes et des oranges.Ce qui est vraiment intéressant, c'est une comparaison des arbres B en mémoire et des arbres rouge-noir en mémoire.

[En aparté:Les arbres B, par opposition aux arbres rouge-noir, sont théoriquement efficaces dans le modèle E/S.J'ai testé expérimentalement (et validé) le modèle d'E/S pour le tri ;Je m'attendrais à ce que cela fonctionne également pour les arbres B.]

Les arbres B sont rarement des arbres binaires, le nombre d'enfants qu'un nœud peut avoir est généralement un grand nombre.

Pour être clair, la plage de tailles des nœuds B-tree est un paramètre de l'arbre (en C++, vous souhaiterez peut-être utiliser une valeur entière comme paramètre de modèle).

La gestion de la structure B-tree peut être assez compliquée lorsque les données changent.

Je me souviens qu'ils étaient beaucoup plus simples à comprendre (et à mettre en œuvre) que les arbres rouge-noir.

B-tree essaie de minimiser le nombre d'accès au disque afin que la récupération des données soit raisonnablement déterministe.

C’est vrai.

Il n'est pas rare de voir quelque chose comme un accès à 4 arbres B nécessaire pour rechercher un peu de données dans une même base de données.

Vous avez des données ?

Dans la plupart des cas, je dirais que les arbres RB en mémoire sont plus rapides.

Vous avez des données ?

La recherche étant binaire, il est très facile de trouver quelque chose.B-tree peut avoir plusieurs enfants par nœud, donc sur chaque nœud, vous devez analyser le nœud pour rechercher l'enfant approprié.Il s'agit d'une opération O(N).

La taille de chaque nœud est un paramètre fixe, donc même si vous effectuez un scan linéaire, c'est O(1).Si nous exagérons la taille de chaque nœud, notez que vous gardez généralement le tableau trié afin qu'il soit O (log n).

Sur un arbre RB, ce serait O(logN) puisque vous effectuez une comparaison puis un branchement.

Vous comparez des pommes et des oranges.Le O (log n) est dû au fait que la hauteur de l'arbre est au plus O (log n), tout comme c'est le cas pour un arbre B.

De plus, à moins que vous ne jouiez de vilaines astuces d'allocation avec les arbres rouge-noir, il semble raisonnable de supposer que les arbres B ont un meilleur comportement de mise en cache (ils accèdent à un tableau, pas à des pointeurs éparpillés partout, et ont moins de surcharge d'allocation, augmentant la mémoire localité encore plus), ce qui pourrait l'aider dans la course de vitesse.

Je peux souligner des preuves expérimentales selon lesquelles les arbres B (avec des paramètres de taille 32 et 64, en particulier) sont très compétitifs avec les arbres rouge-noir pour les petites tailles et les surpassent haut la main, même pour des valeurs de n modérément grandes.Voir http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

Les arbres B sont plus rapides.Pourquoi?Je suppose que cela est dû à la localité de la mémoire, à un meilleur comportement de mise en cache et à moins de poursuite de pointeur (qui sont, sinon les mêmes choses, qui se chevauchent dans une certaine mesure).

Autres conseils

En fait, Wikipédia propose un excellent article qui montre que chaque RB-Tree peut facilement être exprimé sous forme de B-Tree.Prenons l'arbre suivant comme exemple :

maintenant, convertissez-le simplement en B-Tree (pour rendre cela plus évident, les nœuds sont toujours colorés en R/B, ce que vous n'avez généralement pas dans un B-Tree) :

Même arbre que B-Tree

(je ne peux pas ajouter l'image ici pour une raison étrange)

Il en va de même pour tout autre RB-Tree.C'est extrait de cet article :

http://en.wikipedia.org/wiki/Red-black_tree

Pour citer cet article :

L'arbre rouge-noir est ensuite structurellement équivalent à un arbre B de l'ordre 4, avec un facteur de remplissage minimum de 33% des valeurs par grappe avec une capacité maximale de 3 valeurs.

Je n'ai trouvé aucune donnée indiquant que l'un des deux est nettement meilleur que l'autre.Je suppose que l'un des deux était déjà éteint si tel était le cas.Ils sont différents en ce qui concerne la quantité de données qu'ils doivent stocker en mémoire et la complexité d'ajouter/supprimer des nœuds de l'arborescence.

Mise à jour:

Mes tests personnels suggèrent que les B-Trees sont meilleurs lors de la recherche de données, car ils ont une meilleure localisation des données et le cache du processeur peut donc effectuer des comparaisons un peu plus rapidement.Plus l'ordre d'un B-Tree est élevé (l'ordre correspond au nombre d'enfants qu'une note peut avoir), plus la recherche sera rapide.D’un autre côté, plus leur ordre est élevé, plus leurs performances en matière d’ajout et de suppression de nouvelles entrées sont médiocres.Cela est dû au fait que l’ajout d’une valeur au sein d’un nœud a une complexité linéaire.Comme chaque nœud est un tableau trié, vous devez déplacer de nombreux éléments dans ce tableau lorsque vous ajoutez un élément au milieu :tous les éléments à gauche du nouvel élément doivent être déplacés d'une position vers la gauche ou tous les éléments à droite du nouvel élément doivent être déplacés d'une position vers la droite.Si une valeur se déplace d'un nœud vers le haut lors d'une insertion (ce qui arrive fréquemment dans un B-Tree), elle laisse un trou qui doit également être rempli soit en déplaçant tous les éléments de la gauche d'une position vers la droite, soit en déplaçant tous les éléments vers la droite une position vers la gauche.Ces opérations (en C généralement effectuées par memmove) sont en fait O(n).Ainsi, plus l’ordre du B-Tree est élevé, plus la recherche est rapide mais plus la modification est lente.En revanche si vous choisissez la commande trop basse (ex.3), un B-Tree présente en pratique peu d'avantages ou d'inconvénients par rapport aux autres structures arborescentes (dans ce cas, vous pouvez aussi bien utiliser autre chose).Ainsi, je créerais toujours des B-Trees avec des commandes élevées (au moins 4, 8 et plus, c'est bien).

Les systèmes de fichiers, qui sont souvent basés sur des B-Trees, utilisent des ordres beaucoup plus élevés (ordre 200 et même beaucoup plus) - en effet, ils choisissent généralement l'ordre suffisamment élevé pour qu'une note (lorsqu'elle contient le nombre maximum d'éléments autorisés) soit égale à la taille d'un secteur du disque dur ou d'un cluster du système de fichiers.Cela donne des performances optimales (puisqu'un disque dur ne peut écrire qu'un secteur complet à la fois, même lorsqu'un seul octet est modifié, le secteur complet est de toute façon réécrit) et une utilisation optimale de l'espace (car chaque entrée de données sur le disque est au moins égale à la taille de un cluster ou est un multiple des tailles de cluster, quelle que soit la taille réelle des données).En raison du fait que le matériel considère les données comme des secteurs et que le système de fichiers regroupe les secteurs en clusters, les B-Trees peuvent produire de bien meilleures performances et une meilleure utilisation de l'espace pour les systèmes de fichiers que n'importe quelle autre structure arborescente ;c'est pourquoi ils sont si populaires pour les systèmes de fichiers.

Lorsque votre application met constamment à jour l'arborescence, en y ajoutant ou en supprimant des valeurs, un RB-Tree ou un AVL-Tree peut afficher de meilleures performances en moyenne par rapport à un B-Tree avec un ordre élevé.Un peu pire pour les recherches et elles peuvent également nécessiter plus de mémoire, mais les modifications sont donc généralement rapides.En fait, les arbres RB sont encore plus rapides pour les modifications que les arbres AVL, c'est pourquoi les arbres AVL sont un peu plus rapides pour les recherches car ils sont généralement moins profonds.

Donc, comme d'habitude, cela dépend beaucoup de ce que fait votre application.Mes recommandations sont :

Beaucoup de recherches, peu de modifications :B-Tree (avec ordre élevé)
Beaucoup de recherches, beaucoup de modifications :Arbre AVL
Petites recherches, beaucoup de modifications :Arbre RB

Une alternative à tous ces arbres est Arbres AA.Comme ceci Le document PDF suggère, les AA-Trees (qui sont en fait un sous-groupe de RB-Trees) ont des performances presque égales à celles des RB-Trees normaux, mais ils sont beaucoup plus faciles à mettre en œuvre que les RB-Trees, AVL-Trees ou B-Trees.Voici une mise en œuvre complète, regarder comme c'est petit (la fonction principale ne fait pas partie de l'implémentation et la moitié des lignes d'implémentation sont en fait des commentaires).

Comme le montre le document PDF, un Treap est également une alternative intéressante à l’implémentation classique des arbres.Un Treap est également un arbre binaire, mais qui n'essaie pas d'imposer un équilibrage.Pour éviter les pires scénarios que vous pourriez rencontrer dans des arbres binaires déséquilibrés (ce qui ferait que les recherches deviendraient O(n) au lieu de O(log n)), un Treap ajoute un peu de caractère aléatoire à l'arbre.Le hasard ne peut pas garantir que l’arbre soit bien équilibré, mais il rend également très improbable que l’arbre soit extrêmement déséquilibré.

Rien n'empêche une implémentation de B-Tree qui ne fonctionne qu'en mémoire.En fait, si les comparaisons clés sont bon marché, le B-Tree en mémoire peut être plus rapide car son regroupement de plusieurs clés dans un seul nœud entraînera moins le cache manque lors des recherches.Voir ce lien pour les comparaisons de performances.Une citation:"Les résultats des tests de vitesse sont intéressants et montrent que l'arbre B + est considérablement plus rapide pour les arbres contenant plus de 16 000 éléments." (L'arbre B + n'est qu'une variation de B-Tree).

La question est ancienne mais je pense qu'elle est toujours d'actualité.Jonas Kölker et Mecki ont donné de très bonnes réponses, mais je ne pense pas que les réponses couvrent toute l'histoire.Je dirais même que toute la discussion passe à côté de l'essentiel :-).

Ce qui a été dit à propos des B-Trees est vrai lorsque les entrées sont relativement petites (entiers, petites chaînes/mots, flottants, etc.).Lorsque les entrées sont volumineuses (plus de 100 B), les différences deviennent plus petites/insignifiantes.

Permettez-moi de résumer les principaux points concernant les B-Trees :

Ils sont plus rapides que n'importe quel arbre de recherche binaire (BST) en raison de la localité de la mémoire (ce qui entraîne moins d'échecs de cache et de TLB).
Les arbres B sont généralement plus efficaces dans l'espace si les entrées sont relativement petites ou si les entrées sont de taille variable.La gestion de l'espace libre est plus facile (vous allouez des morceaux de mémoire plus grands) et la surcharge supplémentaire des métadonnées par entrée est plus faible.Les arbres B gaspilleront un peu d'espace car les nœuds ne sont pas toujours pleins, cependant, ils finiront par être plus compacts que les arbres de recherche binaires.
La grande performance O ( O(logN) ) est la même pour les deux.De plus, si vous effectuez une recherche binaire à l'intérieur de chaque nœud B-Tree, vous vous retrouverez même avec le même nombre de comparaisons que dans un BST (c'est un bel exercice mathématique pour vérifier cela).Si la taille du nœud B-Tree est sensible (taille de la ligne de cache 1-4x), la recherche linéaire à l'intérieur de chaque nœud est encore plus rapide en raison de la préfecciation matérielle.Vous pouvez également utiliser des instructions SIMD pour comparer les types de données de base (par exempleentiers).
Les B-Trees sont mieux adaptés à la compression :il y a plus de données par nœud à compresser.Dans certains cas, cela peut être un énorme avantage.Pensez simplement à une clé à incrémentation automatique dans une table de base de données relationnelle utilisée pour créer un index.Les nœuds principaux d'un B-Tree contiennent des entiers consécutifs qui se compressent très, très bien.
Les B-Trees sont clairement beaucoup, beaucoup plus rapides lorsqu'ils sont stockés sur un stockage secondaire (où vous devez bloquer les E/S).

Sur le papier, les B-Trees présentent de nombreux avantages et pratiquement aucun inconvénient.Alors, faut-il simplement utiliser des B-Trees pour obtenir les meilleures performances ?

La réponse est généralement NON – si l’arbre tient dans la mémoire.Dans les cas où les performances sont cruciales, vous souhaitez une structure de données arborescente sécurisée pour les threads (en termes simples, plusieurs threads peuvent faire plus de travail qu'un seul).Il est plus problématique de faire en sorte qu'un B-Tree prenne en charge les accès simultanés que de créer un BST.Le moyen le plus simple de faire en sorte qu'une arborescence prenne en charge les accès simultanés est de verrouiller les nœuds lorsque vous les parcourez/les modifiez.Dans un B-Tree, vous verrouillez plus d'entrées par nœud, ce qui entraîne plus de points de sérialisation et plus de verrous contestés.

Toutes les versions d'arborescence (AVL, Red/Black, B-Tree, etc.) ont d'innombrables variantes qui diffèrent par la façon dont elles prennent en charge la concurrence.Les algorithmes vanille enseignés dans un cours universitaire ou lus dans certains livres d'introduction ne sont presque jamais utilisés dans la pratique.Il est donc difficile de dire quel arbre fonctionne le mieux car il n’existe aucun accord officiel sur les algorithmes exacts derrière chaque arbre.Je suggérerais de considérer les arbres mentionnés davantage comme des classes de structures de données qui obéissent à certains invariants arborescents plutôt que comme des structures de données précises.

Prenons par exemple le B-Tree.Le B-Tree vanille n'est presque jamais utilisé dans la pratique - vous ne pouvez pas le faire évoluer correctement !La variante B-Tree la plus couramment utilisée est le B+-Tree (largement utilisé dans les systèmes de fichiers et les bases de données).Les principales différences entre le B+-Tree et le B-Tree :1) vous ne stockez pas les entrées dans les nœuds internes de l'arborescence (vous n'avez donc pas besoin de verrous en écriture en haut de l'arborescence lors de la modification d'une entrée stockée dans un nœud interne) ;2) vous avez des liens entre les nœuds au même niveau (vous n'avez donc pas besoin de verrouiller le parent d'un nœud lors des recherches de plage).

J'espère que ça aide.

Les gars de Google ont récemment publié leur implémentation de conteneurs STL, basés sur des B-trees.Ils affirment que leur version est plus rapide et consomme moins de mémoire par rapport aux conteneurs STL standard, implémentés via des arbres rouge-noir.Plus de détails ici

Pour certaines applications, les arbres B sont nettement plus rapides que les BST.Les arbres que vous pourrez trouver ici :

http://freshmeat.net/projects/bps

sont assez rapides.Ils utilisent également moins de mémoire que les implémentations BST classiques, car ils ne nécessitent pas l'infrastructure BST de 2 ou 3 pointeurs par nœud, plus quelques champs supplémentaires pour conserver les informations d'équilibrage.

Ils sont utilisés dans différentes circonstances - les arbres B sont utilisés lorsque les nœuds de l'arbre doivent être conservés ensemble dans le stockage - généralement parce que le stockage est une page de disque et que le rééquilibrage peut donc être très coûteux.Les arbres RB sont utilisés lorsque vous n'avez pas cette contrainte.Ainsi, les arbres B seront probablement plus rapides si vous souhaitez implémenter (disons) un index de base de données relationnelle, tandis que les arbres RB seront probablement plus rapides pour (disons) une recherche en mémoire.

Ils ont tous le même comportement asymptotique, donc les performances dépendent davantage de l'implémentation que du type d'arbre que vous utilisez.Une combinaison de structures arborescentes pourrait en fait être l'approche la plus rapide, dans laquelle chaque nœud d'un arbre B s'inscrit exactement dans une ligne de cache et une sorte d'arbre binaire est utilisée pour effectuer une recherche dans chaque nœud.Gérer vous-même la mémoire des nœuds peut également vous permettre d'obtenir une localité de cache encore plus grande, mais à un prix très élevé.

Personnellement, j'utilise simplement ce qui se trouve dans la bibliothèque standard du langage que j'utilise, car cela demande beaucoup de travail pour un très faible gain de performances (le cas échéant).

Sur le plan théorique...Les arbres RB sont en fait très similaires aux arbres B, car ils simulent le comportement des arbres 2-3-4.Les arbres AA sont une structure similaire, qui simule plutôt 2 ou 3 arbres.

de plus ... la hauteur d'un arbre rouge noir est O(log[2] N) alors que celle du B-tree est O(log[q] N) où plafond[N]<= q <= N .Donc, si nous considérons les comparaisons dans chaque tableau clé de l'arbre B (qui est fixé comme mentionné ci-dessus), alors la complexité temporelle de l'arbre B <= complexité temporelle de l'arbre rouge-noir.(cas égal pour un enregistrement unique de taille égale à celle d'un bloc)

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow