Особенности работы с информацией, размещаемой на диске

Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).

Диск рассматривается как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом , выполняется специальная операция-(чтение с диска). После внесения изменений в объект выполняется операция-(запись на диск).

Время работы программы в основном определяется количеством этих операций, так что имеет смысл читать/записывать как можно больше информации за один раз и сделать так, чтобы узел Б-дерева заполнял полностью один сектор диска. Таким образом, степень ветвления (число детей узла) определяется размером сектора.

Типичная степень ветвления Б-деревьев находится между и в зависимости от размера элемента. Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. Например, Б-дерево степени и высоты может хранить более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску при поиске нужного ключа.

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

Определение Б-дерева. Б-деревом называют корневое дерево, устроенное следующим образом. Каждый узел содержит следующие поля:

— количество ключей, хранящихся в узле ;
,,,— сами ключи в неубывающем порядке;
— булевское значение, истинное, когда узел является листом.

Если— внутренний узел, то он содержит указатели на его детей в количестве.

У листьев детей нет, и эти поля для них не определены.
Все листья находятся на одной и той же глубине, равной высоте дерева.
Возможное число ключей, хранящихся в одном узле, определяется параметром, которое называется минимальной степенью Б-дерева.
Для каждого некорневого узлавыполняется неравенство. Таким образом, число детей у любого внутреннего узла (кроме корня) находится в пределах от до .
Если дерево не пусто, то в корне должен храниться хотя бы один ключ. Узел, хранящий ровноключей, будет называться полным.

Ключислужат границами, разделяющими значения ключей в поддеревьях. Точнее,

ссылается на поддерево, ключи в котором меньше, чем ;
при ссылается на поддерево, ключи в котором находятся в пределах от до ;
ссылается на поддерево, ключи в котором больше, чем.

В случае, когда, у каждого внутреннего узла,или потомка, получается так называемое---дерево. Для эффективной работы с диском на практике выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.

Теорема 1.

Для всякого Б-дерева высоты, хранящегоключей, выполнено неравенство, где— минимальная степень узла.

Доказательство.

Число узлов в дереве высоты будет наименьшим, если степень каждого узла минимальна, то есть у корня потомка, а у внутренних узлов — по потомков. Следовательно узла будет на глубинеузлов — на глубинеузлов — на глубине и т.д. на глубине будетузлов. При этом в корне хранится один ключ, а во всех остальных узлах поключей. Таким образом, получаем неравенство

откуда следует утверждение теоремы.

Как и для красно-черных деревьев, высота Б-дерева с узлами есть, но основание логарифма для Б-деревьев гораздо больше, что примерно враз сокращает количество обращений к диску.

Основные операции с Б-деревьями. Корень Б-дерева размещают в оперативной памяти, при этом чтения с диска для корня никогда не требуется; однако всякий раз, когда изменяется корень, его сохраняют на диске. Все узлы, передаваемые как параметры, уже считаны с диска. Все процедуры обрабатывают дерево за один проход от корня к листьям.

Поиск в Б-дереве похож на поиск в двоичном дереве. Разница в том, что в каждом узле выбирается один вариант из , а не из двух. При поиске просматриваются узлы дерева от корня к листу. Поэтому число обращений к диску есть , где— высота дерева, а — количество ключей. Так как, то время вычислений равно.

Создание пустого Б-дереваосуществляется с помощью процедуры, которая находит место на диске для нового узла и размещает его. Это можно реализовать за время и не использовать операцию чтения с диска.

Добавление элемента в Б-деревоосуществляется с использованием процедуры разбиения полного (сключами) узла на два узла, имеющие поэлементов в каждом. При этом ключ-медианаотправляется к родителю узла и становится разделителем двух полученных узлов. Это возможно, если узел неполон. Если — корень, процедура работает аналогично. В этом случае высота дерева увеличивается на единицу.

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

Удаление элемента из Б-дерева происходит аналогично добавлению, хотя немного сложнее. Читателю предоставляется возможность разработать процедуру удаления, которая требуетобращений к диску для Б-дерева высоты , при этом вся процедура требуетвремени.

В заключение заметим, что сбалансированные деревья и Б-деревья обсуждаются в книгах Д.Кнута, А.Ахо, Дж.Хопкрофта и Дж.Ульмана. Подробный обзор Б-деревьев дан в книге Т.Кормена и др. Л.Гибас и Р.Седжвик рассмотрели связи между разными видами сбалансированных деревьев, включая красно-черные и 2-3-4-деревья.

В 1970 г. Дж. Хопкрофт предложил понятие 2-3-деревьев, которые явились предшественниками Б-деревьев и 2-3-4-деревьев. В этих деревьях каждая внутренняя вершина имеет 2 или 3 детей. Б-деревья были введены Д.Байером и Е.Мак-Крейтом в 1972 г.

Содержание Назад