В-деревья
В-дерево - это структура, очень широко применяемая для поиска данных на внешнем носителе. Ее используют практически все существующие системы управления базами данных.
В-деревом порядка m называется дерево, обладающее следующими свойствами:
- каждый узел имеет не более m сыновей
- каждый узел имеет не менее m/2 сыновей
- корень, если он не лист, имеет не менее двух сыновей.
- все листья расположены на одном уровне
- узел, имеющий n сыновей, содержит n-1 ключей. Ключи расположены в узле в возрастающем порядке.
Рис.47 В-дерево
На рис 47. изображено В-дерево порядка 5 . Связи как бы вставлены между ключами так, что указатель pi указывает на поддерево с ключами К, такими, что Ki-1 < K < Ki . Узел, содержащий n ключей и n+1 указателей можно представить как на рис. 48.
Рис.48 Узел В-дерева
Для В-дерева существует обобщение обратного обхода: сначала проходим поддерево, исходящее из P0, затем ключ К1, разделяющий поддеревья, исходящие из Р0 и Р1, затем поддерево, исходящее из Р1, и так далее. Для дерева на рис. 47 обратный обход дает последовательность:
19 26 35 38 39 41 44 48 62 78 88 99.
Таким образом, обратный обход В-дерева дает сортированную последовательность. Рассмотрим операции поиска, вставки и удаления.
Поиск
Начиная с корня, ищем ключ К среди ключей узла. Если поиск удачен, то операция завершается. Если же поиск неудачен, и нужный ключ имеет значение между Ki и Ki+1, спускаемся вниз по связи Pi и повторяем процесс. В конце концов, алгоритм либо найдет ключ, либо выйдет на пустую связь, что означает, что искомого ключа в дереве нет.
Дата добавления: 2014-12-02; просмотров: 918;