Сохранение иерархического упорядоченного списка (flatfile/sql/nosql)

Question

Я хочу сохранить иерархические упорядоченные списки. Одним из примеров может быть вложенный список todo. Другим примером может служить XML. Это будет просто дерево, где дети в порядке. Для простоты записи являются просто строками текста.

Дело в том, что список будет редактироваться пользователем, поэтому важно, чтобы общие операции быстро:

• Редактировать элемент
• Удалить элемент
• Вставьте запись перед другой

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

• Редактирование смотрит хеш, а затем заменить часть данных связанного списка
• Стирание смотрит вверх хэш и делать связанный список удаление
• Вставка смотрит вверх хэш и делать связанный ввод списка

Однако мне нужно хранить данные, и я понятия не имею, как этого добиться. Я не хочу сохранять все дерево, если изменяется только один элемент. Каков наилучший способ? Плоские файлы/SQLs/NoSqls/voodoos?

Answer 1

Использование реляционной базы данных является жизнеспособным решением.Для ваших нужд - быстрой вставки, обновления, удаления - я бы использовать список смежности с дополнительными настройками, как, например:

id 
parent_id 
cardinality -- sort order for all nodes with the same parent_id 
depth -- distance from the root node 

Расчет cardinality и depth осуществляется либо с кодом или - предпочтительно - триггер базы данных для любого вставить, удалить или обновить. Кроме того, для извлечения целой иерархии с одним ЗЕЬЕСТОМ, иерархия таблица моста вызывается для:

id 
descendent_id 

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

See this question for additional detail around Adjacency List, Hierarchy Bridge and other approaches for storing hierarchical data in a relational database.

Наконец, чтобы предоставить некоторые дополнительные разъяснения относительно вариантов, которые вы перечислили:

• Flat Files: сочетание связанных списков и памяти отображаются файлы, вероятно, служить, но вы на самом деле просто добавить собственные в эта точка, где решение SQL или NoSQL, вероятно, будет лучше.
• SQL: это был бы мой подход - инструментарий лучше всего подходит для обработки данных, резервного копирования и восстановления.
  • XML: это также возможность с базой данных, очень конкретный поставщик, вам необходимо изучить синтаксис для вставки узла, обновления и удаления. Может быть очень быстрым, если база данных предлагает тип данных XML.
• NoSQL: если вы говорите, тем key-value storagetypical approach for hierarchical data appears to be materialized path, но это потребует перерасчет всего пути для всех затронутых узлов на изменениях, которые, вероятно, медленно. Вместо этого рассмотрим, что Java Content Repository (JCR) - Apache Jackrabbit - это API всей реализации, ориентированный вокруг иерархических структурированных данных и сохраняющий его - возможно, слишком тяжелый для проблемы, которую вы пытаетесь решить.
• вуду: гм ...

Update

Если вы реализуете все части из этого ответа, добавить дешево, пересортировывать небольшая стоимость, шаг стоит дорого. Компромисс - это быстрый просмотр обхода иерархии - например, найдите полную родословную узла за одну операцию. В частности, добавление листа является операцией O (1). Повторная сортировка означает обновление мощности всех узлов-узлов, следующих за перемещенным узлом. Перемещение означает обновление (1) мощности для исходных и целевых узлов-узлов, следующих за ним, (2) глубина перемещенных и потоковых-узлов и (3) удаление и добавление родословной в таблицу иерархических мостов.

Однако, перейдите только с списком Adjancency List (т. Е. id, parent_id), и напишите, что дешево, читает на одном уровне, дешево, но читает, что траверс иерархии дорог. В последнем случае потребуется использовать рекурсивный SQL, такой как CONNECT BY Oracle или Common Table Expressions, как в SQL Server и других РСУБД.

Answer 2

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

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

Предположим, что вы используете типичное хранилище ключей, от xDBM или Berkeley DB к любым из современных предложений NoSQL. Также вы можете взять компактный SQL-движок, например. sqlite. Обычно они используют деревья для индексирования ключей, поэтому для доступа к ключу или к хэш-таблицам требуется примерно O (logN), что занимает примерно столько же или меньше.

Вы не указали, когда вы сохраняете свои данные постепенно. Если вы делаете это только раз в то время (не для каждого обновления), вам нужно будет эффективно сравнивать базу данных с вашей основной структурой данных. Это будет относительно трудоемким, потому что вам нужно пройти по всему дереву и посмотреть каждый идентификатор узла в базе данных. Это логарифмически, но с огромной константой из-за необходимости ввода-вывода. И тогда вы захотите очистить постоянный магазин от предметов, на которые больше не ссылаются. Может случиться так, что просто демпинг дерева как JSON намного эффективнее. Фактически, это то, что делают многие базы данных в памяти.

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