Как Titan обеспечивает постоянный поиск по времени с помощью HBase / Cassandra?
В книге О'Рейли "Графовые базы данных" в главе 6, которая рассказывает о том, как Neo4j хранит графическую базу данных, говорится:
Чтобы понять, почему обработка собственных графов намного эффективнее, чем графики, основанные на интенсивной индексации, рассмотрим следующее. В зависимости от реализации, поиск индекса может быть O(log n) в алгоритмической сложности по сравнению с O(1) для поиска непосредственных отношений. Чтобы пересечь сеть из m шагов, стоимость индексированного подхода, равная O(m log n), превосходит стоимость O(m) для реализации, в которой используется смежность без индекса.
Затем поясняется, что Neo4j выполняет поиск в постоянном времени, сохраняя все узлы и отношения в виде записей фиксированного размера:
С записями фиксированного размера и идентификаторами записей, похожими на указатели, обходы осуществляются просто путем поиска указателей вокруг структуры данных, что может быть выполнено с очень высокой скоростью. Чтобы проследить определенное отношение от одного узла к другому, база данных выполняет несколько дешевых вычислений идентификатора (эти вычисления намного дешевле, чем поиск по глобальным индексам, что мы должны были бы сделать, если имитировать граф в неграфовой собственной базе данных)
Последнее предложение вызывает у меня вопрос: как Titan, использующий Cassandra или HBase в качестве бэкэнда хранилища, может добиться такого повышения производительности или восполнить его?
2 ответа
Neo4j достигает O(1) только тогда, когда данные находятся в памяти в той же JVM. Когда данные находятся на диске, Neo4j работает медленно из-за погони за указателем на диске (у них плохое представление на диске).
Titan достигает O(1) только тогда, когда данные находятся в памяти в той же JVM. Когда данные находятся на диске, Titan работает быстрее, чем Neo4j, потому что он имеет лучшее представление на диске.
Пожалуйста, смотрите следующий пост в блоге, который количественно объясняет вышесказанное: http://thinkaurelius.com/2013/11/24/boutique-graph-data-with-titan/
Таким образом, важно понимать, когда люди говорят O(1), в какой части иерархии памяти они находятся. Когда вы находитесь в одной JVM (одной машине), легко быть быстрым, как Neo4j и Titan демонстрируют с соответствующим кэшированием. двигатели. Когда вы не можете поместить весь график в память, вы должны полагаться на интеллектуальное расположение дисков, распределенный кеш и тому подобное.
Пожалуйста, смотрите следующие два сообщения в блоге для получения дополнительной информации:
http://thinkaurelius.com/2013/11/01/a-letter-regarding-native-graph-databases/ http://thinkaurelius.com/2013/07/22/scalable-graph-computing-der-gekrummte-graph/
OrientDB использует аналогичный подход, когда отношения управляются без индексов (смежность без индекса), а с прямыми указателями (ССЫЛКАМИ) между вершинами. Это как в указателях памяти, но на диске. Таким образом, OrientDB достигает O(1) при обходе в памяти и на диске.
Но если у вас есть вершина "Город" с тысячами ребер к вершинам "Персона", и вы ищете всех людей с возрастом> 18, то OrientDB использует индексы, потому что запрос задействован, поэтому в данном случае это O (журнал N).