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

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

Последовательная организация хранения данных (ПОХД).

ПОХДобладает следующими преимуществами:

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

2.возможность использования любых носителей информации.

3.сокращение времени обработки при условии, что порядок размещение на носителе совпадает с требованием в порядке обработки.

4.простота организации данных и манипулирование ими, так как идет увеличение объема памяти и уменьшение цены, то значимость 1 и 2 фактора снижается.

Последовательные структуры данных имеют недостатки:

1.неудобство корректировки.

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

3.трудности в обеспечении адекватного, интегрированного отображения предметной области.

4.длительность выборочного поиска.

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

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

Списковая организация хранения данных.

Заключается в использование адресных указателей для связей элементов данных. Различают списковую организацию с совместным и раздельным хранением, с объектной, собственной, ассоциативной, адресной информацией, однонаправленные и двунаправленные списки. Такая классификация списковых структур традиционная. Взависимости от характера связывания элементов, списковая структура может связывать однотипные элементы данных в единую структуру – однородный список. На одном и том же множестве элементов может быть задано несколько связей, каждая из которых выделяет подмножество элементов, это списки – многосвязные. Если информация в списках одного типа, то информация называется гомогенной. Если информация разнородна, то список называется гетерогенным.

СХЕМА.

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

При создании БД возможны различные организации однородных и гетерогенных структур. В некоторых БД каждому из типов элементов может ставиться отдельная отдельная совокупность (файл). Такая структура – многофайловая структура.

Списковая организация обладает преимуществами:

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

2.позволяют динамически наращивать состав БД без существенного изменения существующих ее частей.

3.устраняют дублирование данных (избыточность), позволяют на одном и том же множестве элементов обеспечивать их различную упорядоченность.

4.просто могут быть организованы в любой прямоадресной памяти.

НЕДОСТАТКИ:

1. Большой расход памяти на указатели.

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

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

4. Списковая структура нуждается в сложном управлении свободной памяти.

5. Эффект дробления памяти приводит к необходимости реорганизации массива.

СИМВОЛИЧЕСКИЕ УКАЗАТЕЛИ. (СУ)

В любой БД устанавливаются СУ, если они автоматически поддерживают СУБД.

СУ имеют ряд преимуществ перед адресными:

1. Позволяют производить независимую реорганизацию связанных массивов.

2. Повышают семантическую самостоятельность каждой из связанных совокупностей.

3. Могут быть реализованы в памяти любого типа.

НЕДОСТАТКИ:

1. Расходуется больше времени на поиск и корректировку данных.

2. Требуется больше памяти, чем адресным указателям.

ИНДЕКСНАЯ СТРУКТУРА.

Понятие индекса используется по-разному.

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

При плотной, каждой записи этого файла соответствует элемент индекса. При

разряженной элементы индекса соответствуют группе записи индексированного файла. При организации БД преимущество плотной индексации.

Характеристика индексных структур – способ организации индексного массива и связаные с ним особенности корректировки структуры.

При разряженной индексации –индексируемый массив должен быть частично упорядочен. Плотная не предъявляет требований к организации индексируемого массива. Распределение памяти для расширенного файла – важно. Выделение специальной области в памяти, их связывает записью, переплетая в цепочку, как следствие – замедляет процесс обработки данных в БД, требует ее периодической реорганизации, кроме индексации по ключивой записи плотная индексация по любому полю записи. Такая индексация – вторичная инвертированная. Она производится как по одному, так и по сов-ти полей. Рандомизированный способ доступа.