Нелинейные структуры организации файлов данных

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

Рис. 2.12. Нелинейная структура данных на примере односвязного списка (поля указателей выделены жирными рамками).

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

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

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

Одной из таких стратегий является стратегия минимизации расходов на доступ к записям, связанным на логическом уровне отношением «Один — ко многим», что обусловлено широкой распространенностью таких отношений в предметных областях АИС.

Данная стратегия основывается на использовании иерархических древовидных структур.

Общая схема этой стратегии выглядит следующим образом. Для записей информационного объекта на стороне «Один» образуется страница файла данных, в которую последовательно (как и в линейных структурах) помещаются соответствующие записи. При появлении в базе данных связанных записей, для каждой записи из страницы объекта на стороне «Один» образуются «подчиненные страницы» для размещения соответствующих связанных записей объекта на стороне «Многие». В свою очередь, подчиненные записи сами могут иметь свои подчиненные записи, для которых создаются соответствующие страницы, и т.д. (рис. 2.13).

Рис. 2.13. Пример нелинейной древовидной иерархической структуры данных.

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

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

Временные затраты на поиск и обработку записей в буферах оперативной памяти существенно меньше затрат на считывание данных из «медленной» внешней памяти и блоковое (страничное) считывание обеспечивает существенный выигрыш в расходах на доступ и обработку связанных записей.

Во многих предметных областях АИС отношения между информационными объектами могут порождать ситуации, когда у определенных записей на стороне «Многие» имеется несколько разных предков на стороне «Один». Такие случаи не вписываются в рамки описанных иерархических структур. И решение в этих случаях достигается через введение избыточности (дублирования) данных по связанным записям или иными способами.

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

Деревом называется неориентированный связный ациклический граф. Граф, любая пара вершин которого связана, называется связным графом.

Отсутствие цикла – ацикличность.

Деревья с ориентированными ребрами (дугами) называют деревьями с корнем. Все ребра имеют направление от корня.

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

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

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

Рис. 2.14. Нелинейная древовидная, иерархическая структура.

Хорошая алгоритмизируемость этих операций предопределила широкое использование нелинейных древовидных структур в схемах физической организации данных, обеспечиваемых СУБД.