Записи к ключам K1 ÷ Ks, поступают в процессор, где записан алгоритм хеширований. После вычисления хеш – функции для ключа K1 , запись с ключом K1 ,размещается в основной области памяти.
Запись с ключом K2 имеет значение хеш – функции одинаковое с записью K1 . В этом случае происходит обращение к адресу А2 и запись с ключом K2 размещается в области переполнения и т.д.
6.4. Методы организации и обработки файлов.
Записи базы данных хранятся во внешней памяти (диски, дискеты, ленты) а их обработка осуществляется в оперативной памяти ЭВМ.
Между ОЗУ и внешней памятью обмен осуществляется блоками или страницами.
Размер страницы зависит от конкретной реализации системы, но обычно это число байт кратное 28
128 <- 256 байт -> 512
Обычно блоки заполняются записями не полностью. Причем выделяется основная область и область переполнения.
Основная память Область переполнения
В общем случае предполагаем, что каждый файл имеет фиксированный формат записи. Поля в каждой записи располагаются в одном и том же порядке и для каждого из них предусмотрено соответствующее число байтов, которое устанавливается при генерации или регенерации базы данных. Каждому полю устанавливается тип данных, который позволяет интерпретировать его биты. При этих предположениях мы можем однозначно декодировать записи.
Над файлом требуется выполнять следующие типичные операции:
1. включить запись;
2. удалить запись;
3. модифицировать запись;
4. найти запись с конкретным значением поля или с некоторой комбинацией значений полей.
Введем скоростную характеристику обработки файла базы данных.
Выделим основные элементы вычислительной системы используемые при обработке данных:
ОЗУ
– и внешняя память
Назовем передачу блока данных из ОЗУ во внешнюю память или наоборот. Поиск записи по ключу осуществляется с использованием блока информации, находящегося в ОЗУ.
Поэтому основной операцией или основным критерием того или иного метода организации файлов данных является количество доступов к блоку.
6.4.1. Хешированные файлы
Рассмотрим логическую структуру файла, имеющего имя R1.
А11 – атрибут, который является ключом записи – определенности причем, что его размер 5 байт.
Для вычисления хеш – функции используется метод деления.
В методе деления требуется выполнить участок памяти, имеющий непрерывную адресацию, т.е. адрес за адресом.
Если размер записи в файле R1 равен 5210 байтами, а мы предполагаем, что в файле будет 105 записей, то мы должны зарезервировать 50 мб памяти. В этот участок мы и будем размещать записи нашего файла.
Очевидно, что этот путь создания файла очень неэкономичен. Решение может быть реализовано с помощью следующей структуры:
|
Записи с ключами V1÷Vm , поступают в процессор, где вычисляется хеш – функция записи i – h(Vi) .
В области памяти А размещается только ключ записи Vi. Его размер будет 5 * 105 = 50 кбайт.
В области памяти В размещается сама запись. Для размещения коллизионных ситуаций используется метод цепочек.
Оценка скоростных характеристик хешированного файла
Определим количество доступов, необходимых для поиска записи с заданным ключом V в хешированном файле каждого из операций поиска включения, модификации и удаления требует доступа к внешней памяти для получения нужного блока справочника участка. Затем по указателю нужно загрузить в ОЗУ блок с записями, содержащими запись с ключом V.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.