Как работают указатели диска?

Question

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

Так, как правильно хранить указатели на диске? Ответ так же прост, как (Файл, Смещение), или я что-то упускаю? Я могу интуитивно понять, как указатели могут быть преобразованы в пары (File, offset) и обратно, но есть ли какие-то тонкости, на которые я должен обратить внимание?

Редактировать: Я должен отметить, что меня особенно интересует, как база данных будет делать это внутренне, для b-дерева. Я, вероятно, сделал вопрос более общим, чем следовало бы, хотя я ценю ответы на основе XML.

Answer 1

Ваше представление о парах (файл, смещение) правильное.

При хранении данных на дисках важно следить за тем, чтобы диски работали медленно. Итак, существуют специальные структуры данных, которые были разработаны для хранения «доступных для поиска» данных на дисках. Доступ к узлам двоичного дерева поиска, хранящегося на дисках с использованием указателя (file, offset), будет на несколько порядков медленнее, чем доступ к ним в памяти.

Если важна скорость доступа, вам нужно хранить на дисках вещи, к которым ожидается доступ, ближе друг к другу. Для этого используется пара структур данных: B-дерево и B + дерево . Ищите их, чтобы узнать, как их использовать. Существуют сложные алгоритмы кэширования , используемые несколькими приложениями, такими как базы данных, для кэширования объектов в памяти, поэтому приложениям не нужно обращаться к диску для получения данных снова и снова.

Если скорость доступа не важна, тогда достаточно просто «сериализовать» данные на диске в форме XML, как предложили Эйден и Даррен.

Редактировать: Если вам нужно больше подробностей о том, как базы данных хранят данные на диске, вам нужно больше узнать о теории баз данных. Я бы посоветовал прочесть хорошую книгу по базам данных, чтобы вы понимали требования, которые определяют формат диска. Обратите внимание, что я в основном имею в виду реляционные базы данных здесь, но есть другие породы из баз данных , которые имеют полностью различные требования и, следовательно, различные форматы дисков. Однако начинать с реляционных баз данных - хорошая вещь, поскольку они наиболее часто используются.

Короче говоря, некоторые вещи, которые влияют на формат диска реляционной базы данных:

1. Производительность чтения / записи на диск
   
2. Восстановление базы данных (в случае повреждения)
   
3. Отношения между сущностями
   
4. Сборка мусора
   
5. Поддержка транзакций
   
6. Первичный индекс
   

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

Answer 2

Точно, сохранение значения указателей будет бессмысленным.

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

Например, вот как могут храниться ваши данные: [meta-data][data]</p> <p>[meta-data] = [ length ][ list-of-Nested-Set-Model-Locations ] [ list-of-data-records ] = [ lft-#1 ][ rgt-#1 ][ lft-#2 ][ rgt-#2 ] ... [data] = [length][ payload / data-itself ]

Это только пример, и использование JSON (рекомендуется) или XML может быть лучше и проще.

Answer 3

Binary или Text - первый вопрос

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

XML был создан как переносимый способ сохранения и обмена структурированными данными.

Если бы это был я, я бы использовал XML-подобный, но менее неуклюжий YAML.

Если файлы, вероятно, станут действительно большими, вы можете сделать то, что делает OpenOffice, и сохранить их как текстовую разметку, но записать непосредственно в сжатый (я думаю, это zip для OO) архив.

Большинство языков уже имеют библиотеки сериализации; Я уверен, что есть некоторая библиотека Boost для C. Как правило, есть несколько интерфейсов сериализации, которые используют разные представления.

Если вы используете библиотеку, XML или YAML, ссылки будут подразумеваться в древовидном представлении. Если ваши данные имеют более общий график, то Независимо от того, используете ли вы текст или бинарный файл, вам, возможно, придется нормализовать ссылки. Это проблема с указателем, которую вы упомянули. Один из способов решения этой проблемы - сохранить временные карты, которые используются при чтении или записи файла. То есть вы просто называете каждую цель ссылки, скажем, A1, A2, A3 ..., а затем используете ее как тег в месте назначения и как имя ссылки (думаю, href =) в источнике.

Я бы не использовал смещения файлов в качестве указателей, просто он кажется слишком хрупким и, естественно, имеет смысл использовать XML, YAML или что-то еще, что уже существует.

Answer 4

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

Обеспечение:

1. Ваши узлы содержат ссылки на сохраняющиеся местоположения
2. Вы можете знать, когда пишете узел, в какие места писать

Вы можете сделать это так, как пожелаете. Файловые системы - это деревья , в которых используется дисковая система inode.

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

Вы также можете использовать файлы XML с ссылки на другие местоположения или отдельный файл и XPath / XPointers .

<Node id="someNode">
    <value>...</value>
    <children>
        <child xpath="/node[id=1]" />
        <child xpath="/node[id=29]" />

Но это будет означать сериализацию ваших значений в символы, если они являются просто двоичными двоичными объектами (eww). Ваше значение может быть путем двоичного фрагмента, только что записанного в файл, например:

<value>/path/to/mappable.bin</value>

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

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

Деревья есть деревья.

Answer 5

Можно ли выполнить поиск по дереву в памяти? Это похоже на общую проблему Java при отправке объекта по сети. Объекты имеют ссылки на другие объекты, но адрес указателя изменится один раз из адресного пространства программы. Не могли бы вы сериализовать свое дерево в форму XML или JSON?