Приветствую!

Вот у меня есть B+ дерево. Как вычислить оптимальный порядок дерева (максимальное количество ключей, хранимых в узле), в зависимости от количества элементов в дереве.

Вот у меня математика такая:
максимальное количество элементов в узле: N
Количество элементов: Z

Глубина дерева: log по основанию (N/2) от Z // N/2 — т.к в самом худшем случае в узле содержится N/2 ключей, а сложность оценивается при самом худшем случае.

Сложность: N/2 * log по снованию (N/2) от Z // множитель впереди N/2 — количество сравнений при поиске внутри узла (в какой узел следует спуститься дальше)

Тогда берем производную: (N/2 * log по снованию (N/2) от Z) штрих по N = 0
В итоге, при решении уравнения, получается что N не зависит от количества элементов и порядка 2*e = 5.4, т.е. порядок дерева примерно 5 или 6.

Где ошибка?

Здравствуйте, FreeX, Вы писали:

FX>В итоге, при решении уравнения, получается что N не зависит от количества элементов и порядка 2*e = 5.4, т.е. порядок дерева примерно 5 или 6.

FX>Где ошибка?

Никакой ошибки здесь нет. Система счисления с основанием e имеет максимальную плотность записи.
Т.к. ты рассматриваешь худший случай, в котором основание = n/2, то и резульат верен: n = 2 * e