Указатели узлов обычно хранятся на диске в виде адресов (например, с использованием длинных целых чисел).
В общем случае реализация выбирает использование либо физических, либо логических адресов:
- Физические адреса указывают фактическое смещение (в файле или аналогичном), где хранится узел.
- Напротив, для логических адресов требуется какой-то механизм, который разрешается в физический адрес каждый раз, когда указатель перемещается/обходит.
Физическая адресация выполняется быстрее (поскольку механизм разрешения не требуется). Однако логическая адресация может позволить реорганизовать узлы без перезаписи указателей. Возможность реорганизации узлов таким образом может быть использована в качестве основы для реализации хорошей кластеризации, использования пространства и даже низкоуровневого распределения данных.
В некоторых реализациях используется комбинация логической и физической адресации, так что каждый адрес состоит из логического адреса, который ссылается (динамически) на сегмент (блоб) и физического адреса в этом сегменте.
Важно отметить, что адреса узлов основаны на диске, поэтому их нельзя напрямую преобразовать в указатели в памяти.
В некоторых случаях полезно преобразовать указатели на диске в указатели на память, когда данные загружаются в память (и затем преобразовать обратно в указатели на диске при записи).
Это преобразование иногда называют прокруткой указателя, и его можно реализовать разными способами. Фундаментальная идея заключается в том, что данные, адресованные прокручиваемыми указателями в памяти, не должны загружаться в память до того, как указатель будет перемещен/пройден.
Обычный подход к этому состоит в том, чтобы либо использовать логическую схему адресации в памяти, либо использовать отображаемые в память файлы. Файлы с отображением памяти используют адресацию виртуальной памяти, при которой страницы памяти не загружаются в память до обращения к ним. Файлы отображения виртуальной памяти предоставляются ОС. Этот подход иногда называют адресацией с ошибкой страницы, потому что доступ к данным на странице памяти, которая еще не отображена в память, вызовет прерывание сбой страницы.
person
Mårten Wikström
schedule
20.06.2013
