Titan如何使用HBase/Cassandra实现恒定时间查找？

Question

在第6章的O'Reilly书籍"图形数据库"中,它是关于Neo4j如何存储图形数据库的,它说:

要理解为什么本机图处理比基于重索引的图更有效,请考虑以下内容.根据实现,索引查找可以是算法复杂度中的O(log n),而O(1)则用于查找直接关系.为了遍历m个步骤的网络,索引方法的成本(O(m log n))使得使用无索引邻接的实现的O(m)成本相形见绌.

然后解释说Neo4j通过将所有节点和关系存储为固定大小的记录来实现这种恒定时间查找:

对于固定大小的记录和类似指针的记录ID,只需通过追踪数据结构周围的指针即可实现遍历,这可以以非常高的速度执行.为了遍历从一个节点到另一个节点的特定关系,数据库执行几个廉价的ID计算(这些计算比搜索全局索引便宜得多,因为如果在非图形本机数据库中伪造图形,我们必须这样做)

最后一句话触发了我的问题:使用Cassandra或HBase作为存储后端的Titan如何实现这些性能提升或弥补它？

Answer 1

当数据在同一JVM中的内存中时,Neo4j仅实现O(1).当数据在磁盘上时,由于磁盘上的指针追逐,Neo4j很慢(它们的磁盘表示很差).

当数据在同一JVM中的内存中时,Titan仅实现O(1).当数据在磁盘上时,Titan比Neo4j更快,因为它具有更好的磁盘表示.

因此,当人们说O(1)它们所处的内存层次结构的哪个部分时,了解它很重要.当你在一个JVM(单机器)中时,它很容易快速,因为Neo4j和Titan都展示了它们各自的缓存引擎.如果无法将整个图形放在内存中,则必须依赖智能磁盘布局,分布式缓存等.

有关更多信息,请参阅以下两篇博文:

为了扩展,Neo4j不支持所有遍历的O(1).假设边缘谓词.为了得到最近的顶点v的朋友在Neo4j中花费O(| out(v)|)(即以顶点为中心的线性扫描).为什么？因为Neo4j不会将其数据排序在内存中(也不在磁盘上).Neo4j必须遍历v的所有传出友元边缘以确定哪一个具有最新的时间戳.在Titan中,这(可以)是O(1)操作.您可以在这里了解更多信息:http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/这一进步是通过Titan在磁盘和内存中实现的. (3认同)
Neo4j总是算法O(1),因为它是一个id*偏移计算,产生一个记录.在机械方面,与任何疲惫的存储方法一样,路径越来越短.点击一个缓存的对象,然后将数据库到磁盘的路径短路并返回; 点击冷缓存然后你会去磁盘.这仍然是O(1).没有索引或其他O(log n)或更差的搜索要执行.这是图形本地一直到堆栈的巨大好处. (2认同)