Если возникнет необходимость переместить список
Если возникнет необходимость переместить список на новое место в памяти ЭВМ, то потребуется выполнить работу изменению указателей во всех записях.
Второй тип указателей – относительный адрес – позволяет размещать записи в любом месте памяти и на различных внешних устройствах без изменения значений указателей, при этом относительное расположение в памяти узлов списка между собой должно оставаться постоянным. При перемещении списка ука затели в записях не изменяются, а изменяется базовый адрес при вычислении действительных машинных адресов. Относительные адреса в качестве указателей применяются при страничной организации памяти. Скорость доступа к узлам при использовании относительных адресов несколько замедляется по сравнению со случаем машинных адресов, однако появляется возможность размещать список в любом свободном месте памяти подходящего размера.
Третий тип указателей – символический адрес (идентификатор) – позволяет перемещать отдельные записи относительно друг друга, включать или удалять записи в список без изменения указателей во всех остальных записях списка. Однако при работе с символическими указателями скорость доступа меньше, чем при работе с машинными или относительными адресами. Идентификаторы в качестве указателей удобно использовать для интенсивно изменяющихся файлов. Преобразование идентификатора в машинный адрес при выполнении операций обращения к узлам списка выполняется с помощью специального алгоритма в соответствии с выбранным методом адресации.
С точки зрения организации структуры данных различают два типа указателей [17]:
– встроенные указатели;
– справочник указателей.
Если указатели образуют часть записи, то они называются встроенными. Если указатели хранятся отдельно от записей, то они образуют справочник.
Указатели имеют следующие возможные пути использования [17]:
1) определяют направление доступа (можно двигаться только в тех направлениях, которые заданы указателями);
2) соединяют вместе связанные по смыслу данные;
3) отображают ориентированные ребра в древовидных или сетевых структурах;
4) связывают память на дисках и организуют цепочки дисковых страниц и т. п.
Применение многосвязанных списков – это основной механизм, позволяющий разработчикам СУБД реализовывать сложные нелинейные структуры. Однако следует избегать слишком большого количества указателей, поскольку на них тратится память и время на переходы по указателям. Кроме того, при большом количестве указателей основная структура, представляемая в памяти ЭВМ, теряет четкость, и могут возникнуть связи, которые в отображаемой структуре отсутствуют.
