Файловые структуры организации базы данных.

В каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые применяются практически во всех СУБД.

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

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

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

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

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

Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа.

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

Каждая файловая система — система управления файлами — поддерживает некоторую иерархическую файловую структуру, включающую чаще всего ограниченное число уровней иерархии в представлении внешней памяти (рис. 9).

Для каждого файла в системе хранится следующая информация:

· имя файла;

· тип файла (например, расширение или другие характеристики);

· размер записи;

· число занятых физических блоков; - базовый начальный адрес;

· ссылка на сегмент расширения;

· способ доступа (код защиты).

Для файлов с постоянной длиной записи адрес размещения записи с номером К может быть вычислен по формуле

ВА+(К – 1) • LZ + 1, где ВА – базовый адрес; LZ – длина записи.

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

На устройствах последовательного доступа могут быть организованы файлы только последовательного доступа.

Они могут быть организованы двумя способами:

1. конец записи отмечается специальным маркером;

2. в начале каждой записи записывается ее длина.

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

Суть методов хеширования состоит в том, что выбираются значения ключа (или некоторые его характеристики), которые используются для начала поиска, т.е. вычисляется так называемая хеш-функция h(k), где k – значение ключевого поля. В этом случае число шагов поиска значительно уменьшается. Однако при таком подходе возможны ситуации, когда нескольким разным ключам может соответствовать одно значение хеш-функции, т.е. один адрес. Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хеш-функции, называются синонимами.

Поэтому при использовании хеширования как метода доступа необходимо принять два независимых решения:

· выбрать хеш-функцию;

· выбрать метод разрешения коллизий.

Существует множество различных стратегий разрешения коллизий, наиболее распространенными из которых являются:

· разрешение коллизии с помощью области переполнения;

· разрешение коллизии методом свободного замещения.