Физическое представление данных, страница 8

В случае индексного файла в нем будет содержаться m2/c2 записей. Если в блоке индексного файла содержится Син– записей, то индексный файл будет содержать

m2/c2* Син– блоков

А количество доступов в индексном файле нахождение указателя записи с заданным ключом V2 будет равно

Кg = ½ * m2/ c2* Син

Для нахождения записи с ключом V2 нужен еще один доступ

Кg = 1 + (½ * m2/ c2* Син)

И один доступ для размещения модифицированной записи , т.е.

Кg = 2+ (½ * m2/ c2* Син)

Пример:

m2 = 10⁵ записей

c2 = 10

Сгл = 100

Для поиска только в главком файле не обходимо

Кg = 10⁵ /2 = 5*10⁴ – доступность

Для поиска в индексном файле не обходимо

Кg = (10⁵ /2*10³ ) +1 = 5*10² – доступность

т.е. разница на два порядка.

Двоичный поиск (вторая стратегия поиска)

Стратегия второго поиска связана с методом деления сортированного адресного пространства пополам и определение, в какой половине находиться искомое значение ключа.

Пусть в индексе имеется 8 записей и значение их ключем совпадает с номерами записей т.е.

Нам не обходимо найти запись с ключом равным 3.

1 шаг – дает нам значение ключа равное 4

2 шаг – дает нам значение ключа равное 2

3 шаг – дает нам значение ключа равное 3.

т.е. для поиска требуемой записи мы потратим 3 шага.

Обозна чим через n – число записей, и Km – количество шагов для поиска, тога Km = log2 n

Если 16>n>8,то

Km = log2 n + 1

Перейдем теперь к блокам индекса нашего примера.

Пусть нам необходимо найти запись с ключами то при V2 =45 – 4 блока, то при 2-й стратегии мы имеем:

1 шаг – Загружается блок БI3

2 шаг – Загружается блок БI2

3 шаг – Загружается блок БI1

Здесь есть ссылка на адрес записи с ключом 45 затем, Загружается блок с записую, имеющий ключ 45.

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

Таким образом

Kg = log2 n + 1 + 1   +1

log2 n + 1 – поиск блок индексного файла с ключом V2

1 – загрузка блока в ОЗУ с записью, имеющей ключ V2 = 45, модификация записи

1 – загрузка блока с модифицированной записью из ОЗУ во внешнюю память

Здесь nин – количество блоков индексного файла

Для примера имеем:

nин = mгл/cгл* Син = 10³

и Kg = log210³  + 3 ≈ 13 доступов

т.е. количество доступов уменьшилось по сравнению с поиском в основном файле на 4 порядка.

Файлы с плотным индексом

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

Файл IFD Основная область Файл F

К – значение ключа

Р – указатель

А1, А2,..,Ап – атрибут записи

Для файла с плотным индексом количество блоков индексного файла

nин = mгл/cгл

т.к. индексный файл содержит ключи всех тех записей Kgин = (плотные индексы) и Kgин = (неплотные индексы)

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