19.3. Методы включения записей, основанные на резервировании

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

Наличие некоторого объема свободной памяти в каждом управляемом интервале приводит к тому, что большая часть вновь поступающих записей умещается в пределах соответствующих интервалов. Тем не менее, неизбежны случаи нехватки распределенной свободной памяти в интервалах для включения новых записей. В таких случаях осуществляется «расщепление» интервала. Предположим, что необходимо включить запись с некоторым значением ключевого поля. В соответствии со значением ключевого поля определяется интервал, в который следует включить запись. Но, так как интервал уже полностью заполнен, поэтому осуществляется его расщепление: половина его записей пересылается в свободный интервал, входящий в состав той же управляемой области.

Резюмируя, перечислим способы включения в файл новых записей:

1). При включении новых записей файл перезаписывается с размещением записей в соответствующих местах.

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

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

19.4. Физическое представление иерархических структур

Рассмотрим физическое представление древовидных структур на примере обновления дерева с использованием следующих методов (слайд 8):

1. Физически последовательное размещение.

2. Указатели.

3. Цепи и кольца.

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

Физически последовательное размещение. На слайде (слайд 8) представлен пример реализации иерархической структуры путем физически последовательного размещения данных на носителе.

Последовательность элементов иногда называется левосписковой структурой (последовательность типа «сверху вниз - слева направо»).

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

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

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

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

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

В этом случае для определения местонахождения записей А, В или С можно использовать индексы.

Использование указателей на «подобные» и «порожденные».Для обеспечения эффективных процедур выборки записей могут использоваться межзаписные ссылки следующих типов:

• указатели на порожденные записи;

• указатели на подобные записи;

• указатели на исходные записи.

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

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

На рис. ссылки образуют кольца двух типов: подобных записей и кольца «исходный—порожденный». В записях самого нижнего уровня показаны указатели на исходные записи. Для единообразия здесь каждая запись имеет два указателя. Однако кольца большей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.