Л. Партыка, И. И. Попов системы управления базами данных


А1(В2(С5С12С6)В1(С12С9)ВЗ(С14С11С7С18))



бет43/215
Дата29.01.2022
өлшемі4,64 Mb.
#115817
1   ...   39   40   41   42   43   44   45   46   ...   215
Байланысты:
Голицына О Л Партыка Т Л Попов И И Системы

А1(В2(С5С12С6)В1(С12С9)ВЗ(С14С11С7С18))

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



Левосписковые структуры с переполнениями. Включение и удаление элементов могут быть выполнены с помощью метода переполнения или метода распределенной свободной памяти.

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



Рис. 1.32. Пример реализации древовидной структуры методом переполнения

до обновления

Рис. 1.33. Пример реализации древовидной структуры методом переполнения

после обновления

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

Использование указателей на  «подобные»  и  «порожденные».

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



  • указатели на порожденные записи;

  • указатели на подобные записи;

  • указатели на исходные записи.

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

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



Рис. 1.34. Пример реализации древовидной структуры (рис. 1.28) с использованием ссылок «порожденный — подобный» (заштрихованные области означают конец списка)



Рис. 1.35. Пример реализации древовидной структуры с использованием кольцевых ссылок

 

На рис. 1.35 ссылки образуют кольца двух типов: подобных записей и кольца «исходный — порожденный». В записях самого нижнего уровня показаны указатели на исходные записи. Для единообразия здесь каждая запись имеет два указателя. Однако кольца большей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.





Достарыңызбен бөлісу:
1   ...   39   40   41   42   43   44   45   46   ...   215




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет