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

Пусть главный файл содержит 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 (для записи блока).

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

2.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.2 Задание 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. Эффективность работы хешированных файлов.