Упорядоченные последовательные файлы

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

Преимущество.
Эффективный поиск (бинарный) по значениям полей сортировки. Выполняется с учетом разбиения логических полей по страницам. В общем случае бинарный поиск эффективнее линейного, однако этот метод чаще применяется для поиска данных в первичной, а не во вторичной памяти.

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

ХЕШИРОВАННЫЕ ФАЙЛЫ

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

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

Хеш-функция выбирается таким образом, чтобы записи внутри файла были распределены максимально равномерно.

Один из методов построения хеш-функции носит название свертка и основан на выполнении некоторых арифметических действий над различными частями поля перемешивания. При этом, например, символьные строки преобразуются в целые числа с использованием некоторой кодировки — на основе расположения букв в алфавите или ASCII-кодов символов.

Более популярный альтернативный метод основан на перемешивании на основе остатка от деления.

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

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

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

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

Использование метода хеширования для извлечения записей основано на полностью известном значении хеш-поля. Поэтому хеширование не .подходит для операций извлечения данных по заданной маске или диапазону значений. Более того, хеширование не подходит для поиска и извлечения данных по любому другому полю, отличному от поля перемешивания.

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

Лекция 12-13

ОТКРЫТАЯ АДРЕСАЦИЯ

При возникновении конфликта система выполняет линейный поиск первого доступного слота в вычисленном сегменте. Если такой слот не найден, поиск продолжается в следующем сегменте. Если слот не найден и в последнем сегменте, поиск слота продолжается с первого сегмента. Если слот не найден до достижения первоначального сегмента, то запись невозможна (БД переполнена).

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

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

Преимущества
1. Высокая плотность записи при фиксированных по размеру сегментах (БД переполнена, когда заполнены все слоты).
2. Высокая эффективность поиска, записи, удаления для разреженных БД, т.к. записи будут расположены рядом со своим сегментом.

Недостатки.
1. Большая потеря производительности при выполнении операций поиска, записи, удаления при сильно заполненных БД.
2. Фиксированный размер БД.