Организация файла БД в виде кучи. Эффективность таких файлов

База данных (БД) – это совместно используемый набор логически связанных данных и описание этих данных, предназначенное для удовлетворения информационных потребностей организации. Можно сказать, что база хранится на диске как набор записей различного формата, т.е. в виде файлов. В данном случае под файлом понимают набор записей одинакового формата, т.е. файл аналогичен отношению. Для наиболее быстрой обработки данных отношение при хранении разбивается на фрагменты. Такие фрагменты наз-ся блоки или страницы. Блоки м.б. по-разному организованы внутри файла, напр., м.б. файлы, организованные в виде кучи, хешированные и последовательные файлы.

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

Поиск в таких файлах осущ-ся путем перебора всех записей из всех блоков файла, т.е. эф-ть поиска в отношении r равна Br, где Br – число блоков в отношении r.

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

Модификация эл-та осущ-ся в 3 этапа: ищем данный эл-т в файле; изменяем его; перезаписываем блок. Удаление эл-та осущ-ся в 2 этапа: поиск удаляемого элемента; помечаем на удаление. Часто для последующего использования освободившегося пространства, последняя запись последнего блока перемещается на место удаленной записи. Это замедляет процесс удаления, но ускоряет другие операции.

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