Différence entre B-arbres et arbres 2-3-4

Question

Quelle est la différence entre les arbres B et 2-3-4 arbres?

En outre, comment voulez-vous trouver le maximum et la hauteur minimale de chacun?

Answer 1

... un lien vers Wikipedia et une citation:

  

"2-3-4 arbres B-arbres d'ordre 4."

A 2-3-4 est B-tree.
Il est appelé arbre 2-3-4 parce que le nombre d'enfants pour un non-feuille, noeud non racine est 2,3 ou 4.
Si elle avait été 6, il aurait pu être appelé un arbre 3-4-5-6, ou 3-6 arbre pour faire court.
Étant donné que le nombre minimum d'enfants est la moitié du maximum, on peut juste sauter habituellement l'ancien et parler d'un B-arbre de l'ordre m .
L'ordre d'un B-arbre est défini comme le nombre maximum d'enfants d'un nœud peut avoir.
Dans un arbre 2-3-4, comme nous l'avons vu, le maximum est 4.

Il est la hauteur pire et le meilleur cas est donnée par la formule générale pour B-arbres .

Le meilleur des cas : log _m n. (tous les noeuds sont pleins) Le pire des cas : log _{m / 2} n. (tous les noeuds sont à moitié vide)

où

• m est l'ordre de l'arbre - le nombre maximum d'enfants d'un noeud peut avoir, dans ce cas, 4 - et
• n est le nombre d'entrées dans l'arborescence

« arbre B peut avoir un ordre d'un nombre » - oui, mais pour une sous-classe particulière de B-arbres, vous fixer ce nombre à l'avance. Il est comme parler de papillons en général vs parler de la papillon Monarch . B-arbres sont une classe de structures de données, comme les papillons sont une classe d'insectes. papillons Monarch sont une sous-classe de papillons, tout comme les arbres 2-3-4 sont une sous-classe B-arbres.

Answer 2

la différence principale raison pour laquelle b-arbre entre en existence est le nombre de fractionnement des nœuds requis dans le temps d'insertion est inférieure à 2-4 arbre. Dans 2-4 arbre nous avons trouvé parfois un terme appelé fractionnement en cascade, mais en b-arbre il n'y a pas de séparation présente en cascade.