Сколько элементов может быть сохранено в B-дереве порядка n?

В моей книге говорится, что порядок B-дерева - это максимальное количество указателей, которое может храниться в узле. (стр. 348) Количество «ключей» на единицу меньше порядка. Таким образом, B-дерево порядка n может содержать n-1 элемент.

Это книга Майкла Дж. Фолка «Файловые структуры», второе издание.

Если ваша формула для количества элементов не включает в себя экспоненцию, вы сделали это неправильно.

Бинарное дерево порядка 5 может содержать 2^0 + 2^1 + 2^2 + 2^3 + 2^4 элемента, поэтому 31 ... (что составляет 2^порядка - 1).

Редактировать: Похоже, я перепутал порядок и глубину/длину. Что такое порядок двоичного дерева? Похоже, вы обсуждаете B-деревья так, как будто они, по самой природе своего определения, не содержат максимум два дочерних элемента на элемент.

Терминология
Порядок B-дерева непостоянно определяется в литературе.
(см., Например, раздел терминологии в статье Википедии о B-деревьях )
Некоторые авторы считают его минимум количество ключей , которое может содержать нелистовой узел, в то время как другие считают, что это максимальное количество дочерних узлов , которое может содержать нелистовой узел ( что на единицу больше, чем максимальное количество ключей, которое может содержать такой узел).
Тем не менее многие другие обходят двусмысленность, предполагая ключ фиксированной длины (и узлы фиксированного размера), что делает минимум и максимум одинаковыми, поэтому два определения порядка дают значения, которые отличаются на 1 (как уже говорилось, количество ключей всегда на единицу меньше, чем количество дочерних элементов.)

Я определяю глубину как количество узлов, найденных на пути поиска к листовой записи, включая корень узел и листовой узел. В этом смысле очень мелкое дерево с только корневым узлом, указывающим непосредственно на листовые узлы, имеет глубину 2. Если бы это дерево вырастало и требовало промежуточного уровня нелистовых узлов, его глубина была бы 3 и т. Д.

Как многие элементы могут храниться в B-дереве порядка n?
Предполагая ключи фиксированной длины и предполагая, что "порядок" n определяется как максимальное количество дочерних узлов , ответ будет:

   (Average Number of elements that fit in one Leaf-node) * n ^ (depth - 1)

Как мне понять? ...:
Данные ("элементы") хранятся только в конечных узлах.Таким образом, количество удерживаемых элементов - это среднее количество элементов, которые помещаются в один узел, умноженное на количество листовых узлов.
Количество конечных узлов само определяется количеством дочерних узлов, которые помещаются в нелистовой узел (порядок). Например, нелистовой узел чуть выше листового узла указывает на n (порядок) листовых узлов. Затем нелистовой узел выше этого нелистового узла указывает на n подобных узлов и т. Д., Следовательно, «в степени (глубина -1)».

Обратите внимание, что приведенная выше формула обычно выполняется с использованием средних значений (ключей, содержащихся в нелистовом узле, и элементов, содержащихся в листовом узле), а не при фиксированной длине ключа и фиксированной длине записи: деревья обычно имеют узел размер, который соизмерим с размерами ключа и записи, следовательно, содержит числовой ключ или записи, которые достаточно велики, чтобы эффективное количество ключей или записей, содержащихся в любом листе, относительно мало отличалось от среднего.

Пример :
Дерево глубины 4 (корневой узел, два уровня нелистовых узлов и один уровень [очевидно] листовых узлов) и порядка 12 (нелистовые узлы могут содержать до 11 ключей, следовательно, указывают на 12 узлов ниже них) и такой, что конечные узлы могут содержать по 5 элементов каждый , будет:
- его корневой узел указывает на 12 узлов под ним - каждый узел под ним указывает на 12 узлов под ними (следовательно, на уровне «3» будет 12 * 12 узлов (при условии корень - это уровень 1 и т. д., эта нумерация, кстати, также неоднозначно определена ...) - каждый узел в "уровне 3" будет указывать на 12 листовых узлов (следовательно, будет 12 * 12 * 12 листовых узлы.
- каждый листовой узел имеет 5 элементов (в данном примере)
Следовательно .. такое дерево будет сохраняться ...

  Nb Of Elements in said tree = 5 * 12 * 12 * 12
                              = 5 * (12 ^ 3)
                              = 5 * (12 ^ depth -1)
                              = 8640

Распознать формулу в 3-й строке .

Что вообще примечательно для B-Tree,и что делает их популярными, так это то, что относительно мелкое дерево (дерево с ограниченным числом «переходов» между корнем и искомой записью) может содержать относительно большое количество записей. Это число умножается на порядок на каждом уровне.