4.2.3. Использование указателей на «подобные» и «порожденные»
Для обеспечения эффективных процедур выборки записей могут использоваться межзаписные ссылки следующих типов:
- указатели на порожденные записи;
- указатели на подобные записи;
- указатели на исходные записи.
При построении древовидных структур, в которых используется какой либо один тип указателя, всегда исходят из альтернативы между сложностью реализации списка указателей переменной длины на порожденные записи и увеличением времени поиска, связанным с использованием цепочки указателей на подобные записи.
Практически эффективные компромиссы могут быть достигнуты путем использования в каждой записи двух указателей каких-либо двух типов (рис. 4.11), а также использованием кольцевых структур (например, рис. 4.12).
 |
Рис. 4.11. Пример реализации древовидной структуры (рис. 4.5.) с использованием ссылок «порожденный-подобный» (штрихованные области означают конец списка)
Рис. 4.12. Пример реализации древовидной структуры с использованием кольцевых ссылок
На рис. 4.12 ссылки образуют кольца двух типов: подобных записей и кольца «исходный—порожденный». В записях самого нижнего уровня показаны указатели на исходные записи. Для единообразия здесь каждая запись имеет два указателя. Однако кольца большей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.
Назад к разделу "4.2.2. Левосписковые структуры с переполнениями"
Вперед к разделу "4.3. Физическое представление сетевых структур"