массовая загрузка данных в дерево b +

Question

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

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

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

Есть идеи?

Answer 1

Из комментариев под вопросом я могу сказать, что вы обеспокоены тем, что последняя страница (или последние страницы, если рассматривать те, которые находятся выше в дереве), возможно, не достигнет минимального количества заполнения.

Как числотаких страниц ограничено log2 (n) (высота дерева). Я подозреваю, что теоретические гарантии производительности не затрагиваются.

В любом случае, ссылки, на которые вы ссылаетесь, не требуются для правильности.Их достаточно для гарантированных границ во время выполнения.Хотя они не необходимы для гарантированного времени выполнения (например: добавьте одну страницу с одной строкой в ​​конец b-дерева - вы все равно получите такое же гарантированное время выполнения).

ЕслиВы хотите знать, как работают настоящие b-деревья, возможно, вы захотите взглянуть на вашу любимую СУБД (как пользователь SQL Server, я знаю, что SQL Server успешно не обеспечивает гарантию полноты страницы на 50% без практического воздействия).Я думаю, вы обнаружите, что теоретические проблемы рассматриваются как не очень значимые.