Физические структуры данных. Нелинейные структуры

В нелинейных структурах помимо информационных полей физические записи включают одно или несколько полей указателей:

- на следующую запись объекта (односвязные списки);

- на связанные записи других информационных объектов (многосвязные списки, древовидные структуры).

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

Недостаток - растут затраты при любых операциях добавления, удаления и корректировки записей.

Образование страниц физических записей на примере записей, связанных отношением «один-ко-многим».

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

При появлении связанных записей для каждой из них образуются подчинённые страницы для размещения соответствующих связанных записей объекта на стороне «Многие».

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

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

Количество уровней называют высотой дерева.

Максимально возможное количество потомков у одного предка называют степенью дерева.

Деревья степени больше двух называют сильноветвистыми.

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