Эффективность индексированных файлов

Пусть блок главного файла максимально вмещает E записей. Тогда в худшем случае блок будет вмещать e равное (E+1)/2 записей. Эта ситуация складывается при делении блока при вставке новой записи. Аналогично если блок индекса максимально вмещает D, тогда в худшем случае он будет содержать d равное (D+1)/2 записей. Если в файле содержится n записей, то можно сделать следующие выводы об эффективности индексированных файлов.

При двоичном поиске в индексированном файле потребуется 2+Log₂(n/de) обращений к диску. Где n/de – максимальное количество блоков в индексе (логарифм из эффективности двоичного поиска). Еще два обращения для чтения и записи блока основного файла. При интерполирующем поиске потребуется 3+Log₂Log₂(n\de) обращений к диску.

 

Плотное индексирование

 

Индексирование, рассмотренное выше, называется разреженным индексированием. Существует другой вид индексирования широко распространенный в реальных СУБД – плотное индексирование. В этом случае индексные файлы содержат пары вида (v, p), где первый элемент – значение ключа, а второй – адрес записи в основном файле с этим ключом. Такой подход не требует обязательного упорядочивания записей по индексируемому полю, а так же не обязательна уникальность ключа. Поэтому подход плотного индекса применим для ускорения поиска по любым полям, позволяя построить несколько независимых индексов.

При организации таких файлов скорость доступа будет 2+время поиска в файле индекса.

 

B-деревья

При увеличении числа блоков, занятых индексом в разреженных индексированных файлах, снижается эффективность работы. Структура, называемая В–деревом, позволяет избежать такого снижения путем построения индекса для индекса, и при необходимости далее, пока верхний индекс не будет помещаться в один блок. Таким образом, получается иерархическая структура индексов - рисунок 10.

Рисунок 10 – В-дерево степени 5

 

В В-дереве узел может иметь много сыновей (на практике до тысячи). Количество сыновей (максимальное) определяет степень В-дерева.

Узел х, хранящий n[x] ключей, имеет n[x]+1 сыновей. Хранящиеся в х ключи служат границами, разделяющими всех потомков узла на n[x]+1 групп. За каждую группу отвечает один из сыновей х.

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

Операции на В-деревьях.

Поиск.

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

Пример.

Текущий узел=корень.

While текущий узел не лист

Begin

Путь=Путь + Текущий узел

Адрес = адрес из записи, покрывающей значение v.

Текущий узел=извлечь блок(адрес)

end;

Путь=Путь + Текущий узел

 

В результате текущий блок является блоком основного файла, поэтому искомая запись со значением v ищется в нем.

Модификация.

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

Если модифицируются не ключевые атрибуты, то выполняется операция поиска, после чего вносятся изменения в поля записи, и блок перезаписывается на диск.

Вставка.

Изначально необходимо найти блок В, в котором должна располагаться новая запись. Если В содержит меньше, чем 2е-1 записей, то запись размещается в блоке так, чтобы не нарушить сортировку. Очевидно, что новая запись не будет первой записью блока, кроме случая самого левого блока. Следовательно, нет необходимости изменять значения ключей в индексных блоках по иерархии.

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

Удаление.

При удалении необходимо найти блок В, в котором содержится запись v. Если после удаления в блоке осталось е или более записей, то после удаления найденной записи и сдвига всех остальных операция закончена.

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

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

 

Эффективность В-дерева.

 

Пусть главный файл содержит n записей, а e и d – параметры организации В–дерева. Тогда листьев в дереве будет не больше чем n/e, так как е – наименьшее число записей в одном блоке. Предков листьев будет n/de, предков предков листьев n/d²e, и так далее. Если путь от корня до листьев содержит i узлов, то для количества блоков последнего уровня будет ровняться n/d^i-1e. Так как известно, что в В–дереве только один блок является корнем, то следовательно n/d^i-1e равняется 1, из этого следует что, n равняется d^i-1e, и i равняется 1+Log_d(n/e), так как d и e по определению минимальны, то i меньше или равно 1+Log_d(n/e).

То есть, максимальное число обращений к диску при поиске будет 1+Log_d(n/e). При вставке данное значение увеличивается на 1 (для записи блока).

 

Задания на лабораторные работы

Задание 1. Организация файла в виде кучи

 

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

В программе должны быть реализованы следующие функции:

· добавление информации о студент;

· изменение информации о студенте;

· удаление информации о студенте;

· осуществление поиска информации о студенте.

Отношение студент должно содержать следующие атрибуты: номер зачетки (тип integer), фамилия (тип string(30)), имя (тип string(20)), отчество (тип string(30)), номер группы (тип integer).

Для организации хранения информации о записи в файле необходимо использовать тип Zap.

Type

Zap = record

Id_zachet, id_gr: integer;

Surname, Name: string (20);

Patronymic: string(30);

End;

Блок файла должен включать 5 записей.

Type

Block = record

Zap_block: array[1..5] of zap;

End;

Для хранения схемы отношения в файле должен использоваться нулевой блок.

Программа должна работать с любым файлом, организованным по данной схеме.

 

Контрольные вопросы

1. Что такое запись?

2. Какие дополнительные байты может содержать запись?

3. Что такое блок?

4. В чем особенности организации файлов в виде кучи?

5. Эффективность рабы с файлом, организованным в виде кучи.

Задание 2. Организация хешированного файла

 

Написать программу, которая работает с хешированным фалом хранящем информацию об отношении «студент».

В программе должны быть реализованы следующие функции:

· добавление информации о студент;

