Максимальное и минимальное количество ключей в B-дереве

Question

Каково максимальное и минимальное количество ключей, которые можно сохранить в B-дереве порядка 128 и высоты 3?

Для максимума вот что я сделал: у вас есть один корневой узел.Максимальное число дочерних узлов, которое может иметь корневой узел, составляет m (порядок), то есть 128. И у каждого из этих 128 дочерних узлов есть 128 дочерних элементов, что дает нам в общей сложности 1 + 128 + 16384 = 16512 узлов.Согласно Википедии, B-дерево из n узлов может хранить n-1 ключей, так что у нас остается максимум 16511 ключей.

Для min: у вас есть один корневой узел и минимальное количествоэто может иметь 2 детей, и минимальное количество детей, которое могут иметь эти 2 ребенка, равно m / 2, где m - порядок, то есть по 64 ребенка.Это оставляет нам 1 + 2 + 64 + 64 = 131 общее количество детей и 131-1 = 130 ключей.

Правильно ли то, что я здесь сделал?

Answer 1

согласно википедии, узел может иметь не более n-1 ключей, если он имеет n дочерних узлов.следовательно,

                           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

Answer 2

Количество ключей может содержать нижняя и верхняя границы. Эти границы выражаются через фиксированное целое число t> = 2, называемое минимальной степенью B-дерева.

• Каждый узел, кроме корневого, должен иметь не менее t - 1 ключей. Каждый внутренний узел, кроме корня, имеет не менее t дочерних элементов. Если дерево непустое, корень должен иметь хотя бы один ключ.

• Каждый узел может содержать максимум 2t - 1 ключей. Следовательно, внутренний узел может иметь не более 2-х дочерних элементов. Мы говорим, что узел заполнен, если он содержит ровно 2t - 1 ключей.

Макс. Количество клавиш для высоты 3 = (2t-1) + (2t-1) * 2t + (2t-1) * 2t * 2t
Мин. Нет ключей для высоты 3 = (t-1) + (t-1) * t + (t-1) * t * t

Answer 3

Вот код C # для вычисления максимального количества ключей для любого B-дерева с заданным количеством уровней и максимальным числом дочерних узлов, которое может иметь узел.

        /// <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;
        }

Answer 4

Это действительно зависит от того, как вы определяете порядок. Согласно Кнуту, порядок b-дерева - это максимальное число дочерних элементов, что означает, что максимальный ответ равен 129. Если определение порядка - это минимальное количество ключей некорневого узла, то ответ на Макс неизвестен.

Используя это определение , вы вычисляете минимум правильно, но ваш максимум - нет, поскольку каждый узел , включая листья, содержит ключи m-1. Это также согласуется с определением B-Tree в Cormen. если n равно 16512, и каждый n хранит 127 ключей, ответ определенно не 16511.