Сохранение иерархического упорядоченного списка (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, сосредоточенный вокруг представления иерархически структурированных данных и их сохранения - возможно, слишком тяжелый для проблемы, которую вы пытаетесь решить.
• вуду: эм...

Обновить

Если вы реализуете все части из этого ответа, добавить это дешево, пересортировать - это небольшая стоимость, перемещение - дорого. Компромисс - быстрое чтение иерархии - например, найти полное происхождение узла за одну операцию. В частности, добавление листа является операцией 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, в котором уже есть механизмы персистентности (и некоторые другие полезные вещи).