1.2 Эффективность организации блоков в файле

Основная операция внешней памяти – доступ к блоку, т.е. передача блока из внешней памяти в оперативную и наоборот. Важно отметить, что в большинстве современных систем передача данных, при которой осуществляется операции считывания/записи данных из/во вторичной памяти, требуется обычно столько же или более времени, чем поиск требуемых данных в блоке, который уже находится в оперативной памяти. К тому же во всех системах, кроме некоторых гипотетических или экспериментальных, данные необходимо иметь в основной памяти прежде, чем они могут быть использованы. Таким образом, когда идет речь о быстродействии различных алгоритмов доступа к данным, следует подсчитывать число блоков, которые должны быть прочитаны в основную память или записаны из нее. Это число и будет представлять оценку быстродействия алгоритма.

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

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

1.3 Организация файлов в виде кучи

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

Рисунок 4 – Схема организации файла в виде кучи

Поиск.

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

Вставка.

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

Удаление.

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

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

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

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

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

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

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

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

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

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

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

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