Безопасность операционных систем. Безбогов А.А - 51 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

При физически последовательном размещении древовидной структуры данных структура хранения начинается узлом,
соответствующем вершине дерева (рис. 5.3). По иерархии за ним следуют узлы на самой левой ветви дерева. В пределах уз-
лов одного уровня они отображаются слева направо.
Подобная организация структуры хранения является единственной при использовании чисто последовательных сред
хранения, например, магнитных лент. При размещении составляющих древовидной структуры данных они могут иметь мет-
ки или специальные разграничители, позволяющие установить, к какому уровню дерева относится та или иная составляю-
щая структуры данных.
При
логически последовательном размещении древовидной структуры возможно два способа отображения дерева на
среду хранения.
В первом способе (рис. 5.4) порции данных, соответствующие каждому узлу дерева, снабжаются ссылочной информа-
цией на порции данных, связанные с ним и находящиеся ниже по иерархии (т.е. на порожденные этим узлом данные).
При втором способе для отображения дерева формируют специальные таблицы, в которые заносится информация об
узлах дерева и связях между ними.
А
1
В
2
В
3
В
1
С
5
С
6
С
4
С
3
С
1
D
4
D
3
D
2
D
1
С
2
Рис. 5.4. Логически последовательное отображение
древовидной структуры с указателями на порожденные записи
Оба эти способа используют представление информации в виде связных списков, каждый элемент которых наряду с
данными о текущем узле дерева содержит информацию о связанных с этим узлом других узлов древовидной структуры.
Прямая организация данных рассчитана на произвольную обработку информации. Основными отличительными осо-
бенностями прямой организации данных являются: не используется система индексов; способ размещения данных на носи-
теле определяет пользователь в своих рабочих программах. Прямая организация данных характеризуется тем, что идентифи-
катор порции данных (ключ) используется для установления адреса этой порции. В наборах данных с прямой организацией
для указания местоположения порций данных применяется два способа адресации: абсолютная адресация порций данных;
относительная адресация порций данных.
Способ абсолютной адресации основан на том, что адрес каждой порции данных в наборе является ее физическим ад-
ресом на носителе данных. Для наборов данных на магнитном диске абсолютный адрес включает в себя, например номер
цилиндра, номер дорожки, номер сектора, номер блока и т.п. – в зависимости от типа накопителя на магнитных дисках. Не-
достатком способа прямой адресации является жесткость привязки порций данных к месту на носителе и, следовательно,
проблематичность их перемещения на внешних запоминающих устройствах.
Способ относительной адресации основан на использовании порядковых номеров порций данных, отсчитываемых от
начала набора данных. Эти порядковые номера используются либо самостоятельно, либо в сочетании с номерами порций дан-
ных на дорожках магнитных дисков. Существует три разновидности реализации способа относительной адресации: метод клю-
ча (метод прямой адресации); метод косвенной адресации; метод адресных таблиц (метод перекрестных ссылок).
Метод прямой адресации является наиболее распространенным и эффективным, так как он реализуется самым про-
стым образом при произвольном порядке работы с порциями набора данных прямой организации. В этом методе адресом
любой порции данных является некоторое натуральное число, представляющее собой порядковый номер порции относительно
начала набора данных. Очень часто в качестве такого номера используется некоторое поле порции данных (ключ или признак)
либо в "чистом" виде, либо после минимальных преобразований. Например, из текущего значения признака вычитается его
минимально возможное значение. Результат вычитания принимается как относительный номер порции в наборе данных. Пря-
мой метод обеспечивает взаимно-однозначное соответствие между относительным номером порции данных и ее относитель-
ным физическим адресом в наборе.
Основными недостатками метода прямой адресации являются:
1)
необходимость использования порций данных одинаковой длины;
2)
перед созданием набора данных необходимо выполнить подготовительные действия по разметке отведенного для
него участка на носителе данных;
3)
если значения признака, задающего адрес порции данных, расположены неравномерно, то набор данных будет не-
эффективно использовать выделенное ему пространство памяти на носителе, поскольку внутри набора данных образуются
пустоты из-за наличия неиспользованных значений признака.

Страницы