Физичиские структуры данных показывают каким образом данные отражаются в среде хранения. При отражении данных с определенной логической структурой, с одной стороны должна сохранятся их симантика, а с другой должна обеспечиваться эффективность обработки данных. На физические структуры оказывает влияние АБД и запоминает устройства, так как размещение данных на разных носителях имеют свою специфику. По способу закрепления места в памяти различают позиционные и непозиционные структуры. В позиционных структурах место и роль элементов заранее однозначно определено, элемент имеет степень закрепления. Иногда структура БД становится гибкой, когда в ключ вводится логика, такие структуры становятся вычисляемыми или рандомизированными. В непозиционных структурах элементы жестко не закреплены, задается логический порядок следования данных, способ отображения связей между ними в памяти, а также порядок, согласно которому определяется следующий элемент. По способу отображения связей между элементами различают последовательно-смежные, списковые структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 СХЕМА .  

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

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

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

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

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

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

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

НЕДОСТАТКИ:

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

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

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

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

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