· изменение информации о студенте;

· удаление информации о студенте;

· осуществление поиска информации о студенте.

Отношение студент должно содержать следующие атрибуты: номер зачетки (тип integer), фамилия (тип string(30)), имя (тип string(20)), отчество (тип string(30)), номер группы (тип integer). Атрибут «номер зачетки» выступает в роли первичного ключа.

В качестве хеш-функции необходимо использовать остаток от деления первичного ключа на 4.

Для организации хранения информации записи в файле необходимо использовать тип Zap.

Type

Zap = record

Id_zachet, id_gr: integer;

Surname, Name: string (20);

Patronymic: string(30);

End;

Каждый блок – это запись из массива записей и указателя на следующий блок. Блок файла должен включать 5 записей.

Type

Block = record

Zap_block: array[1..5] of zap;

Nextb: integer;

End;

Для хранения схемы отношения в файле должен использоваться нулевой блок.

Информация о каталоге бакетов также должна размещаться в нулевом блоке.

Type

Block0 = record

Relation_scheme: string(255);

Catalog: array[0..4]of record nf, nl: integer;

End;

End;

Переменная nf – номер первого блока в бакете, переменная nl – номер последнего блока в бакете.

В пределах каждого бакета, блоки записываются как в файле в виде кучи.

Программа должна работать с любым файлом, организованным по данной схеме.

 

Контрольные вопросы

1. Что такое бакет?

2. Что такое каталог бакетов?

3. Что такое хеш-функция?

4. В чем особенности организации хешированных файлов?

5. Причины снижения эффективности хешированных файлов.

6. Что такое динамическое хеширование?

7. Эффективность работы хешированных файлов.

 

Задание 3. Организация индексного файла

 

Написать программу, которая организует хранение информации об отношении «студент» в виде разреженного индексируемого файла.

В программе должны быть реализованы следующие функции:

· добавление информации о студент;

· изменение информации о студенте;

· удаление информации о студенте;

· осуществление поиска информации о студенте.

Отношение студент должно содержать следующие атрибуты: номер зачетки (тип integer), фамилия (тип string(30)), имя (тип string(20)), отчество (тип string(30)), номер группы (тип integer). Атрибут «номер зачетки» выступает в роли первичного ключа.

Информация о студентах храниться в основном файле, а индексы хранятся в файле индексов (отдельно).

Для организации хранения записей основного файла необходимо использовать тип Zap.

Type

Zap = record

Id_zachet, id_gr: integer;

Surname, Name: string (20);

Patronymic: string(30);

End;

Каждый блок – это запись из массива записей и указателя на следующий блок. Блок файла содержит 5 записей.

Type

Block = record

Zap_block: array[1..5] of zap;

End;

Для хранения схемы отношения в файле используется нулевой блок.

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

Программа должна работать с любым файлом, организованным по данной схеме.

 

Контрольные вопросы

1. В чем суть организации индексированных файлов?

2. В чем суть процесса инициализации?

3. Чем плотное индексирование отличается от разреженного?

4. Как осуществляется индексация по нескольким полям?

5. Перечислите основные действия, выполняемые при операции вставки в индексный файл.

6. Перечислите основные действия, выполняемые при операции удаления из индексного файла.

7. Какие алгоритмы поиска в индексном фале Вы знаете?

 

Задание 4. Организация файла в виде В-дерева

Написать программу, которая организует хранение информации об отношении «студент» в файле организованном в виде В-дерева.

В программе должны быть реализованы следующие функции:

· добавление информации о студент;

· изменение информации о студенте;

· удаление информации о студенте;

· осуществление поиска информации о студенте.

Отношение студент должно содержать следующие атрибуты: номер зачетки (тип integer), фамилия (тип string(30)), имя (тип string(20)), отчество (тип string(30)), номер группы (тип integer). Атрибут «номер зачетки» выступает в роли первичного ключа.

Информация о студентах храниться в основном файле, а индексы хранятся в файле индексов (отдельно).

Для организации хранения информации главного файла записи в файле необходимо использовать тип Zap.

Type

Zap = record

Id_zachet, id_gr: integer;

Surname, Name: string (20);

Patronymic: string(30);

End;

Каждый блок – это запись из массива записей и указателя на следующий блок. Блок файла должен содержать 5 записей.

Type

Block = record

Zap_block: array[1..5] of zap;

End;

Для хранения схемы отношения в файле используется нулевой блок.

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

Программа должна работать с любым файлом, организованным по данной схеме.

 

Контрольные вопросы

8. В чем суть организации файла в виде В-дерева?

9. Перечислите основные действия, выполняемые при операции вставки в файл организованный в виде В-дерева.

10. Перечислите основные действия, выполняемые при операции удаления из файла организованного в виде В-дерева.

11. Перечислите основные действия, выполняемые при операции поиска в файле организованном в виде В-дерева.

12. какова эффективность организации файлов в виде В-дерева.

Рекомендуемая литература

1. Дейт К. Дж. Введение в системы баз данных — 8-е изд. — М.: «Вильямс», 2006. — С. 1328. — ISBN 0-321-19784-4

2. Коннолли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика — 3-е изд. — М.: «Вильямс», 2003. — С. 1436. — ISBN 0-201-70857-4

3. Хомоненко А.Д. Базы данных. Учебник для вузов / А.Д. Хомоненко, В.М. Цыганков, М.Г. Мальцев. – М.: «Бином», 2006

4. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. — М.: Финансы и статистика, 1989. — 351 с.

 

⇐ Предыдущая12345

Поделиться: