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

Question

Я хочу хранить иерархические упорядоченные списки.Одним из примеров могут быть вложенные списки задач.Другим примером будет 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 выполняется с помощью кода или - предпочтительно- триггер базы данных для любой вставки, удаления или обновления.Кроме того, для извлечения всей иерархии с помощью одного оператора SELECT вызывается таблица моста иерархии:

id
descendent_id 

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

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

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

• Плоские файлы : комбинация связанных списков и файлов, отображаемых в память, вероятно, подойдет, нона самом деле вы просто катитесь на своем месте в тот момент, когда решение SQL или NoSQL, вероятно, будет лучше.
• SQL : это мой подход - здесь лучше всего подходят инструменты для манипулирования данными, резервного копирования и восстановления.
  • XML : это также возможно с базой данных, в зависимости от конкретного поставщика, вам необходимо изучить синтаксис для вставки, обновления и удаления узла.Может быть очень быстрым, если база данных предлагает тип данных XML.
• NoSQL : если вы говорите хранилище значений ключей , типичный подход для иерархических данных представляется материализованным путем, но для этого потребуется пересчитать весь путь для всех затронутых узлов при изменении, что, вероятно, медленно.Вместо этого рассмотрим Java Content Repository (JCR) - Apache Jackrabbit - это реализация - весь API, сосредоточенный вокруг представления иерархически структурированных данных и их сохранения - возможно, слишком тяжелый для проблемы, которую вы пытаетесь решитьрешать.
• voodoo : гм ...

Обновление

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

Тем не менее, используйте только Список смежности (т. Е. id, parent_id), и запись становится дешевой, чтение для одного уровня - дешевым, но чтение, которое пересекает иерархию, дорого.Тогда последнему потребуется использовать рекурсивный SQL, такой как Oracle CONNECT BY или Common Table Expressions, как в SQL Server и других RDBMS.

Answer 2

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

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

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

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

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