Profondeur maximale d'un B-arbre
Comment pouvez-vous comprendre la profondeur maximale d'un B-arbre?
Disons que vous avez eu un B-arbre d'ordre 1625, ce qui signifie que chaque nœud a 1625 pointeurs et 1624 éléments.
Quelle est la profondeur maximale de l'arbre si elle contient 85,000,000 clés?
- En dehors de la commande, vous devez également indiquer le [moyenne] nombre d'enregistrements (ou "éléments") qui s'inscrivent dans un nœud feuille.
- Si c'est les devoirs veuillez étiqueter comme tels.
Vous devez vous connecter pour publier un commentaire.
En supposant
la compréhension de l'ordre défini dans la question
Spécifiquement que nous pouvons compter sur 1625 pointeurs par nœud (quelques significations de la commande définir comme le maximum nombre de touches ou des pointeurs, qui serait alors potentiellement augmenter la taille de l'arbre calculé ci-dessous)
... cet arbre aurait une profondeur minimale de 3, c'est à dire qu'il aurait un nœud racine, une couche de non-nœuds feuilles, et la couche de nœuds feuilles.
... cet arbre aurait une profondeur maximale de 3 ainsi.
Pour calculer la profondeur dans la plupart des cas optimal:
prendre le nombre total d'enregistrements, 85,000,000, diviser par l'ordre, de 1 625
cela donne au comte de la feuille de lignes : 52,308
prendre ce numéro de la feuille de lignes, divisez-le par la commande
cela donne 33; ce nombre est moins de l'ordre alors on peut arrêter de se diviser, c'est le nombre de pointeurs dans le nœud racine. A ce nombre, plus que ce qu'un nœud peut contenir que nous aurions un niveau supplémentaire et continuera de le diviser.
Nous avons fait deux divisions de sorte que la profondeur de l'arbre est de 3.
Le pire des cas, arriverait-il si tous les nœuds ont dû être séparés, donc la tenue en moyenne de l'ordre/2 (pas d'arrondi) des pointeurs. Le calcul pour le pire des cas est similaire, nous venons de le diviser par ordre /2 , c'est à dire 812.5, ce qui dans notre cas, la production de 104,616 feuille-nœuds, 129 non-nœuds feuilles au-dessus du niveau des feuilles, et enfin une racine de garder trace de ces 129 non-nœuds feuilles.
Le pire des cas la hauteur pour un B-Arbre d'ordre m est logm/2n.
Voir: http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights
B est un arbre équilibré , le pire des cas, la récupération est délimité par sa hauteur.Chaque nœud dans un Arbre de capacité de l'ordre a d. Profondeur maximale = pire des cas
d=1624/2=812
Hauteur <= logd+1 ((n+1)/2)+1
la réponse est log812+1 ((85,000,000+1)/2)+1
Profondeur maximale dépend des algorithmes utilisés pour manipuler l'arbre, et quelle est leur pire-cas de comportement est (je ne connais pas les détails, désolé). La profondeur approximative est log(N)/log(1625), en supposant un équilibrage parfait.
Un B+-arbre peut être légèrement plus profond, car seules les feuilles maintenez les touches, mais la différence est probablement négligeable. Il peut également être moins si l'on considère que chaque nœud non-feuille n'a qu'à tenir des pointeurs.
La formule de max profondeur d'un arbre b a déjà été donnée par Peut Berk Güder.
Dans votre cas m = 1625
Mais ayant un nombre impair de pointeurs et même le nombre de touches peut être pas une bonne idée
parce que dans ce cas, vous devrez inégalement diviser un nœud quand il est plein.
Plutôt que vous devriez garder nombre impair de touches et même le nombre de pointeurs par nœud pour les uniformes, le fractionnement des nœuds.
C'est pour les B+, pas sûr au sujet de B.
85,000,000 dossiers, dans le meilleur des cas, sont comptabilisés dans le plafond(85m/1624)=52340 feuilles. C'est le niveau inférieur, et c'est pourquoi nous nous en utilisant le nombre d'éléments, plutôt que le nombre de pointeurs.
Pour trouver combien de niveaux il y a, nous allons continuer à diviser la feuille numéros de nous trouver à l'ordre, en prenant le plafond le long du chemin: plafond(52340/1625)=33. Cette fois, nous utilisons le nombre de pointeurs, car nous avons déjà déterminé le niveau inférieur, où les éléments sont stockés, et qui travaille aujourd'hui avec des pointeurs pour pointer vers l'élément de feuilles.
Que ce nombre n'est pas plus grand que l'ordre lui-même, nous nous arrêtons là, car c'est la racine; haut niveau. Racine a 33 pointeurs qui peuvent indiquer un max de 33x1625 (53625) feuilles, la différence ne devrait pas vous embrouiller comme tous de l'élément feuilles pourrait être remplie au maximum. 53625 feuilles peuvent stocker plus, 53625x1624 (87,087,000) des éléments, ce qui est plus que suffisant pour tenir notre exemple.
Revenir à la question, il n'est que la racine, et l'élément feuilles du dessous, donc la profondeur est de 2.
Espère que cette aide.