为什么图形数据库比 RDB 在图形遍历方面更快?

Question

我读过几篇文章(像这样(，指出由于无索引邻接，在运行图遍历算法时，图形数据库本质上比RDB更快。但是，我很难理解它的理论理由。在我看来，如果您构造哈希索引邻接表，您应该达到相同的复杂性性能。

例如，使用具有 2 个表的 RDB 查找一个人的朋友(给定人员 ID(：人和友谊

1(定位朋友：O(m( - 其中m是朋友的数量。
2(对于每个朋友Id，定位在人：O(1(总计：O(m(

在图形数据库中，这应该是相同的，不是吗？

Answer 1

不，查询在 RDBMS 中的执行方式与在图形数据库中的执行方式不同。

1. 您给出的示例是查找给定人员的朋友，这是一个单跳查询(以图形术语表示(，并且在两种数据库中都非常容易。

   但是，如果要执行 n 跳查询(n> 3(，则可以在 RDBMS 中使用子查询或联接，性能将取决于优化器。

   下面是一个示例：

   假设我们有表类，字段id(主键(和name，学生有字段id(主键(，name和class_id。

为了找到 id 为 2 的类名，以及对应的学生，我们需要在两个表之间连接班级和学生

SELECT c.name as c_name, s.name as s_name 
FROM class as c 
LEFT JOIN student as s 
ON c.id = s.class_id 
WHERE c.id = 2;

解释查询： 表中说明的查询

将扫描整个学生表以找到 class_id=2。

当然，我们可以在学生class_id列上创建一个索引。

索引表

它读取student_class索引以获取指向物理的指针 行，然后读取记录，因为它是非聚集索引。

在图形数据库中，数据被建模为节点和连接。

图形数据库模型

要查找 id 为 2 的班级名称以及相应的学生， 只需获取类节点并在select上向后遍历即可 连接。并避免联接索引查找性能问题。

2. 如果你想找到最短路径和两点之间的所有可能的路径(但你不知道查询有多少跃点(，那么使用 RDBMS 会有很多麻烦。查询会很长。LDBC有一些分别使用SQL，GQL(Cypher(和SparQL的好案例。不幸的是，我没有发现不同语言之间的运行时差异。

很难

3. 用RDBMS进行像LPA(标签传播算法(和页面排名算法这样的图计算。但是在某些(大多数(图形DBMS中这样做会容易得多