Titan如何使用HBase/Cassandra实现恒定时间查找？
xupengkunwudi163899 发布于 2022-12-19 21:11在第6章的O'Reilly书籍"图形数据库"中,它是关于Neo4j如何存储图形数据库的,它说:
要理解为什么本机图处理比基于重索引的图更有效,请考虑以下内容.根据实现,索引查找可以是算法复杂度中的O(log n),而O(1)则用于查找直接关系.为了遍历m个步骤的网络,索引方法的成本(O(m log n))使得使用无索引邻接的实现的O(m)成本相形见绌.
然后解释说Neo4j通过将所有节点和关系存储为固定大小的记录来实现这种恒定时间查找:
对于固定大小的记录和类似指针的记录ID,只需通过追踪数据结构周围的指针即可实现遍历,这可以以非常高的速度执行.为了遍历从一个节点到另一个节点的特定关系,数据库执行几个廉价的ID计算(这些计算比搜索全局索引便宜得多,因为如果在非图形本机数据库中伪造图形,我们必须这样做)
最后一句话触发了我的问题:使用Cassandra或HBase作为存储后端的Titan如何实现这些性能提升或弥补它？
-
当数据在同一JVM中的内存中时,Neo4j仅实现O(1).当数据在磁盘上时,由于磁盘上的指针追逐,Neo4j很慢(它们的磁盘表示很差).
当数据在同一JVM中的内存中时,Titan仅实现O(1).当数据在磁盘上时,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-图形/
2022-12-19 21:20 回答
寒江大哥_599
京公网安备 11010802041100号