图数据库vs关系数据库时空复杂

Question

图和关系数据库横向的时间复杂度是多少？

Answer 1

O（N）for both？

图形DB在其核心有一个表格（https://stackoverflow.com/a/2968931/623735）。 RDB在处理表格方面已经发展得非常高效。因此，具有持久存储的大多数大型GDB使用RDB来存储节点表。 GDB只是将所有常规数据表行的id堆栈到一个“节点”表（为了有效索引而分组和排序）中。 GDB的神奇之处在于用于行走/探索图形的高效算法。

所以我不认为GDB真的在两个表（遍历）上进行连接，就像RDBMS对同一类数据上的同一种查询所做的那样。一个GDB只是从一个节点（节点表中的行）走到另一个节点（以链表的方式）。一旦找到您查询的节点，就会对节点属性表执行一次“遍历”以检索您查询的信息（名称，排名，序列号;）。

Answer 2

也许你会发现这篇文章“Efficient graph management based on bitmap indices”有帮助。在第4部分称为实验结果中，作者测试了mysql，图数据库DEX和Neo4j以及列存储MonetDB中的相同查询（包括查询1和2中的遍历）。

对于某个遍历操作，DEX（图形数据库）和mysql之间的区别是120秒（DEX）和12小时执行（mysql）次。

您还可以阅读位图存储的有趣方法。

Answer 3

更快，计算机或代数？

关系模型是思考有关数据的方式，一种方式代表数据到用户。它说没有什么关于实现。询问关系数据库的时间复杂度就像询问时间复杂度为f(x)。

没有SQL DBMS我已经使用元组的线性数组来存储数据。他们都使用某种树：B-树，B +树。一棵树是一张图。 Ergo，物理图形数据库声称的优势是基于，好吧，如果你问我什么都没有。

SQL DBMS在过去几年中增加了对所谓递归查询的支持。这些查询的有效执行没有理论上的问题，我已经看到它完成了。但是查询优化器必须支持它才能正常工作，如果开源项目在这方面有一些工作要做，我不会感到惊讶。

在选择你的武器，不要问关于“关系数据库”，但关于具体的实现递归查询处理的支持，

小心假对称的，虽然。 “图表数据库”中缺少一个相当长的列表。例如，关系模型基于代数，这是SQL基于（大部分，松散地）的内容。图论缺乏这样的代数，因此也是一种很好的操作语言。强制执行和交易也有类似的情况。

Answer 4

图数据库的一个（也许是）关键点是不必为遍历做任何连接。