Операции над индексированными файлами

Инициализация. Пусть имеются записи со следующими значениями ключей: 16, 2, 5, 37, 79, 56, 4, 25, 54, 68

Процесс состоит из трех этапов:

1. Записи в исходном файле сортируются, после чего распределяются по блокам. Обычно файлы БД имеют тенденцию к увеличению, поэтому при инициализации блоки оставляют незаполненными на 20%. Таким образом, основной файл имеет вид упорядоченных записей, размещенных в упорядоченные блоки.

 

Пример,

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

 

Рисунок 8 – Организация основного файла

2. Создание индексного файла. При этом берутся первые записи каждого блока и составляются пары (< значение ключа первой записи блока>, < адрес блока> ). Исключение – первый блок. Для него в индексный файл записывается пара (-¥, адрес первого блока). Это необходимо, чтобы не описывать отдельные алгоритмы для работы со значениями ключа, меньшими, чем все существующие в файле на данный момент. Схема организации индексного файла представлена на рисунке 9.

 

 

 

Рисунок 9 – Организация индексного файла

 

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

Поиск.

Пусть 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 доступов к индексу.

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

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

Вставка.

Для вставки записи с ключом V1 в индексированный файл выполняется операция поиска блока B_i, в который должна быть помещена новая запись. После чего, необходимо определить позицию записи в нутрии найденного блока. Это выражается в сохранении сортировки после выполнения операции вставки. Поэтому все записи блока, имеющие ключи больше V1 сдвигаются вправо. При этом освобождается место под V1. Если в блоке B_i нет свободного места, то необходимо проверить блок B_i+1. Найти этот блок можно, используя запись в индексном файле (она следует за записью, покрывающую v1 ).

Если в B_i+1 блоке есть свободное место, то последняя запись блока B_i переносится в качестве первой в блок B_i+1, после чего в обоих блоках записи сдвигаются вправо, и запись V1 помещается в требуемую позицию в блоке B_i. Также в этом случае необходимо произвести изменение в блоке индексного файла, так как изменилось значение ключа первой записи блока B_{i+1 .}

Если в блоке B_i+1 много свободного места, то все записи (вместе с новой) двух блоков, делятся пополам и размещаются в них поровну. При этом также необходимо перезаписать оба блока и внести изменения в файл индекса.

Если блок B_i+1 заполнен, или не существует (то есть B_i – последний), то аналогичную последовательность действий производят с блоком B_i-1.

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

При организации вставки в индексированный файл можно принять единую стратегию, когда при заполнении блока i, не проверяется ни i+1, ни i-1 блоки, а сразу захватывается новый блок. Это упрощает и несколько ускоряет процедуру вставки. Однако такая стратегия увеличивает общее число блоков и нарушает их порядок.

Удаление.

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

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: