Сохранение древовидной структуры данных в Ruby

Question

У меня есть проект, в котором мне нужно создавать и хранить большие деревья данных в Ruby. Я рассматриваю различные подходы для сериализации, десериализации и запросов деревьев, и мне интересно, что будет лучшим способом. Моими основными ограничениями являются время чтения, эффективность запросов и совместимость между версиями и кроссплатформенностью. Наиболее частой операцией является получение наборов узлов на основе комбинации идентификатора / значения и / или функции (ий). Дерево может иметь глубину до 15-20 уровней. Перемещение поддеревьев является необычной процедурой, но должно быть возможно без слишком большого количества черной магии. Интеграция с Rails не является первостепенной задачей. Варианты, о которых я подумал, а также некоторые вопросы, которые меня беспокоят, следующие:

• Маршал деревьев, а при необходимости загружать их в память и запрашивать их в Ruby (неэффективность по мере роста дерева, кросс-версия совместимости?)
• То же, что и выше, но использовать YAML (более совместим с версиями, но менее эффективен?)
• То же, что и выше, но использовать пользовательский анализатор XML (нужно воссоздавать объекты с нуля при каждой загрузке дерева?)
• Сериализация деревьев в XML, сохранение их в базе данных XML (например, Sedna) и использование XPath для запросов к деревьям (нет опыта работы с этим подходом, не уверены в эффективности?)
• Использование списков смежности для запроса деревьев, хранящихся в базе данных без схемы (неэффективность при подсчете потомков?)
• Использовать материализованные пути (вероятность переполнения максимальной длины строки для глубоких деревьев?)
• Использовать вложенные множества (сложные запросы SQL?)
• Использовать массив предков ? Кажется интересным с точки зрения эффективности запросов в соответствии со страницей MongoDB, но я не смог найти никакого серьезного обсуждения этого алгоритма.

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

Answer 1

Деревья действительно хорошо работают с графическими базами данных, такими как neo4j: http://neo4j.org/learn/

Neo4j - это база данных графа, хранящая данные в узлах и взаимосвязях графа. Наиболее общий из структур данных, граф элегантно представляет любой тип данных, сохраняя естественную структуру домена.

В Ruby есть хороший интерфейс для деревьев: https://github.com/andreasronge/neo4j

Pacer - это библиотека JRuby, которая обеспечивает очень выразительные обходы графов. Pacer позволяет создавать, изменять и просматривать графики, используя очень быструю и эффективную для обработки потоковую обработку. Это также означает, что почти вся обработка выполняется на чистой Java, поэтому, когда речь идет об обычной проблеме выразительности Ruby и скорости, вы можете получить свой торт и съесть его тоже, это очень быстро!

https://github.com/pangloss/pacer

Неография похожа на камень neo4j.rb и предложена Роном в комментариях (спасибо Рон!)

https://github.com/maxdemarzi/neography

Answer 2

Поскольку вы рассматриваете подход SQL, вот несколько вещей, о которых стоит подумать.

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

Что база данных покупает у вас по другим подходам:

- Не нужно беспокоиться о производительности памяти / диска. Когда данные перетекают на диск, вы не сильно снижаете производительность. Для сравнения рассмотрим, что происходит, когда хэш-таблица переполняет память.

- Возможность добавлять индексы для оптимизации производительности.

- Возможность «просто» изменить путь доступа к дереву путем изменения SQL

Одна из проблем стандартного SQL состоит в том, что вы можете представить узел дерева в виде простой пары:,,. Затем, с помощью простого соединения, вы можете перемещаться между родителями и листьями. Тем не менее, соединения накапливаются по мере продвижения вверх по дереву.

Вздох. Различные базы данных имеют разные решения для этого. SQL Server имеет рекурсивные CTE, которые позволяют вам обходить дерево. У Oracle есть другой подход к древовидным структурам.

Это начинает усложняться.

Возможно, лучшим подходом является назначение «листового» идентификатора на основе иерархии в дереве. Таким образом, если это бинарное дерево, то «10011» будет узлом в правой ветви, левой ветви, левой ветви, правой ветви, правой ветви. Там вы будете хранить информацию. , , например, есть ли у него дети и все остальное. Получить родителя легко, потому что вы можете просто обрезать последнюю цифру.

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

Я полагаю, что это может быть связано с подходом "массива предков".

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

usp_tree_FetchNode (NodeId) usp_tree_GetParent (NodeId) usp_tree_NodeDelete (NodeId) usp_tree_FetchSubTree (NodeId) и т. д. и т. д.

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

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

Answer 3

Вы смотрели на камень предков ? Я использовал его для простых деревьев, но по описанию он выглядит в соответствии с вашими требованиями.