Л. Партыка, И. И. Попов системы управления базами данных
Физическое представление сетевых структур
жүктеу/скачать 4,64 Mb.
|
Голицына О Л Партыка Т Л Попов И И Системы
- Бұл бет үшін навигация:
- Физически последовательное размещение.
| Физическое представление сетевых структур
Так же как и в случае древовидных структур, связи в сетевых структурах (см. гл. 2, разд. 2.1) можно представить, используя физически последовательное размещение, указатели, кольца. Рассмотрим простую сетевую структуру (рис. 1.36). Рис. 1.36. Пример простой сетевой структуры Физически последовательное размещение. Если древовидные структуры можно представить без избыточности с помощью физически последовательного размещения, для сетевых структур это обычно невозможно. Однако в некоторых случаях может оказаться удобным способом представить один набор связей типа «исходный — порожденный» путем физически последовательного размещения, а для остальных связей использовать другой метод. Например, можно использовать физически последовательное размещение для представления связей А и С (рис. 1.37). Рис. 1.37. Пример реализации сетевой структуры с последовательным размещением. В этом примере связи между В и С реализуются с помощью множественных указателей на порожденные записи, указателей на исходные записи и указателей на порожденные и подобные записи. Для множественных указателей на порожденные записи требуются списки указателей переменной длины; для указателей на порожденные и подобные записи необходимы длинные цепочки. Обычно для представления сетевых структур физически последовательное размещение не применяется. Использование указателей. Если для реализации сетевых структур используются указатели, то они должны представлять все связи, причем какие-то записи должны называться исходными (например, верхние), а какие-то — порожденными (нижние записи). На практике может использоваться много различных вариантов конфигураций указателей. На рис. 1.38 показаны кольцевые структуры, в которых имеются указатели на исходные, порожденные и подобные записи. Однако если какая-нибудь связь между записями относится к типу «многие ко многим», то названные три метода физического представления сетевых структур оказываются непригодными. Более того, если в простых сетевых структурах на предыдущих рисунках для хранения указателей на исходные записи требовались
Рис. 1.38. Пример реализации сетевой структуры с использованием указателей один или два указателя в каждой записи, то здесь необходимы списки указателей переменной длины. Основной проблемой, возникающей при организации встроенных списков указателей переменной длины, является сложность их ведения. При обновлении файла должна существовать возможность сокращения и удлинения списков, что обычно приводит к необходимости периодической реорганизации. Реорганизация является сложной задачей, поскольку при перемещении записей должны быть изменены многие указатели. Эта проблема частично решается, если использовать символические указатели, которые не изменяются при перемещении записей. Однако их применение отражается на механизме адресации и при поиске записей в файле: система затрачивает на поиск записей больше времени, чем при использовании прямых указателей.
жүктеу/скачать 4,64 Mb. Достарыңызбен бөлісу:
|