Есть ли какой-нибудь алгоритм массовой загрузки в B-Tree?

На самом деле ответ — да.

Основное различие между B + -деревьями и обычными B-деревьями состоит в том, что значения фактически сохраняются в листьях для первого, а в последующем вы найдете значения в каждом узле. Следовательно, B + -деревья позволяют хранить данные практически непрерывно, каждый лист содержит непрерывный срез всех отсортированных данных. Это не может быть правдой для B-деревьев: внутренний узел будет содержать несколько элементов, но они не будут смежными по отношению к. весь отсортированный набор данных.

Это свойство важно для массовой загрузки: этот процесс работает с уже отсортированным набором данных, разрезая его на массивы, которые образуют листья дерева B +. Таким образом, для B-дерева похоже, что оно не может работать.

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

Давай позвоним o (порядок) минимальное число дочерних элементов в узле (это соответствует исходному определению порядка B-дерева). Мы считаем, что корневой узел находится на самой высокой стадии дерева, а листья — на самой низкой (стадия 0). Для хорошо сбалансированного дерева все листья действительно будут на одной стадии.

Стадия k элементов древовидных групп, которые расположены по меньшей мере на o элементы на этапе к-1. После начальной сортировки мы должны извлечь элементы из отсортированного массива, который составляет стадию 0, и сгруппировать их в другой массив для построения стадии 1, затем сделать это снова с этим массивом в новый массив для стадии 2 и повторить процесс пока не станет меньше o элементы в новейшем массиве, который будет корневой стадией. С этого момента возможно построить дерево непосредственно из сценического набора:

• разделить каждую стадию на массивы o элементы,
• построить индексные массивы для связи узлов с подузлами
• построить каждый узел как пару соответствующего индексного массива * массив значений

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

В целом работа, необходимая для массовой загрузки B-дерева, более утомительна, чем для B + -дерева, но это возможно.