graph - 如何在关系数据库中持久化图形数据结构？

Question

我已经考虑过创建一个 Vertices 表和一个 Edges 表，但是在内存中构建图和遍历子图是否需要大量查找？我想避免过多的数据库读取。有没有其他方法可以持久化图形？

旁注:我听说过 Neo4j，但我的问题实际上是如何从概念上表示标准数据库中的图形。不过，我对一些 NoSQL 解决方案(如 mongodb)持开放态度。

Answer 1

不幸的是，答案是:您的考虑在每一点上都是完全正确的。您必须将节点(顶点)存储在一张表中，并且边引用 FromNode 和 ToNode 才能将图形数据结构转换为关系数据结构。而且您也是对的，这最终会导致大量查找，因为您无法将其划分为可能会立即查询的子图。您必须从节点到边缘遍历到节点到边缘再到节点......等等(递归地，而 SQL 正在使用集合)。

重点是...

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

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

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

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

说到快速路由，路由框架如 Graphhopper在内存中建立完整的图(十亿个节点)。由于 Graphhopper 使用其 GraphStore 的 MemoryMapped 实现，因此它甚至适用于仅需要一些 MB 内存的 Android 设备。完整的图形在启动时从数据库读取到内存中，然后在那里完成路由，因此您无需查找数据库。