B+ дерево, Построение, Свойства: - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Рис. 9

Пример B+ дерева, связывающего ключи 1-7 с данными d1-d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей.

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

Построение

При построении B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k до 2k, где k -- степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать "цепную реакцию" деления узлов, заканчивающуюся в корне.

Свойства:
    - В B+ дереве легко реализуется независимость программы от структуры информационной записи. - Поиск обязательно заканчивается в листе. - Удаление ключа имеет преимущество -- удаление всегда происходит из листа. - Другие операции выполняются аналогично B-деревьям. - B+ деревья требуют больше памяти для представления чем B-деревья. - B+ деревья имеют возможность последовательного доступа к ключам.

Похожие статьи




B+ дерево, Построение, Свойства: - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Предыдущая | Следующая