Структуры данных и модели вычислений


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


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

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

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

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

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

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

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

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

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

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

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

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




Начало  Назад  Вперед



Книжный магазин