минимальное / максимальное количество записей на дереве B +?

Question

Я искал лучшие и худшие сценарии для дерева B + (http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights), но я не знаю, как использовать эту формулу с имеющейся у меня информацией. Допустим, у меня есть дерево B с 1000 записей, какое максимальное (и максимальное) количество уровней B может иметь? Я могу иметь столько / мало ключей на каждой странице. Я также могу иметь как можно больше / меньше страниц. Есть идеи? (Если вам интересно, это не домашнее задание, но оно, несомненно, поможет мне разобраться в некоторых вещах для hw.)

Answer 1

У меня нет математики, но ...

По сути, основным фактором глубины дерева является "разветвление" каждого узла дерева.

Обычно в простом B-дереве разветвление составляет 2, 2 узла в качестве дочерних для каждого узла в дереве.

Но с B + Tree, как правило, у них есть веер гораздо больше.

Одним из факторов, влияющих на воспроизведение, является размер узла на диске.

Например, если у вас есть размер страницы 4K и, скажем, 4000 байт свободного пространства (не включая любые другие указатели или другие метаданные, связанные с узлом), и допустим, что указатель на любой другой узел в дерево представляет собой 4-байтовое целое число. Если ваше B + Tree на самом деле хранит 4-байтовые целые числа, то объединенный размер (4 байта информации указателя + 4 байта информации ключа) = 8 байтов. 4000 свободных байтов / 8 байтов == 500 возможных детей.

Это даст вам веер из 500 для этого надуманного дела.

Таким образом, с одной страницей индекса, то есть корневым узлом или высотой 1 для дерева, вы можете сослаться на 500 записей. Добавьте еще один уровень, и вы получите 500 * 500, поэтому для 501 страницы 4K вы можете сослаться на 250 000 строк.

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

Но, надеюсь, вы сможете понять суть того, как все это работает.

Answer 2

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

1-й уровень (или корень) имеет m-1 записей 2-й уровень имеет m * (m-1) записей (поскольку корень имеет m дочерних элементов с m-1 ключами в каждой) 3-й уровень имеет m ^ 2 * (m-1) записей .... H-й уровень имеет m ^ (h-1) * (m-1)

Таким образом, если H - высота дерева, общее количество записей равно n = m ^ H-1 что эквивалентно H = log_m (n + 1)

Следовательно, в вашем случае, если у вас есть n = 1000 записей с каждым узлом, имеющим m детей (m должно быть нечетным), то наилучшая высота регистра будет равна log_m (1000 + 1)

Аналогично, для худшего случая:

Уровень 1 (root) имеет как минимум 1 запись (и минимум 2 дочерних) 2-й уровень имеет как минимум 2 * (d-1) записи (где d = ceil (m / 2) - минимальное количество дочерних элементов, которое может иметь каждый внутренний узел (кроме корневого)) 3-й уровень имеет 2d * (d-1) записей ... H-й уровень имеет 2 * d ^ (h-2) * (d-1) записей

Таким образом, если H - высота дерева, общее количество записей равно n = 2 * d ^ H-1, что эквивалентно H = log_d ((n + 1) / 2 + 1)

Следовательно, в вашем случае, если у вас n = 1000 записей с каждым узлом, имеющим m детей (m должно быть нечетным), тогда высота наихудшего случая будет равна log_d ((1000 + 1) / 2 + 1)

Answer 3

Зависит от арности дерева.Вы должны определить это значение.Если вы говорите, что у каждого узла может быть 4 дочерних элемента, а у вас 1000 записей, тогда высота будет

Наилучший случай log_4 (1000) = 5

Наихудший случай log_ {4/2} (1000) = 10

Арность равна m, а количество записей равно n.