Удаление. Для вставки записи с ключом V1 в индексированный файл выполняется операция поиска блока Bi, в который должна быть помещена новая запись

Вставка.

Для вставки записи с ключом 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 блоки, а сразу захватывается новый блок. Это упрощает и несколько ускоряет процедуру вставки. Однако такая стратегия увеличивает общее число блоков и нарушает их порядок.

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

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