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