AgensGraph-Btree VS Neo4j-IndexFree

Question

为了有效处理数据,Neo4j表示他们以"无索引邻接"的方式搜索图形数据.但是,我知道AgensGraph使用PostgreSQL的"Btree"方式进行查询

与"无索引邻接"相比,使用PostgreSQL的"Btree"有什么好处？

Answer 1

免责声明:我领导AgensGraph的发展

Neo4j使用固定大小的数组来存储有关节点和关系的信息.该结构提供的一个好处是,它可以通过计算ID的乘积和元素的固定大小来查找文件中的节点或关系的位置及其内部ID.所以Neo4j不需要Btree结构(在RDBMS中很流行),他们坚持认为Neo4j为图形数据提供了"无索引邻接".

相反,AgensGraph用于查找顶点(节点)或边缘(关系).因此人们可能会认为AgensGraph的方法不如Neo4j快,因为与Neo4j的O(1)相比,渐近复杂度为O(log n).

从理论上讲,这是事实.但实际上,有几点需要考虑.首先,在RDBMS中,日志的基础非常大.因此Btree(log n)的高度非常小(大多数情况<= 3),Btree的内部页面大多缓存在内存中.

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

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

实际上,我们发现AgensGraph比Neo4j更快,即使在多客户端会话中它也更有效,因为Btree也被开发为针对这些并发访问进行了优化.