Неупорядоченные и упорядоченные файлы

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

Недостатки при неупорядоченном хранении данных:

· файл подобного типа не обладает никаким упорядочиванием, для доступа к его записям применяется линейный поиск;

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

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

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

В качестве примера поиска записи в упорядоченном файле рассмотрим Отношение сотрудники, предположив, что поле Код сотрудника является ключом упорядочения и на каждой странице находится по одной записи. Необходимо найти сотрудника с кодом 004. Упорядоченный файл выглядит как на рисунке 20.

Рисунок 20 - Пример упорядоченного файла

При бинарном поиске поиск сотрудника 004 будет иметь следующие этапы:

1. Выборка средней страницы файла (страница 3). Проверка наличия искомой записи между 1-й и последней записями страницы 3. Так как запись не найдена и значение искомой записи больше значений на странице, происходит переход на середину правой части оставшихся страниц.

2. Выборка страницы 5 файла. Проверка наличия искомой записи между 1 и последней записями этой страницы. Так как запись не найдена и значение искомой записи меньше значений на странице, происходит переход на страницу между уже проверенными.

3. Выборка страницы 4, как промежуточной между 3-й и 5-й. Проверка наличия искомой записи между 1-й и последней записями этой страницы. Определение страницы 4 как искомой.

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