postgresql - AgensGraph-Btree VS Neo4j-IndexFree

Question

为了处理数据的有效手段，Neo4j 表示他们以“无索引邻接”的方式搜索图数据。但是，我知道AgensGraph使用PostgreSQL的“Btree”方式进行查询

与“无索引邻接”相比，使用 PostgreSQL 的“Btree”有什么好处？

Answer 1

免责声明：我领导 AgnsGraph 的开发

Neo4j 使用固定大小的数组来存储有关节点和关系的信息。该结构提供的好处之一是它可以通过计算 ID 的乘积和元素的固定大小来找到文件中具有其内部 ID 的节点或关系的位置。所以 Neo4j 不需要 Btree 结构（在 RDBMS 中很流行），他们坚持 Neo4j 为图形数据提供“无索引邻接”。

相反，AgensGraph 用于查找顶点（节点）或边（关系）。所以人们可能会觉得 AgnsGraph 的方法没有 Neo4j 快，因为与 Neo4j 的 O(1) 相比，渐近复杂度是 O(log n)。

从理论上讲，这是真的。但实际上，有几点需要考虑。首先，在 RDBMS 中，日志的基础非常大。所以 Btree 的高度 (log n) 非常小（大多数情况 <= 3）并且 Btree 的内部页面大多缓存在内存中。

更重要的是，考虑到在处理图遍历时需要真正的磁盘 I/O，实际上并不是那么简单。

当查询找到与某个顶点（其 ID 为 v1）相邻的边时，在 AgnsGraph 中搜索 Btree，它可以通过 Btree 的一次循环检索所有相邻边的 ID，并依次读取 Btree 的叶子条目。边缘聚集在 Btree 的叶子条目中，因此可以快速检索相邻边缘。虽然有多个相邻边，但 AgensGraph 需要查找 Btree。但在 Neo4j 中，关系可以存储在固定大小数组的不同页面中。相邻关系使用双向链表链接。因此，如果它们分散在文件中，则需要更多随机 I/O。

实际上，我们发现 AgensGraph 比 Neo4j 更快，并且即使在多客户端会话中更新效率也更高，因为 Btree 也针对这些并发访问进行了优化。

Answer 2

据我了解，“无索引邻接”意味着 Neo4j 可以在恒定时间 O(1) 内获取节点的相邻元素。

我不知道 AgnsGraph 是如何工作的，但是在 BTree 中获取元素是 O(log n)。