В B + дереве на фактические записи ссылаются изнутри листьев.Внутренние узлы, с другой стороны, не ссылаются на записи напрямую, а определяют диапазоны для значений ключа, чтобы пройти через дерево к листу (блоку), в котором, наконец, есть значения ключа для интересующих записей.
Другим свойством деревьев B + является то, что число дочерних элементов внутреннего узла имеет не только верхнюю границу (то есть разветвление F ), но и нижнюю границу: F / 2 .(Я игнорирую, что корень освобожден от этого нижнего правила).Этот коэффициент 1/2 является коэффициентом заполнения (0,5).
Количество листовых блоков ( L ) связано с количеством записей ( t )и разветвление ( F ), но не так, как дерево (не) сбалансировано.В лучшем, минимальном случае имеем:
min (L) = ⌈ t / F⌉
В худшем, максимальном случае имеем:
max (L) = t 2t / F⌉
Если у вас другой коэффициент заполнения ( c > = 0,5), то наихудший случай:
max (L) = ⌈ t / cF⌉
Имейте в виду, что увеличение коэффициента заполнения уменьшает используемое пространство, но увеличивает накладные расходы времени при вставке записей.Когда коэффициент заполнения будет близок к 1, использование пространства будет оставаться минимальным, но обновления будут выполняться медленно.