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