Max et min nombre de clés dans un B-arbre

Quel est le nombre maximum et minimum de touches qui peuvent être stockées dans un B-arbre d'ordre de 128 et de hauteur 3?

Pour le maximum, voici ce que j'ai fait:
Vous avez un seul nœud racine. Le maximum d'enfants d'un nœud racine est m (ordre), donc c'est de 128. Et chacun de ces 128 enfants ont 128 enfants, cela nous donne un total de 1+128+16384=16512 total de nœuds. Selon Wikipedia, un B-arbre de n nœuds peuvent stocker les n-1 touches, alors que nous laisse avec un maximum de 16511 clés.

Pour min:
Vous avez un seul nœud racine, et le nombre minimum d'enfants, ce qui peut avoir est de 2, et le nombre minimum d'enfants de ces 2 enfants peut avoir sont m/2, où m est l'ordre, afin de 64 enfants. Cela nous laisse avec 1+2+64+64=131 total des enfants et 131-1=130 clés.

Est ce que j'ai fait ici correct?

Ce qui est totalement faux calcul et de la accepté de répondre aussi des guides dans la fausse direction. La question est à propos de min et max n'. de touches, mais vous êtes le comptage des nœuds de l'arbre-B, puis le calcul des min/max pas. de touches qui peuvent être stockées dans un nœud avec x enfants.

OriginalL'auteur Snowman | 2011-04-05

  1. 0

    Cela dépend vraiment de la façon dont vous définissez l'ordre. Selon Knuth, de l'ordre d'un b-arbre est le nombre maximum d'enfants, ce qui voudrait dire que le max de réponse est de 129. Si la définition de la commande est le nombre minimum de touches de non-nœud racine, alors la réponse à la max est inconnue.

    À l'aide de cette définition, votre calcul de la valeur minimum est correct, mais votre maximum n'est pas, parce que chaque nœud, y compris les feuilles, contient m-1 clés. C'est également cohérente avec la définition de B-Arbre dans le Cormen. si n est 16512, et chaque n magasins 127 clés, la réponse est certainement pas 16511.

    OriginalL'auteur philosodad

  2. 5

    selon wikipedia , un nœud peut avoir au plus n-1 touches si il a n nœuds enfants.
    par conséquent ,

                               root [127keys]
                 128 childnodes [each having 127 keys]
             128*128 childnodes [each having 127 keys]

127+128*127+128*128*127 = total no of maximum allowed keys
    N'est-ce pas seulement un arbre d'une hauteur de 2? Je vois un arbre d'une hauteur de 0 comme un nœud (la racine).

    OriginalL'auteur Sukantu Barman

  3. 4

    Il y a des limites inférieure et supérieure sur le nombre de touches d'un nœud peut contenir. Ces limites sont exprimées en termes de fixe entier t >= 2 appelé le degré minimum de la B-arbre.

    • Chaque nœud autre que la racine doit avoir au moins t - 1 clés.
      Chaque noeud interne autre que la racine a au moins t enfants.
      Si l'arbre n'est pas vide, la racine doit avoir au moins une clé.

    • Chaque nœud peut contenir au plus 2t - 1 clés.
      Par conséquent, un nœud peut avoir au plus 2t enfants.
      On dit qu'un nœud est complète si elle contient exactement 2t - 1 touches.

    Max pas de clés pour la taille 3 = (2t-1) + (2t-1) * 2t + (2t-1) * 2 * 2voies

    Min pas de clés pour la taille 3 = (t-1) + (t-1)*t + (t-1) * t * t

    n'est-ce pas possible d'exprimer en tant que formule avec h = hauteur et t = degré de l'arbre-b:

    OriginalL'auteur Sampath Liyanage

  4. 0

    Voici le code C# pour calculer nombre maximum de clés pour tout B-Arbre étant donné le nombre de niveaux et le nombre maximum d'enfants d'un nœud peut avoir. 

            ///<summary>
        ///Given number of levels in the tree, computes the maximum number of keys the tree can hold. 
        ///</summary>
        ///<param name="levelCount">Is the number of levels in the tree. </param>
        ///<param name="MaxBranchingDegree ">Is the maximum number of children a node in the tree can have. </param>
        ///<returns>Maximum number of keys a tree with <paramref name="levelCount"> levels can hold. </returns>
        public int ComputeMaxKeyCount(int levelCount, int MaxBranchingDegree )
        {
           int maxKeys = 0;
           for (int l = 0; l < levelCount; l++)
           {
              maxKeys += (MaxBranchingDegree - 1) * (int)Math.Pow(MaxBranchingDegree, l);
           }
           return maxKeys;
        }

    OriginalL'auteur PiJei