Memgraph中从任意节点高效查找树的根：路径验证、最优方法及性能对比

1. 你创建的路径是否正确？ #

你当前的Cypher语句创建的关系方向是父节点指向子节点（(父节点:Node)-[:PARENT]->(子节点:Node)），因为n1.id = n2.id - 1意味着n1是n2的前序ID，最终生成的是id=0→id=1→id=2→…→id=100000的链式结构。

但如果你的需求是从子节点沿父指针找根，这个关系方向是完全反向的——正确的关系应该是子节点指向父节点（(子节点)-[:PARENT]->(父节点)），否则你需要反向遍历边才能找到父节点，这会大幅降低查询效率。

2. 查找根节点的最优方法 #

方法一：修正关系方向后使用无出边判断（推荐） #

首先修正数据创建语句，让子节点指向父节点：

CREATE INDEX ON :Node(id);
FOREACH (i IN range(0, 100000) | CREATE (:Node {id: i}));
MATCH (child:Node), (parent:Node) 
WHERE child.id = parent.id + 1 
CREATE (child)-[:PARENT]->(parent);

此时，根节点（id=0）没有任何PARENT出边（因为没有比它ID更小的节点），查询时只需找到从id=1出发，沿PARENT边遍历到没有出边的节点即可：

MATCH path=(n:Node {id:1})-[:PARENT*]->(root:Node)
WHERE NOT (root)-[:PARENT]->()
RETURN root;

Memgraph对这种正向遍历做了优化，结合已创建的id索引，能快速定位起始节点并沿边深度遍历到根，性能接近最优。

方法二：不修改数据，反向遍历边 #

如果不想重新创建数据，可以反向遍历PARENT边（即找指向当前节点的父节点），查询语句如下：

MATCH path=(root:Node)<-[:PARENT*]-(n:Node {id:1})
WHERE NOT ()<-[:PARENT]-(root)
RETURN root;

不过这种反向遍历的性能略逊于正向遍历，因为Memgraph的边存储是基于正向关系优化的。

方法三：使用递归查询（便于和PostgreSQL对比） #

Memgraph支持Cypher的递归查询，写法和PostgreSQL的WITH RECURSIVE逻辑一致，便于你直接对比两者性能：

WITH RECURSIVE traversal AS (
  SELECT n AS node FROM :Node n WHERE n.id = 1
  UNION ALL
  SELECT parent FROM traversal t, (t)<-[:PARENT]-(parent:Node)
)
SELECT node FROM traversal t WHERE NOT ()<-[:PARENT]-(t.node);

3. 你之前的方法性能差的原因 #

你之前的查询match (n:Node)-[:PARENT*]->(root:Node) WHERE n.id=1 AND root.is_child = 'no' RETURN n, root存在两个致命问题：

• 关系方向完全错误：你在沿PARENT边正向遍历，实际是在找id=1的子节点链，而非父节点链，遍历路径长度达到了10万级；
• 无限制变长路径遍历：[:PARENT*]会遍历所有可能的子节点路径，直到找到标记is_child='no'的节点，产生了大量无效计算，直接导致耗时飙升。

内容的提问来源于stack exchange，提问作者mwpb