Главная » Java, Структуры данных и алгоритмы » В-деревья

0

Наиболее известной версией структуры данных (я,6)-дерева для содержания словаря во внешней памяти является В-дерево (см. рис. 9.33). В-дерево порядка d — это (я,6)-дерево, в котором а = \d/2], a b = d. Но поскольку рассматриваются стандартные словарные методы запроса и обновления для (а,6)-дерева, ограничимся изучением 1/О-сложности В-деревьев.

Рис. 9.33. В-дерево 6-го порядка

Главным свойством В-дерева является возможность выбора d таким, чтобы d ссылок на дочерние элементы и d-\ ключей, хранящихся в узле, могли целиком войти в дисковый блок (при условии, что dесть 0(B). Возможность выбора также следует из того, что при анализе операций поиска и обновления (я,6)-дерева а и b составляют 0(5). Таким образом,/(6) и g(b) есть 0(1), поскольку всякий раз при операции поиска или обновления выполняется только одна дисковая передача.

Как показано выше, каждая операция поиска и обновления требует обращения максимум к 0(1) узлу для каждого уровня дерева. Следовательно, каждая словарная операция поиска или обновления в В-дереве

потребует всего 0(logp/2-| п\ то есть 0(log п / log В) дисковых передач. Например, операция ввода опускается вдоль В-дерева в поисках узла, в который требуется ввести новый объект. Если в результате добавления узел переполняется (количество дочерних элементов доходит до d + 1), то этот узел делится на два узла, имеющих L(d + l)/2j и \(d + 1)/2] дочерних элементов соответственно. Этот процесс повторяется на следующем уровне и будет продолжаться на максимум 0(log# п) уровнях.

Аналогично, если в результате удаления потеряна значимость (количество дочерних элементов уменьшается до \d/2\- 1), то перемещаем ссылки из соседнего узла, имеющего минимум \d/2 \ + 1 дочерних элемента, или выполняем слияние э^ого узла с соседним (и повторяем эти операции в их родительском узле). Как и для операции ввода, это может продолжаться максимум на 0(1 ogsn) уровнях. Требование наличия в каждом составном узле как минимум\d/2\ дочерних элементов предполагает, что каждый дисковый блок, используемый для поддержки В-дерева, хотя бы наполовину заполнен. Из этого следует

- Утверждение 9.9. В-дерево с п объектами имеет 1/0-сложность 0(logв п) для операций поиска и обновления и использует 0(п/В) блоков, где В — размер одного блока.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии