Представление файлов В-деревьями

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Дальневосточный федеральный университет»

ШКОЛА ЕСТЕСТВЕННЫХ НАУК

Кафедра прикладной математики, механики, управления и программного обеспечения

РЕФЕРАТ

по дисциплине «Структуры и алгоритмы компьютерной обработки данных»

Направление «МОАИС»

на тему «Представление файлов В-деревьями»

Выполнил студент гр. А.А. Андреев

Проверил доцент кафедры ПММУПО

С.Н. Остроухова

г. Владивосток

2013 г.

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

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

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

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

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

- Каждая вершина может содержать не более 2n ключей.

- Каждая вершина за исключением, может быть, корневой содержит не менее n ключей (корневая вершина, если она не является листом, содержит не менее двух потомков).

- Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m - количество ключей в вершине.

- Все листовые вершины располагаются на одном уровне.

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

В В-дереве не должно быть блоков, заполненных меньше, чем наполовину. Значение ключа первой записи индексного блока пропускается.

Каждая нелистовая вершина Б-дерева имеет вид:

файл реорганизация дерево ключ

<p₀, k₁, p₁, k₂, p₂,..., p_m-1, k_m, p_m>

Здесь p_i представляет собой указатель на i -го потомка, а k_i - значение ключа поиска (указатели на записи основного файла ради простоты не указаны). Для любого i в диапазоне [1, m-1] все ключи, расположенные в поддереве, на которое указывает указатель p_i, находятся в диапазоне [k_i, k_i+1]. Соответственно, все ключи поддерева p₀ будут меньше k₁, а все ключи поддерева p_m- больше k_m.

Поиск некоторого k ключа в Б-дереве происходит следующим образом. Начиная с корневой вершины выполняется следующая последовательность действий:

Просматриваются ключи k₁, k₂,, k_m, Если искомый ключ k найден, то по соответствующему указателю извлекается запись основного файла. Для поиска ключа в вершине может использоваться либо простой последовательный поиск, если m невелико, или двоичный поиск, для достаточно больших m.

Если k_i< k< k_i+1 для i в диапазоне [1, m-1], то поиск продолжается на странице p_i.

Если k< k₁, то поиск продолжается на странице p₀.

Если k>k_m, то поиск продолжается на странице p_m.

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

Если найденная вершина содержит менее 2*n ключей, то ключ просто добавляется к данной вершине.

Если страница уже заполнена, то она разделяется на две. При этом 2*n из 2*n+1 ключей пополам (с учетом порядка) распределяются между получившимися вершинами. Центральный ключ (по значению) помещается в родительскую вершину. При этом может произойти ее разделение.

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

При удалении из Б-дерева происходит балансировка и слияние страниц. Процедуру удаления можно описать следующим образом:

Если удаляемый ключ находится на листовой вершине, то он просто удаляется.

Если удаляемый ключ находится на промежуточной вершине, то он заменяется на смежный элемент, который расположен на листовой вершине.

Если в результате удаления количество ключей вершины стало меньше n, то выполняется балансировка - ключи поровну распределяются между данной, родительской и смежной вершинами.

Если количество ключей на смежной вершине равно n, то балансировка невозможна, но можно слить данную и смежную вершины, заняв один ключ из родительской. Это может привести в свою очередь к балансировке или слиянию на следующем уровне.

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

Размещено на Allbest.ru