Модель данных для древовидной структуры (файловая система): модель документа и модель графа

Question

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

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

имея эти требования, я разделил проблему на 2 задачи:

1. смоделировать структуру рекурсивных элементов для поиска потомков / поддеревьев потомков
2. смоделировать структуру элемента для поиска по свойству элементов

Теперь возможности nosql schema free - это хорошая функция для хранения различных свойств для каждого файла, и это хорошо для пункта 2.

Вместо этого у меня есть некоторые сомнения по поводу пункта 1 о плюсах / минусах использования базы данных документов (например, mongodb) с одной коллекцией элементов и материализованного шаблона проектирования пути, или использования базы данных графов (например, arangodb) с 2 коллекциями: элементы для data (коллекция документов) и itemsParents для отношения родитель-потомок (коллекция ребер) и функция обхода графа.

Есть ли преимущества в производительности при использовании графической базы данных для моих требований?

Обход графа более эффективен по сравнению с материализованным фильтром путей для выполнения моей задачи?

Если да, можете ли вы объяснить мне, почему?

Спасибо

Answer 1

Графическая база данных, безусловно, будет отличным выбором для иерархической структуры, такой как файловая система. Говоря конкретно о Neo4j, у вас может быть такая схема:

(:Folder)-[:IN_FOLDER]->(:Folder)
(:File)-[:IN_FOLDER]->(:Folder)

Найти файл или папку так же просто, как следующий Cypher:

MATCH (file:File {path: '/dir/file'})
RETURN file

Чтобы найти все файлы / папки непосредственно в папке:

MATCH (folder:Folder {path: '/dir'})<-[:IN_FOLDER]-(file_or_folder)
RETURN file_or_folder

Если вы хотите найти все файлы / папки рекурсивно, вы можете сделать:

MATCH (folder:Folder {path: '/dir'})<-[:IN_FOLDER*1..5]-(file_or_folder)
RETURN file_or_folder

1..5 регулирует глубину (от одного до пяти уровней), которую вы ищете.

Для всего этого вы хотите индекс на path свойство как Folder а также File этикетки. Конечно, вам не нужно делать это таким образом, в зависимости от вашего варианта использования.

Причина, по которой Neo4j может быть намного быстрее в этом случае, заключается в том, что, как только вы найдете узел на диске, отношения могут быть пройдены с помощью всего нескольких обращений к файлу, в отличие от поиска по всей таблице или индексу для каждого прыжка. Я рекомендую ознакомиться с бесплатной книгой Graph Databases от O'Reilly для получения подробной информации о внутренностях Neo4j.

Answer 2

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

Вы бы получили

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

1.-4. является наилучшим возможным, потому что сложность не может быть лучше, чем размер набора результатов.

Позвольте мне объяснить аргументы производительности более подробно:

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

Случай 3. (прямые потомки) быстрее с базой данных графа, поскольку он "находит всех прямых соседей" как очень быстрый примитив. Если вы полагаетесь на материализованный путь и отсортированный индекс, вы не можете получить прямых потомков с запросом диапазона, поэтому он будет медленнее.

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

Преимущество многомодельной базы данных состоит в том, что вы можете объединить преимущества двух подходов (3. и 4.), которые вы предлагаете, в одном хранилище данных.

Одной из возможностей такой базы данных является база данных ArangoDB.

Отказ от ответственности: я один из основных разработчиков.