Différence entre les B-Arbres et les Arbres 2-3-4

...un lien vers Wikipedia et un devis:

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

Un 2-3-4 est un B-tree.

Il est appelé arbre 2-3-4 parce que le nombre d'enfants pour un non-feuille, non-nœud racine est de 2,3 ou 4.

S'il avait été de 6, il aurait pu s'appeler un 3-4-5-6 arbre, ou 3-6 arbre pour faire court.

Depuis, le nombre minimum d'enfants est la moitié de la valeur maximum, on peut généralement ignorer l'ancienne et de parler d'un B-arbre d'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 de 4.

C'est le pire et le meilleur des cas, la hauteur est donnée par la la formule générale pour les B-arbres.

Dans le meilleur des cas: journal_mn. (tous les nœuds sont pleins)

Le pire des cas: journal_m/2n. (tous les nœuds sont à moitié vide)

Où

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

"B arbre peut avoir un ordre de n'importe quel nombre " - oui, mais pour une sous-classe de B-arbres, vous fixer ce nombre à l'avance. C'est comme de parler de papillons en général vs parler de la Papillon monarque. B-arbres sont une classe de structures de données, tout comme les papillons sont des insectes. Les papillons monarques sont une sous-classe de papillons, tout comme les arbres 2-3-4 sont une sous-classe de B-arbres.

OriginalL'auteur Andras Vass