4. Складывание.

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

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

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

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

Запись 00 Запись 01

0

1 Цепочка 0

...

М-1

Рис. 5.1

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

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

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

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

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

5.3. Индексированные файлы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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