Хешированные файлы

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

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

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

· открытая адресация;

· несвязанная область переполнения;

· связанная область переполнения;

· многократное хеширование.

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

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

При динамических методах хеширования сегменты создаются по мере необходимости. В начале записи добавляются только в первый сегмент, до тех пор, пока он не будет полностью заполнен. Затем сегмент расщепляется на части, количество которых зависит от числа i битов в хеш-значении, где 0<=i<32. Значение i изменяется в зависимости от размера базы данных. Текущее значение i для каждого сегмента (глубина) хранится в таблице адресов сегмента.

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