Оформить и купить диплом на бланке ГОЗНАК без предоплаты

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

Если применяется хеширование, то поля записи, соответствующие ключу отношения, объединяют в единое поле и интерпретируют как  число N. Для полученного числа вычисляют хеш-функцию H(N).

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

Приведем несколько достаточно быстрых алгоритмов для вычисления хеш-функции H(N) с хорошим равномерным распределением значений.

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

Пример. Пусть  число значений M = 70, а ключ N = 255. Квадрат ключа равен 65025, центральные цифры – 02 из диапазона 0...99. Приводим число 2 к диапазону 0...69:   2 · ( 70 / 100 ) => 1,4  и округляем результат до 1. Число 1 суть значение хеш-функции.

Деление. Ключ делится на M или на близкое к M простое число. Остаток от деления является значением хеш-функции.

Пример. Пусть  число значений M = 70, а ключ N = 255.

Разделим 255 на 70 и остаток, равный 45, используем как значение хеш-функции. Можно разделить 255 на простое число 67; значение хеш-функции будет равно 54.

Сдвиг разрядов. Разряды ключа разбиваются на две части: старшие и младшие разряды. Обе части сдвигаются навстречу друг другу настолько, чтобы число перекрывающихся разрядов соответствовало разрядности M. Перекрывающиеся разряды складываются и результат приводится к диапазону 0...M-1.

Пример. Пусть  число значений M = 70, а ключ N = 17543291.

Делим ключ на две части 1754 и 3291, сдвигаем навстречу друг другу на 2 разряда, что  соответствует разрядности M и складываем перекрывающиеся разряды. Результат получается равным 86. Приводим число 86 к диапазону 0...69: ( 86 · 70 ) / 100  и получаем значение хеш-функции равным 60.

Складывание. Разряды разбиваются на три части, средняя из которых соответствует по разрядности числу M. Затем все части складываются, причем крайние части “заворачиваются”, т. е. используются в обратном порядке, и результат приводится к диапазону 0...M-1.

Пример. Пусть  число значений M =70, а ключ N = 17543291. Делим ключ на три части 175, 43 и 291, складываем числа 57, 43 и 92 по модулю 100. Результат получается равным 92. Приводим число 92 к диапазону 0...69: ( 92 · 70 ) / 100  и получаем значение хеш-функции равным 63.

Исследования приведенных алгоритмов позволили выделить алгоритм “Деление” как лучший, правда, с небольшим преимуществом по равномерности распределения.

На рисунке отражена организация хешированного файла.

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

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

 

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

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

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

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

Применяют два вида индексных файлов:

- файл с плотным индексом;

- файл с разреженным индексом.

В файле с плотным индексом хранят пары (v, p), где v – ключ записи, а p – указатель (адрес или смещение) на запись в главном файле.

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

При удалении записи указатель p устанавливают в значение NULL (“пусто”) и в главном файле возникают “дыры”; поэтому следует время от времени переписывать главный и индексный файлы.

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

Проблему большого объема файла с плотным индексом решают путем введения нового уровня индексов, а именно создают файл с индексом индексных пар. В этом файле хранят пары (w, n), где w – значение v ключа для первой пары (v, p) из n–й части файла с плотным индексом.

Файл с индексом индексных пар копируют в оперативную память. В результате поиска по ключу находят индекс n. Затем читают соответствующую часть файла с плотным индексом и находят в нем пару (v, p) с адресом p нужной записи в главном файле.

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

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

В файле с разреженным индексом хранят пары (u, k), u – значение ключа для первой записи в k–м блоке записей. Сравнение по ключу позволяет определить номер k блока записей, а затем последовательно просматриваются записи в блоке. Характер данного алгоритма поиска объясняет другое название файлов с разреженным индексом – файлы с индексно-последовательной организацией.

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

Для файлов с разреженным индексом также применяют иерархию индексов.

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