Индексы, ориентированные на вершины Titan, и метки Neo4j
Я пытался сравнить эти две технологии, когда подходил к этому, и мне было интересно, есть ли у кого-нибудь из вас опыт работы с какой-либо из них или с обеими? В основном меня интересуют показатели производительности при работе с подобными вариантами использования.
3 ответа
Соглашаясь со всем, что сказал Марко, можно пойти дальше и доказать, что в мире графовых баз локальные индексы могут (и даже должны) заменять глобальные. На мой взгляд, единственным большим преимуществом модели данных графа является то, что она позволяет вам кодировать вашу модель данных в топологию графа, получая качественные преимущества с точки зрения гибкости, простоты эволюции и производительности. Имея это в виду, я бы сказал, что ярлыки в Neo4j фактически отвлекают от всего этого; преобразование метки в узел со смежными ребрами, указывающими на источник, имеющий эту метку, в гораздо большей степени соответствует философии "схема - это график".
Конечно, если вашему движку не хватает локальных индексов, мы снова возвращаемся к проблеме с суперузлами. Но если они у вас есть (что-то, что я бы сказал, должно быть требованием для того, чтобы их называли базой данных графов), вы можете легко превратить вашу метку в узел Lи создайте отношения, указывающие на этот узел для тех вершин, которые вы хотите пометить L
v -[L]-> L
означающий, что v имеет ярлык L, Теперь, если вы хотите, чтобы в Titan он вел себя как ярлык Neo4j, просто сделайте -[L]-> отношение, чтобы быть "manyToOne" (см. ограничения мощности Титана) и создать вершинно-ориентированный индекс. Этот шаблон позволяет вам получить все, что вы могли с ярлыками и многое другое; вы можете
- эффективно использовать это как пространство имен для свойств, относящихся к этой метке
- сортировать элементы внутри одной метки
- легко вкладывать метки без потери производительности (просто используйте составной ключ)
- отделить декларацию этикетки
Lкак осуществляется доступ к элементам, помеченным им
Разница между этими двумя понятиями заключается в разнице между глобальной и локальной индексацией.
Насколько я понимаю, метки вершин Neo4j позволяют вам разбить пространство индексов по "категориям" вершин. Таким образом, O(log(|V|)) поиск сейчас O(log(|V|/c)), где c это количество категорий / меток, которые у вас есть над вашим набором вершин, и (уравнение) предполагает равное количество вершин в каждой категории. Таким образом, помощь меток вершин в вызовах глобального индекса, так как это функция V,
Затем вершинно-ориентированные индексы Титана сортируют и индексируют инцидентные ребра вершины. Стоимость нахождения определенного ребра по его метке / свойствам, связанным с вершиной, равна O(log(inc(v))), где inc(v) размер падающего ребра, установленного на вершину v, Как таковые, вершинно-ориентированные индексы являются локальными индексами, так как это функция v,
Насколько я понимаю, Neo4j не поддерживает вершинно-ориентированные индексы. Вы видите эту концепцию в настоящее время в Titan, OrientDB и TinkerGraph (… и RDF хранит сортировку таким же образом - через спаговые пары). Далее, все известные графовые базы данных поддерживают глобальные индексы, хотя (я полагаю, только Neo4j и OrientDB), поддерживают разделение набора вершин посредством концепции метки.
Опять же, предполагая, что мои предположения верны в отношении использования меток вершин в Neo4j, мы говорим о двух разных случаях использования - глобальная и локальная индексация. С точки зрения проблемы суперузлов, глобальные индексы не устраняют проблему прохождения через большую вершину, в то время как это является единственной целью локальных вершинно-ориентированных индексов.
Вы можете прочитать о проблеме суперузлов и вершинно-ориентированных индексах здесь:
http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/
Метки могут позволить себе некоторые шаблоны проектирования, которые улучшают производительность за счет снижения плотности графика. Например: они устраняют необходимость в узлах типа, которые часто могут быть довольно плотными. Метки могут быть по выбору связаны с уникальным индексом. Здесь способность индексировать свойство не нова, но способность ограничивать его уникально. Если вы ранее выполняли работу в своем приложении, вы можете ощутить некоторое повышение производительности, если база данных справится с этим. (Это, безусловно, гораздо удобнее.) Наконец, если вы не назначите уникальный индекс метке, он все равно будет проиндексирован, чтобы повысить производительность для определенных типов запросов (например, "дайте мне все узлы, имеющие метку ")
Все это говорит о том, что, хотя в некоторых случаях ярлыки могут помочь с производительностью, они были представлены больше с точки зрения простоты использования. Мы только начинаем с Neo4j 2.1, который специально предназначен для плотной работы узлов (что, как я знаю, вы ждали), наряду с другими улучшениями производительности и масштабируемости... включая удаление (для всех практических целей устранения) верхнего размера пределы.
Филипп