Терминология
Порядок B-Tree непостоянно определен в литературе.
(см., например, раздел терминологии статьи Википедии о B-Trees )
Некоторые авторы считают, что это минимальное количество ключей , которое может содержать неконечный узел, в то время как другие считают, что это максимальное число дочерние узлы может содержать неконечный узел (что на один больше, чем максимальное количество ключей, которое может содержать такой узел).
Тем не менее, многие другие обходят неоднозначность, предполагая, что ключ фиксированной длины (и узлы фиксированного размера) делают минимальные и максимальные одинаковыми, поэтому два определения порядка дают значения, отличающиеся на 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 и что делает его популярным то, что относительно небольшое дерево (дерево с ограниченным количеством «прыжков» между корнем и искомой записью) может содержать запись с относительно большим числом , Это число , умноженное на порядок на каждом уровне.