B-tree plus rapide que AVL ou RedBlack-Tree?

Question

Je sais que la performance n'est jamais noir et blanc, souvent d'une mise en œuvre est plus rapide dans le cas où X et plus lent dans le cas où Y, etc. mais, en général - sont des B-arbres plus vite, puis AVL ou RedBlack-Arbres? Ils sont beaucoup plus complexes à mettre en œuvre puis AVL arbres (et peut-être même RedBlack-arbres?), mais sont-ils plus vite (le fait de leur complexité payer) ?

Edit: je tiens aussi à ajouter que si ils sont plus rapides, puis l'équivalent AVL/RedBlack arbre (en termes de nœuds/contenu) - pourquoi sont-ils plus vite?

Answer 1

Sean post (actuellement acceptées) est plein de bêtises. Désolé Sean, je ne veux pas être impoli; j'espère pouvoir vous convaincre que ma déclaration est basé sur des faits.

Ils sont totalement différents dans leur cas d'utilisation, de sorte qu'il n'est pas possible de faire une comparaison.

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

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

toujours O(log n)

B-arbres sont généralement basés sur le disque structures, et sont donc intrinsèquement plus lente que les données en mémoire.

Non-sens. Lorsque vous stockez des arbres de recherche sur le disque, vous utilisez généralement les B-arbres. C'est bien vrai. Lorsque vous stockez des données sur le disque, c'est plus lent pour accéder à des données en mémoire. Mais un rouge-noir arbre stockées sur le disque est aussi plus lent qu'un rouge-noir arbre stockées dans la mémoire.

Vous êtes à comparer des pommes et des oranges ici. Ce qui est vraiment intéressant est la comparaison de dans-mémoire B-arbres et en mémoire des arbres rouge-noir.

