8.1.2 Неупорядоченные и упорядоченные файлы
Неупорядоченный файл (куча) имеет простейшую структуру. Записи в файле размещаются в том порядке, в котором они в него вставляются. Каждая новая запись размещается на последнюю страницу файла, а при заполнении последней страницы в файл добавляется новая страница.
Недостатки при неупорядоченном хранении данных:
файл подобного типа не обладает никаким упорядочиванием, для доступа к его записям применяется линейный поиск;
при удалении записи необходимо извлечь страницу, удалить запись и затем сохранить страницу. Пространство удаленных записей повторно не используется, следовательно, во избежание потери производительности работы необходима периодическая реорганизация.
Неупорядоченные файлы используются при массовой загрузке данных в таблицу.
Упорядоченные файлы исключают недостатки использования неупорядоченных файлов. Записи в упорядоченных файлах можно отсортировать по значениям одного или нескольких полей, т.е. образовать набор данных, упорядоченный по некоторому ключу. Поле или набор полей, по которому сортируется файл, называется полем упорядочения. Если поле упорядочения является также ключом доступа к файлу, т.е. гарантирует наличие в каждой записи уникального значения этого поля, то оно называется ключом упорядочения для данного файла.
В
качестве примера поиска записи в
упорядоченном файле рассмотрим Отношение
сотрудники, предположив, что поле Код
сотрудника является ключом упорядочения
и на каждой странице находится по одной
записи. Необходимо найти сотрудника с
кодом 004. Упорядоченный файл выглядит
как на рисунке 20.
Рисунок 20 - Пример упорядоченного файла
При бинарном поиске поиск сотрудника 004 будет иметь следующие этапы:
Выборка средней страницы файла (страница 3). Проверка наличия искомой записи между 1-й и последней записями страницы 3. Так как запись не найдена и значение искомой записи больше значений на странице, происходит переход на середину правой части оставшихся страниц.
Выборка страницы 5 файла. Проверка наличия искомой записи между 1 и последней записями этой страницы. Так как запись не найдена и значение искомой записи меньше значений на странице, происходит переход на страницу между уже проверенными.
Выборка страницы 4, как промежуточной между 3-й и 5-й. Проверка наличия искомой записи между 1-й и последней записями этой страницы. Определение страницы 4 как искомой.
Операции вставки и удаления записей в отсортированном файле усложняются в связи с необходимостью поддерживать установленный порядок записей. При удалении записей возможно неполное заполнение страниц, при добавлении переполнение страниц и, как следствие, перемещение записей на следующую страницу и т.д. Для решения этой проблемы используют файл переполнения, или файл транзакции, который является неотсортированным файлом и содержит записи переполнения. Поиск при такой организации памяти в отсортированном файле ведется по бинарному правилу, а если запись не найдена, то в файле транзакции - по линейному.
8.1.3 Хешированные файлы
В хешированном файле записи не обязательно вводятся в файл последовательно. Вместо этого для вычисления адреса страницы, на которой должна находиться запись, используется хеш-функция, параметрами которой является значение одной или нескольких полей этой записи. Подобное поле называют полем хеширования, а если поле является также ключевым полем, то оно называется хеш-ключом. Записи в хешированном файле распределены произвольным образом по всему доступному для файла пространству, поэтому хешированные файлы называют файлами с произвольным или прямым доступом. Методы хеширования можно разделить на статические и динамические.
При статических методах хеширования хеш-функция выбирается таким образом, чтобы записи внутри файла были распределены наиболее равномерно. Один из методов создания хеш-функции называется сверткой и основан на выполнении некоторых арифметических действий над различными частями поля хеширования. При этом символьные строки преобразуются в целые числа с использованием некоторой кодировки. Другой альтернативный метод создания хеш-функций основан на хешировании с применением остатка от деления. В этом методе используется функция MOD, которой передается значение поля. Функция делит полученное значение на некоторое заранее заданное целое число, после чего остаток от деления используется в качестве адреса на диске.
Недостатком использования хеш-функций является то, что они не гарантируют получения уникального адреса, поскольку количество возможных значений поля хеширования может быть гораздо больше количества адресов, доступных для записи. Случай, если один и тот же адрес генерируется для двух и более записей, называется конфликтом, а подобные записи – синонимами. Разрешение конфликтов усложняет сопровождение хешированных файлов и снижает общую производительность их работы. Для устранения конфликтов используются различные методы:
открытая адресация;
несвязанная область переполнения;
связанная область переполнения;
многократное хеширование.
При статических методах хеширования считается, что пространство хеш-адресов задается непосредственно при создании файла и при значительном увеличении или уменьшении данных в базе данных администратор базы данных вынужден реорганизовать его хеш-структуру. Для этого может потребоваться создание нового файла большего размера, выбор новой хеш-функции, перезапись файла на вновь отведенное место. При динамических методах хеширования допускается динамическое изменение размера файла с целью его постоянной модификации в соответствии с увеличением или уменьшением размеров базы данных.
В хешированных файлах страницы принято называть сегментами, а ячейки для записи внутри сегмента – слотами.
При динамических методах хеширования сегменты создаются по мере необходимости. В начале записи добавляются только в первый сегмент, до тех пор, пока он не будет полностью заполнен. Затем сегмент расщепляется на части, количество которых зависит от числа i битов в хеш-значении, где 0<=i<32. Значение i изменяется в зависимости от размера базы данных. Текущее значение i для каждого сегмента (глубина) хранится в таблице адресов сегмента.
Использование хеширования неудобно для извлечения записей по определенному диапазону, более удобным способом в этом случае является использование индексации.