Модификация

Поиск.

Пусть v1 значение ключа искомой записи. Тогда в индексе необходимо найти запись (v2, b), такую что, v2£v1. И либо v2 – последняя запись в индексе, либо следующие записи имеют вид (v3, b), причем v1<v3. В этом случае говорят, v2 покрывает v1. Таким образом, находится блок, в котором может находиться запись со значение ключа v1. Согласно адресу в записи (v2, b) извлекается блок основного файла. Искомая запись находится либо в этом блоке, либо она вовсе отсутствует в файле.

Таким образом, в целом скорость поиска зависит от скорости поиска в индексном файле записи, покрывающей ключ. Существует три основных вида поиска:

1. Линейный поиск. При данном виде поиска, последовательно перебираются все блоки и все записи индекса. Даже при такой организации поиска в индексе получается выигрыш в скорости доступа по сравнению с остальными видами файлов. Так, если в главном файле содержится R записей в блоке, то по сравнению с организацией его в виде кучи, поиск будет происходить в R раз быстрее.

2. Двоичный поиск. Основой для применения этого метода служит никогда не нарушаемое упорядочивание записей не только в основном файле, но и в индексе.

Пусть В1, В2,…, Вm – блоки индексного файла. Первые записи в этих блоках (индекса) V1, V2, …, Vm. Необходимо найти запись с ключом V. Сначала извлекается блок B_m/2. Необходимо сравнить значение V_m/2 со значением V. Если V<V_m/2, то продолжается поиск, в блоках В1-В_m.2-1, если V³V_m/2, то поиск необходимо провести в блоках B_m/2…B_m. Процесс деления продолжается пока не останется один блок. Далее в этом блоке ищется запись, покрывающая V, с использованием линейного поиска. В результате потребуется Log₂M обращений к индексному файлу.

3. Интерполирующий поиск. В этом случае кроме упорядочивания записей в индексе важную роль играет знание статистики распределения значений ключей. При работе этого метода должна существовать функция f(V1, V2, V3). Эта функция возвращает в качестве результата блок, в котором может находиться запись со значением ключа равной V1, если известно, что V1 находится между значениями V2 и V3. Поиск продолжается пока не останется один блок, затем в нем перебором ищется покрывающая V1 запись. Потребуется 1+ Log₂Log₂M доступов к индексу.

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

Дата добавления: 2015-05-09