[En aparté: B-arbres, plutôt que des arbres rouge-noir, sont théoriquement efficace dans le I/O-modèle. J'ai testé expérimentalement (et validés) le I/O-modèle pour le tri; j'avais espérer qu'il fonctionne pour les B-arbres.]

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

Pour être clair, la gamme de taille de B-arbre de nœuds est un paramètre de l'arbre (en C++, vous pouvez utiliser une valeur entière comme un paramètre du modèle).

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

Je me souviens à être beaucoup plus simple à comprendre (et à mettre en œuvre) que les arbres rouge-noir.

B-arbre essayer de minimiser le nombre d'accès disque, de sorte que la récupération de données est raisonnablement déterministe.

C'est bien vrai.

Il n'est pas rare de voir quelque chose comme 4 B-arbre d'accès nécessaires à la recherche d'un bit de données dans un base de données.

Obtenu des données?

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

Obtenu des données?

Parce que la recherche est binaire, il est très facile de trouver quelque chose. B-arbre peut avoir plusieurs enfants par nœud, donc sur chaque nœud, vous devez analyser le nœud de regarder pour enfant approprié. C'est un O(N) opérations.

La taille de chaque nœud est un paramètre fixe, de sorte que même si vous faites une analyse linéaire, il est O(1). Si nous grands-oh sur la taille de chaque nœud, notez que généralement garder le tableau trié il est donc O(log n).

Sur un RB-arbre ce serait O(logN) depuis que vous êtes en train de faire une comparaison et puis de bifurquer.

Vous êtes à comparer des pommes et des oranges. Le O(log n) c'est parce que la hauteur de l'arbre est au plus O(log n), comme elle l'est pour un B-arbre.

Aussi, à moins que vous la jouer méchant allocation des trucs avec les arbres rouge-noir, il semble raisonnable de conjecturer que les B-arbres ont un meilleur comportement de mise en cache (il accède à un tableau, pas des pointeurs éparpillés sur toute la place, et a moins de l'allocation des frais généraux de l'augmentation de la mémoire de la localité même plus), ce qui pourrait l'aider dans la course de vitesse.

Je peux montrer des preuves expérimentales que les B-arbres (avec les paramètres de la taille 32 et 64 ans, en particulier) sont très compétitifs avec des arbres rouge-noir pour les petites tailles, et supérieure à celle des mains vers le bas, même modérément grandes valeurs de n. Voir http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

B-arbres sont plus rapides. Pourquoi? Je conjecture que c'est en raison de la localité de mémoire, un meilleur comportement de mise en cache et moins pointeur de chasser (qui sont, si pas les mêmes choses, qui se chevauchent dans une certaine mesure).

Answer 2

En fait, Wikipédia a un excellent article qui montre chaque RB-Arbre peut facilement être exprimé comme un B-Arbre. Prendre l'arbre suivant:

maintenant il suffit de le convertir à un B-Arbre (pour le rendre plus évident, les nœuds sont toujours de couleur R/B, ce que vous n'avez généralement pas dans un B-Arbre):

Même Arborescence que B-Arbre

(impossible d'ajouter l'image ici, pour une raison ou une autre)

Même chose est vraie pour tous les autres RB-Arbre. Il est pris à partir de cet article:

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

Pour citer cet article:

Le rouge-noir arbre est alors structurellement équivalent à un B-arbre de ordre 4, avec un minimum de facteur de remplissage de 33% des valeurs par cluster avec un capacité maximum de 3 valeurs.

Je n'ai pas trouvé de données que l'un des deux est nettement mieux que les autres. Je suppose que l'un des deux était déjà mort si c'était le cas. Ils sont différents quant à la quantité de données qu'ils doivent stocker dans la mémoire et combien il est compliqué à ajouter/supprimer des nœuds de l'arbre.

Mise à jour:

Mon tests suggèrent que les B-Arbres sont mieux lors de la recherche de données, car ils ont de meilleures localité des données et donc le CPU cache peut ne compare un peu plus rapide. Le supérieur de l'ordre d'un B-Arbre (l'ordre est le nombre d'enfants d'une note), plus la recherche sera. D'autre part, ils ont de moins bonnes performances pour l'ajout et la suppression de nouvelles entrées à la plus élevée de sa commande. Ceci est causé par le fait que l'ajout d'une valeur dans un des nœuds de complexité linéaire. Comme chaque nœud est un tableau trié, vous devez déplacer beaucoup d'éléments dans la pile lors de l'ajout d'un élément dans le milieu: tous les éléments à gauche de l'élément nouveau doit être déplacée d'une position vers la gauche ou tous les éléments à droite de l'élément nouveau doit être déplacée 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-Arbre), il laisse un trou qui doit également être rempli soit par le déplacement de tous les éléments de la gauche d'une position vers la droite ou par déplacement de tous les éléments à droite d'une position vers la gauche. Ces opérations (en C, généralement effectuée par memmove) sont en fait O(n). Donc, plus l'ordre du B-Arbre, le plus rapide de la recherche, mais le ralentissement de la modification. D'autre part, si vous choisissez la commande trop faible (par exemple 3), un Arbre-B montre peu d'avantages ou inconvénients par rapport à d'autres structures en arbre dans la pratique (dans ce cas, vous pouvez tout aussi bien utiliser autre chose). Donc j'avais toujours créer des B-Arbres à haute ordres (au moins 4, 8 et est très bien).

Les systèmes de fichiers, qui souvent se base sur les B-Arbres, l'utilisation de beaucoup d'ordres supérieurs (de l'ordre de 200 et même beaucoup plus) - c'est parce qu'ils ont l'habitude de choisir l'ordre suffisamment élevé pour qu'une note (quand ils contiennent nombre maximal d'éléments) est égale à la taille d'un secteur sur un disque dur ou d'un cluster du système de fichiers. Cela donne une performance optimale (depuis un HD ne peut écrire qu'un secteur à un moment, même quand juste un octet est modifié, l'ensemble du secteur est réécrit de toute façon) et d'optimiser l'utilisation de l'espace (comme à chaque entrée de données sur le disque au moins égale à la taille d'un cluster ou est un multiple de la taille du cluster, n'importe comment grand les données est vraiment). Causé par le fait que le matériel ne voit données que les secteurs d'activité et le système de fichiers de groupes de secteurs de clusters, B-Arbres peuvent obtenir beaucoup de meilleures performances et l'utilisation de l'espace pour les systèmes de fichiers que toute autre structure de l'arbre; c'est pourquoi ils sont si populaires pour les systèmes de fichiers.

Lorsque votre application est constamment mise à jour de l'arbre, en ajoutant ou en supprimant des valeurs, un RB-Arbre ou un AVL-Arbre peut afficher de meilleures performances en moyenne comparé à un B-Arbre avec ordre élevé. Un peu moins bonne pour les recherches et ils pourraient également besoin de plus de mémoire, mais pour cela, des modifications sont généralement rapides. En fait RB-Arbres sont encore plus rapide pour les modifications que AVL Arbres, à cet effet, AVL-les Arbres sont un peu plus rapide pour les recherches qu'ils sont généralement moins profondes.

Donc comme d'habitude ça dépend beaucoup de ce que votre application est en train de faire. Mes recommandations sont les suivantes:

1. Beaucoup de recherches, peu de modifications: B-Arbre (avec ordre élevé)
2. Beaucoup de recherches, beaucoup de modifications lors de sa réunion: AVL-Arbre
3. Peu de recherches, de nombreuses modifications: RB-Arbre

Une alternative à tous ces arbres sont AA-Arbres. Comme ce PDF document suggère, AA-Arbres (qui sont en fait un sous-groupe de RB-Arbres) sont presque les mêmes caractéristiques à la normale RB-Arbres, mais ils sont beaucoup plus faciles à mettre en œuvre que RB-Arbres AVL Arbres, ou des B-Arbres. Voici une mise en œuvre complète, regardez comment petit, qu'il est (la fonction main ne fait pas partie de la mise en œuvre et la moitié de la mise en œuvre des lignes sont en fait des commentaires).

Comme le PDF document montre, un Treap est également une alternative intéressante à l'arbre classique de la mise en œuvre. Un Treap est aussi un arbre binaire, mais à celui qui n'a pas essayer d'appliquer de l'équilibrage. Pour éviter le pire des scénarios que vous pouvez obtenir dans déséquilibrée des arbres binaires (causant des recherches pour devenir O(n) au lieu de O(log n)), un Treap ajoute un peu de hasard pour de l'arbre. L'aléatoire ne peut pas garantir que l'arbre est bien équilibré, mais il rend aussi très peu probable que l'arbre est extrêmement déséquilibrée.

Answer 3

Rien n'empêche un B-Arbre de mise en œuvre qui ne fonctionne que dans la mémoire. En fait, si les comparaisons clés sont bon marché, en mémoire B-Arbre peut être plus rapide parce que son emballage de multiples clés d'un nœud causera moins de défauts de cache lors de la recherche. Voir ce lien pour les comparaisons de performances. Une citation: "Les résultats des tests de vitesse sont intéressantes et montrent l'arborescence B+ pour être beaucoup plus importante pour les arbres contenant plus de 16 000 articles." (B+Tree est juste une variation sur les B-Arbres).

Answer 4

La question est vieux, mais je pense que c'est toujours d'actualité. Jonas Kölker et Mecki a donné de très bonnes réponses, mais je ne pense pas que les réponses couvrent l'ensemble de l'histoire. Je voudrais même dire que l'ensemble de la discussion est à côté de la question :-).

Ce qui a été dit sur les B-Arbres est vrai lorsque les entrées sont relativement petites (entiers, les petites chaînes de caractères/mots, flotteurs, etc). Lorsque les entrées sont grandes (plus de 100 G), les différences deviennent plus petite ou insignifiante.

Permettez-moi de résumer les points principaux sur les B-Arbres:

• Ils sont plus rapides que n'importe quel Arbre de Recherche Binaire (techniciennes se chargent) due à la localité de mémoire (ce qui entraîne moins de cache et d'absences TLB).

• B-les Arbres sont généralement plus efficace de l'espace si les entrées sont relativement petite ou si les entrées sont de taille variable. Libre de gestion de l'espace est plus facile (vous allouer les plus gros morceaux de la mémoire) et les métadonnées supplémentaires frais généraux par l'entrée est plus faible. B-Arbres les déchets de l'espace comme des nœuds ne sont pas toujours, cependant, ils finissent par être plus compact que les Binaires de Recherche Arbres.

• Le grand O de la performance ( O(logN) ) est la même pour les deux. En outre, si vous n'binaire de recherche à l'intérieur de chaque B-nœud de l'Arborescence, vous allez même jusqu'à la fin avec le même nombre de comparaisons dans un BST (c'est un beau exercices de maths pour le vérifier). Si le B-Arbre du nœud de taille raisonnable (1-4x taille de ligne de cache), linéaire de la recherche à l'intérieur de chaque nœud est encore plus rapide en raison de le matériel de pré-chargement. Vous pouvez également utiliser les instructions SIMD pour la comparaison de types de données de base (par exemple les entiers).

• B-Arbres sont mieux adaptés à la compression: il n'y a plus de données par nœud pour compresser. Dans certains cas, cela peut être un avantage énorme. Il suffit de penser à une auto-incrémentation d'une clé dans une table de base de données relationnelle qui est utilisé pour créer un index. Le chef de nœuds d'un Arbre-B contiennent des nombres entiers consécutifs qui compressent très, très bien.

• B-Arbres sont clairement beaucoup plus rapidement lorsqu'ils sont stockés sur le stockage secondaire (où vous avez besoin de faire bloc IO).

Sur le papier, les B-Arbres ont beaucoup d'avantages et à proximité sans les inconvénients. Alors, doit-on simplement l'utilisation de B-Arbres pour de meilleures performances?

La réponse est en général PAS -- si l'arbre s'inscrit dans la mémoire. Dans les cas où la performance est crucial que vous voulez un thread-safe arborescente de la structure des données (il suffit de mettre, plusieurs threads peuvent faire plus de travail que d'un seul). Il est de plus en plus problématique pour faire un B-Arbre de support des accès simultanés que de faire un BST. La plus simple façon de faire un arbre de support des accès simultanés est de verrouiller les nœuds que vous traversez/modifier. Dans un B-Arbre vous verrouillez plus d'entrées par nœud, résultant en plus de la sérialisation points et plus soutenu serrures.

Tous les arbres versions (AVL, Rouge/Noir, B-Tree, une autres) ont d'innombrables variantes qui diffèrent dans leur façon de soutenir la concurrence. La vanille algorithmes qui sont enseignées dans un cours à l'université ou à la lecture de certains livres d'introduction sont presque jamais utilisées dans la pratique. Donc, il est difficile de dire de quel arbre donne de meilleurs résultats car il n'existe aucun accord officiel sur les algorithmes exacts sont derrière chaque arbre. Je vous propose de considérer les arbres mentionnés plus comme données de la structure des classes qui obéissent à certains arbres comme les invariants plutôt que des données précises-structures.

Prenez par exemple le B-Arbre. De la vanille en B-Arbre est presque jamais utilisée dans la pratique, vous ne pouvez pas le faire à l'échelle ainsi! Le plus commun de B-Tree variante utilisée est le B+-Arbre (largement utilisé dans des systèmes de fichiers, bases de données). Les principales différences entre les B+-Arbre et l'Arbre-B: 1) vous n'avez pas de stocker des entrées à l'intérieur des nœuds de l'arbre (donc vous n'avez pas besoin d'écrire des verrous haut dans l'arbre lors de la modification d'une entrée enregistrée dans un intérieur nœud); 2) vous avez des liens entre les nœuds au même niveau (donc vous n'avez pas à verrouiller le parent d'un nœud lorsque vous faites des recherches).

J'espère que cette aide.

Answer 5

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