答案是不幸的:你的考虑在每一点上都是完全正确的。你必须将节点 (Vertices) 存储在一个表中,并且 Edges 引用 FromNode 和 ToNode 来将图形数据结构转换为关系数据结构。而且你也是对的,这最终会导致大量的查找,因为你无法将其分区为子图,可能会立即被查询。你必须从 Node 到 Edge 遍历到 Edge...

重点是...

关系，面向图形，面向对象，基于文档是满足不同要求的不同类型的数据结构。这就是为什么出现了这么多不同的 NoSQL 数据库（其中大多数是简单的文档存储），因为以关系方式组织大数据根本没有意义。

备选方案 1-面向图形的数据库

但是也有面向图的 NoSQL 数据库，这使得图数据模型成为像OrientDB这样的一流公民，我现在正在玩一点。关于它的好处是，尽管它将数据保存为图，但它仍然可以以关系甚至面向对象或面向文档的方式使用（即通过使用普通的旧 SQL 查询）。尽管如此，Traversing the graph是确保获取数据的最佳方法。

备选方案 2-使用内存中的图形

当涉及到快速路由时，像Graphpper这样的路由框架在内存中构建了完整的 Graph（数十亿个节点）。由于 Graphpper 使用其 GraphStore 的 MemoryMapped 实现，因此甚至可以在只需要一些 MB 内存的 Android 设备上运行。启动时将完整的图从数据库读取到 memor 中，然后在那里进行路由，因此您无需查找数据库。

我遇到了同样的问题，并决定最终使用以下结构，这需要 2 个数据库查询，那么其余的工作都在内存中：

将节点存储在表中，并使用每个节点记录引用图形：

Table Nodes
id  | le | graph_id
---------------------
105 | node1 | 2
106 | node2 | 2

还可以将边缘存储在另一个表中，并再次使用每个边缘引用这些边缘所属的图形：

Table Edges
id | from_node_id | to_node_id | graph_id
-----------------------------------------
1  | 105          | 106        | 2
2  | 106          | 105        | 2

用一个查询获取所有节点，然后用另一个查询获取所有边。

现在构建您的首选方式来存储图形（例如，邻接列表）并继续您的应用程序流。

添加到前面的答案的事实，MS SQL Server 添加support for Graph Architecture starting with 2017。

It follows the described pattern of having Nodes and Edges tables (which suld be created with special "AS NODE" and "AS EDGE" keywords).

它还引入了新的 MATCH 关键字“以支持模式匹配和遍历图形”，如下所示（friend 是下面示例中edge表的名称）：

SELECT Person2.name AS FriendName
FROM Person Person1, friend, Person Person2
WHERE MATCH(Person1-(friend)->Person2)
AND Person1.name = 'Alice';

还有一组非常好的文章on SQL Server Graph Databases on redgate Hub。

我不同意这里的其他帖子，如果你有特殊类的图形有限制，你通常可以摆脱更专业的设计（例如，每个顶点的边数量有限，只需要遍历一种方式等）。

但是，对于存储任意图，关系数据库做出了非常好的权衡，在几乎所有情况下都表现良好。此外，数据需求往往会随着时间的推移而变化，关系数据库让您可以轻松地更改存储和查找，而无需更改数据表示。

让我们来看看你的设计：

一个表的顶点（ID，数据）

一个表的边缘（startId，endId，数据）

首先观察存储是有效的，因为它与要存储的数据成正比。如果我们有 10 个顶点和 10 条边，我们存储 20 条信息。

现在，让我们看看 lookup，假设我们在顶点 id 上有一个索引，我们可以在至少log(n)中查找我们想要的任何数据（根据索引可能更好）。

给定一个节点告诉我离开它的边缘

给定一个节点告诉我进入它的边缘

给定一个边缘告诉我它来自或进入的节点

这是你需要的所有基本查询。

现在假设您有一个“图形数据库”，其中存储了离开每个顶点的边的列表。这使每个顶点的大小可变。遍历起来更容易。但是，如果要遍历另一个方向怎么办？现在，您还可以存储进入每个顶点的边的列表。现在，您有了该信息的两个副本，数据库（或开发人员）必须做很多工作，以确保它们永远不会不同步。

O (log (n)) vs O (1)

关系数据库索引通常以排序的形式存储数据，或者正如其他人所指出的那样，也可以使用哈希表。

首先请注意，大 oh 衡量的是可伸缩性，而不是性能。对于小数据集，哈希可能比许多循环要慢。即使哈希O(1)更好，二进制搜索O(log2)也非常好。您可以在 30 个步骤中搜索十亿条记录！此外，它是缓存和分支预测器友好的。