Эффективность организации файлов в виде кучи

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

Удаление.

Вставка.

Поиск.

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

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

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

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

Пусть в файле существует N записей. В каждый блок может поместиться R записей. То есть в файле должно быть N/R блоков. Время выполнения операций измеряем количеством блоков, которые должны быть запрошены с диска или записаны на него.

При поиске записи в файле возможны два варианта:

1) N/R блоков придется просмотреть, если запись отсутствует в файле или, если ключевое поле, не является уникальным;

2) в противном случае потребуется считать N/2R блоков.

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

Удаление требует найти запись, то есть выполнить операцию поиска, а затем выполнить операцию записи блока, в котором была найдена запись. Таким образом, для удаления записи потребуется в среднем ((N/2R)+1) доступов, если запись существует в файле. Если ее нет в файле, то выполниться N/R доступов. Для дальнейшего использования освободившегося пространства последняя запись последнего блока может быть перемещена на место удаленной записи. Это немного замедлит процесс удаления, но уменьшит количество блоков, что в дальнейшем ускорит выполнение всех операций.

Время выполнения модификации аналогично времени выполнения операции удаления.

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

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