Структуры данных и модели вычислений
Особенности работы с информацией, размещаемой на диске
Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).
Диск рассматривается как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом , выполняется специальная операция-(чтение с диска). После внесения изменений в объект выполняется операция-(запись на диск).
Время работы программы в основном определяется количеством этих операций, так что имеет смысл читать/записывать как можно больше информации за один раз и сделать так, чтобы узел Б-дерева заполнял полностью один сектор диска. Таким образом, степень ветвления (число детей узла) определяется размером сектора.
Типичная степень ветвления Б-деревьев находится между и в зависимости от размера элемента. Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. Например, Б-дерево степени и высоты может хранить более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску при поиске нужного ключа.
Считаем, что прикладная информация, связанная с ключом, хранится в том же узле дерева. На практике это не всегда удобно, и в реальном алгоритме узел может содержать лишь ссылку на сектор, где она хранится.
Определение Б-дерева. Б-деревом называют корневое дерево, устроенное следующим образом. Каждый узел содержит следующие поля:
- — количество ключей, хранящихся в узле ;
- ,,,— сами ключи в неубывающем порядке;
- — булевское значение, истинное, когда узел является листом.
Если— внутренний узел, то он содержит указатели на его детей в количестве.
- У листьев детей нет, и эти поля для них не определены.
- Все листья находятся на одной и той же глубине, равной высоте дерева.
- Возможное число ключей, хранящихся в одном узле, определяется параметром, которое называется минимальной степенью Б-дерева.
- Для каждого некорневого узлавыполняется неравенство. Таким образом, число детей у любого внутреннего узла (кроме корня) находится в пределах от до .
- Если дерево не пусто, то в корне должен храниться хотя бы один ключ. Узел, хранящий ровноключей, будет называться полным.
Ключислужат границами, разделяющими значения ключей в поддеревьях. Точнее,
- ссылается на поддерево, ключи в котором меньше, чем ;
- при ссылается на поддерево, ключи в котором находятся в пределах от до ;
- ссылается на поддерево, ключи в котором больше, чем.
В случае, когда, у каждого внутреннего узла,или потомка, получается так называемое---дерево. Для эффективной работы с диском на практике выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.
