Модель данных - это некоторая абстракция, которая, будучи приложима к конкретным данным, позволяет пользователям и разработчикам трактовать их уже как информацию, то есть сведения, содержащие не только данные, но и взаимосвязь между ними.
Физическая модель данных оперирует
категориями, касающимися организации внешней памяти и структур хранения,
используемых в данной операционной среде. В настоящий момент в качестве
физических моделей используются различные методы размещения данных,
основанные на файловых структурах: это организация файлов прямого и
последовательного доступа, индексных файлов и инвертированных файлов,
файлов, использующих различные методы хеширования, взаимосвязанных
файлов. Физические модели данных, основанные на страничной организации,
являются наиболее перспективными.
В соответствии с методам
управления доступом различают устройства внешней памяти с произвольной
адресацией (магнитные и оптические диски) и устройства с
последовательной адресацией (магнитофоны). Файлы с постоянной длиной
записи расположенные на устройствах прямого доступа является файлами
прямого доступа.
Для файлов с постоянной длиной записи адрес размещения записи с N к вычисляется т.о.
ВА+(К-1)+LZ+1, где ВА – базовый адрес, LZ – длина записи.
Файлы с переменной длиной записи всегда являются файлами непоследовательного доступа. Они организовываются двумя способами:
1. конец записи отличается специальным маркером
2. В начале каждой записи записывается ее длина.
В БД доступ по N записи неэффективный, как правило, мы знаем значение ключа, но не знаем №записи, соответствующий этому ключу.
Для файлов прямого доступа иногда можно построить функцию, которая по значению ключа однозначно вычислила адрес (№записи файла).
NZ=F(K), К – значение ключа.
F() должна быть линейной, чтобы обеспечивать однозначное соответствие.
Если
значения ключей разбросаны по нескольким диапазонам, то построить
взаимнооднозначную функцию не удается. В этом случае используют методы
хеширования (рандомизации). Создаются специальные хэш-функции h(К), К –
значение ключа.
Однако несколько разным ключам могут соответствовать одно значение h(K), т.е. один адрес, - возникают коллизии.
При использовании хеширования необходимо:
- выбрать хеш-функцию,
- выбрать метод разрешения коллизий.
а) использование области переполнения
б) использование области свободного замещения
а) основная область
б) для любой записи добавляется 2 указателя: указатель на предыдущую запись и указатель на следующую
