arbre AVL par rapport à B-tree

Question

Comment est un autre arbre AVL d'un B-tree?

Answer 1

AVL sont destinés à être utilisés en mémoire, où l'accès aléatoire est relativement pas cher. B-arbres sont mieux adaptés pour le stockage disque sauvegardé, car ils groupe un plus grand nombre de clés dans chaque nœud pour minimiser le nombre de positionnements requis par une opération de lecture ou d'écriture. (C'est pourquoi B-arbres sont souvent utilisés dans les systèmes de fichiers et bases de données, tels que SQLite .)

Answer 2

Les deux l'arbre AVL et le B-tree sont similaires en ce qu'elles sont des structures de données qui, par leurs exigences, la cause de minimiser la hauteur de leurs arbres respectifs. Cette « brièveté » permet de rechercher à réaliser dans O (log n), parce que le plus grand nombre de lectures correspond à la hauteur de l'arbre.

    5
   / \
  3   7
 /   / \
1   6   9

Ceci est un arbre AVL, et est un arbre de recherche binaire à son noyau. Cependant, il est auto-équilibrage, ce qui signifie que lorsque vous ajoutez des éléments à l'arbre, il se restructurer pour maintenir aussi uniforme d'une hauteur que possible. Au fond, il ne permettra pas de longues branches.

A B-tree fait aussi, mais par un autre système de rééquilibrage. Il est un peu trop compliqué à écrire, mais si vous effectuez une recherche Google « animation B-tree » il y a des applets vraiment bien là-bas qui expliquent un B-arbre assez bien.

Ils sont différents en ce qu'un arbre AVL est mis en œuvre avec des solutions basées sur la mémoire à l'esprit, alors qu'un B-arbre est mis en œuvre avec des solutions sur disque à l'esprit. AVL ne sont pas conçus pour contenir des collections massives de données, car ils utilisent l'allocation dynamique de la mémoire et des pointeurs sur le bloc suivant de la mémoire. De toute évidence, nous pourrions reproduire les fonctionnalités d'un arbre AVL avec des emplacements de disque et des pointeurs de disque, mais il serait beaucoup plus lent parce que nous aurions encore un nombre important de lit pour lire un arbre d'une très grande taille.

Lorsque la collecte des données est si grand qu'il ne rentre pas dans la mémoire, la solution est un B-tree (factoid intéressant: il n'y a pas de consensus sur ce que le « B » signifie en fait). Un B-arbre possède de nombreux enfants à un noeud et plusieurs pointeurs vers nœud enfants. De cette façon, lors d'une lecture de disque (ce qui peut prendre environ 10 ms pour lire un bloc de disque), la quantité maximale de données du noeud correspondant est renvoyé, ainsi que des pointeurs vers des blocs de disque « de noeud de feuille ». Cela permet le temps de récupération de données à être amorti log (n), ce qui rend le B-tree particulièrement utile pour les bases de données et grande implémentations de récupération ensemble de données.

Answer 3

Un arbre AVL est un arbre de recherche binaire auto-équilibrage, équilibré pour maintenir la hauteur O (log n).

Un B-arbre est un arbre équilibré, mais il est un arbre binaire. Les nœuds ont plus d'enfants, ce qui augmente la recherche par nœud temps mais diminue le nombre de nœuds les besoins de recherche à visiter. Cela rend les bons pour les arbres sur disque. Pour plus de détails, consultez le Wikipedia article .

Answer 4

AVL est équilibrage automatique, ce qui garantit que toutes les opérations sont O (log n) en moyenne et pire des cas.

Answer 5

Le B-tree utilise toutes les idées décrites ci-dessus. En particulier, un B-tree:

1)keeps keys in sorted order for sequential traversing
2)uses a hierarchical index to minimize the number of disk reads
3)uses partially full blocks to speed insertions and deletions
4)keeps the index balanced with an elegant recursive algorithm

En outre, un arbre B-minimise les déchets en assurant que les nœuds intérieurs sont au moins à moitié plein. Un arbre B peut gérer un nombre arbitraire d'insertions et des deletions.

Answer 6

Un arbre AVL est un auto équilibrage arbre binaire qui permettent O (LGN) et un cas moyen le plus mauvais pour l'insertion de la recherche et les opérations de suppression. Il est utilisé dans les arbres de la recherche soutenue mémoire (jeux de données de taille modérée).

A B-Tree est principalement utilisé comme un arbre de recherche soutenu de stockage pour les ensembles de données très importants, car il nécessite moins de lectures sur le disque (puisque chaque noeud contient des clés où N> 1). A B-Tree est dit être un (N, N + 1) B-Tree, où N est le nombre de touches par noeud et N + 1 est le nombre d'enfants par noeud. Les plus touches par nœud les fois moins vous aurez besoin de lire à partir du disque et il sera également naturellement un arbre moins profond (moins les niveaux).

Answer 7

Ils sont très différents en effet, bien qu'ils servent en grande partie dans le même but: soutenir une table associative. Historiquement, l'arbre AVL ont été prises pour surperformer le B-tree pour les opérations en mémoire, mais attente particulièrement vrai lors de l'accès mémoire était pas cher (er) par rapport aux cycles CPU.

Bien que généralement utilisé dans les bases de données pour stocker les clés de longueur variable, les B-arbres sont spécialement conçus pour une longueur fixe et courts enregistrements (données clé +). Pour ces utilisations, qui peuvent surperformer de manière significative les arbres AVL pour des utilisations en mémoire, tant en termes d'encombrement de la mémoire (comme ils stockent des données plus compacte) et la vitesse (ils auraient beaucoup mieux localité de cache).

L2 est une bibliothèque de structures de données implémentant tables associatives très rapide et des séquences sur B-arbres. Il a également AVL, et de faire une comparaison entre les performances des deux est facile.

Answer 8

D'autres answerers ont déjà fourni assez en profondeur des détails techniques sur les deux AVL et B-Tree, mais je voudrais ajouter une information relativement novice en ce qui concerne ces deux :) -

• arbre AVL est un arbre binaire tandis que B-arbre est un arbre à plusieurs voies (arbre n-aire), à ??savoir un nœud dans arbre AVL peut avoir au niveau des noeuds max deux enfants et une pièce d'informations / données tout tout noeud dans un B-tree peut avoir n noeuds et n-1 élément d'information / Les données. B-tree, n est également connu sous son ordre.

Answer 9

En termes simples -

arbre AVL et arbre de recherche binaire sont à la fois, mais même arbre AVL a une contrainte que la différence entre soit la hauteur de l'arbre secondaire gauche et l'arbre secondaire droit devrait être 0, 1 ou -1.

Si rencontrent arbre de recherche binaire ces conditions, il sera appelé comme arbre AVL.

recherche binaire arbre + CONDITION DE LA HAUTEUR est un arbre AVL.

Reportez-vous: Introduction aux algorithmes par Cormen https://books.google.co.in/books ...