c# - SQLite递归查询以获取树的第一个分支

Question

我正在构建一个 Xamarin.Forms 应用程序。我的 SQLite 数据库中有一个表，它以树状形式保存分层数据。我们称之为TreeNode:

public class TreeNode
{
    [PrimaryKey]
    public int Id { get; set; }

    [Indexed]
    public int? ParentId {get; set;}
    public string ParentPath { get; set; }

    [Indexed]
    public int Sort { get; set; }
    public string Data { get; set; }
}

这个树结构包含一个巨大的菜单(+100K 节点)。树中的 sibling 有一个 Sort值来设置顺序。此属性的目的是:

我可以按任意顺序显示菜单元素。

我可以在选择节点时计算默认子树选择。

让我们关注第 2 点。考虑到 Sort，我想选择第一个分支直到第一片叶子。属性(property)。

例如，让我们看看以下表示菜单的树(从 here 中提取):

                               1,0
                                |
    ------------------------------------------------------------------
    2,1                        93,2                 4,3            5,4       
     |                          |                    |              |
------------------------  ----------------------  ----------------  ----------  
6,5  7,6  8,7  9,8  10,9  11,3  12,5  13,7  14,9  15,1  16,5  17,9  18,2  19,8
      |                                |                       |     |
  ----------                        ----------           ----------  ----------
  27,8  26,9                        25,7  24,8           23,6  22,7  21,5  20,6

对于每个节点，第一个数字是 Id , second 是对同一级别中每个兄弟的排序。因此，对于 Id = 2 的节点，Sort = 1，Id = 93，Sort = 2，等等。

我最近几天研究了递归查询，我能够从上到下遍历树(广度优先和深度优先)，我也知道如何获取给定节点的所有祖先。有很多这样的例子。

正如我在第 2 点所说，我想要的是有一个递归查询，返回第一个分支直到第一片叶子，或者将来可能有其他一些条件，但让我们坚持我只想要第一个分支到第一片叶子.在上面的例子中，我想从树中取回的节点是:

1,0
2,1
6,5

我尝试使用类似的查询:

WITH RECURSIVE depth_first_traversal
( 
    level,
    lineage,
    Id,
    ParentId,
    Sort,
    leaf 
)
AS 
( 
    SELECT CAST ( 1 AS INTEGER )    AS level,
        '00' || node.Sort        AS lineage,
        node.Id                  AS Id,
        node.ParentId            AS ParentId,
        node.Sort                AS Sort,
        node.leaf                AS leaf
    FROM node    
    WHERE node.ParentId = 1 --Is NULL 
UNION ALL
    SELECT depth_first_traversal.level + 1,
           depth_first_traversal.lineage || '-' || '00' || node.sibling_number,
           node.node_id,
           node.parent_id,
           node.sibling_number,
           node.leaf
   FROM depth_first_traversal
   INNER JOIN node
   ON node.parent_id = depth_first_traversal.node_id
   --WHERE node.leaf = 1 I was trying to play with a leaf flag to reduce the CTE size
   ORDER BY lineage
)
SELECT 
    node_id,
    level,
    lineage,
    leaf
FROM depth_first_traversal;

但是这个查询在初始选择中返回给定节点的所有分支。所以对于当前查询，它返回我:

NodeId    Leaf
2         0
6         1 <- I would like to stop recursivity here, but how?
7         0
27        1
28        1
8         1
9         1
10        1
93        0
11        1
12        1
13        0
25        1
24        1
14        1
4         0
15        1
16        1
17        0
23        1
22        1
5         0
18        0
21        1
20        1
19        1

我希望我清楚地陈述了我的情况，但总而言之，

我的问题是 :如果对同一级别的 sibling 进行了排序，我该如何进行递归查询以获取树的第一个分支？

我能想到的解决这个问题的唯一方法是对给定的结果进行后处理并使用 leaf停止遍历查询结果的标志。但这远非可取的，因为查询节点越接近树的根，查询所需的时间越长，结果集就越大。

谢谢你的帮助!

更新:我添加了创建表和插入语句:

CREATE TABLE node ( 
   Id          INTEGER,
   ParentId    INTEGER REFERENCES node ( node_id ),
   Sort        INTEGER,
   leaf        BOOL,
PRIMARY KEY ( Id ) );

INSERT INTO node VALUES (  1,  NULL,             9, 0 );
INSERT INTO node VALUES (      2,  1,             1, 0 );
INSERT INTO node VALUES (          6,  2,             5, 1 );
INSERT INTO node VALUES (          7,  2,             6, 0 );
INSERT INTO node VALUES (             27,  7,             8, 1 );
INSERT INTO node VALUES (             26,  7,             9, 1 );
INSERT INTO node VALUES (          8,  2,             7, 1 );
INSERT INTO node VALUES (          9,  2,             8, 1 );
INSERT INTO node VALUES (         10,  2,             9, 1 );
INSERT INTO node VALUES (     93,  1,             2, 0 );
INSERT INTO node VALUES (         11, 93,             3, 1 );
INSERT INTO node VALUES (         12, 93,             5, 1 );
INSERT INTO node VALUES (         13, 93,             7, 0 );
INSERT INTO node VALUES (             25, 13,             7, 1 );
INSERT INTO node VALUES (             24, 13,             8, 1 );
INSERT INTO node VALUES (         14, 93,             9, 1 );
INSERT INTO node VALUES (      4,  1,             3, 0 );
INSERT INTO node VALUES (         15,  4,             1, 1 );
INSERT INTO node VALUES (         16,  4,             5, 1 );
INSERT INTO node VALUES (         17,  4,             9, 0 );
INSERT INTO node VALUES (             23, 17,             6, 1 );
INSERT INTO node VALUES (             22, 17,             7, 1 );
INSERT INTO node VALUES (      5, 1,              4, 0 );
INSERT INTO node VALUES (         18,  5,             2, 0 );
INSERT INTO node VALUES (             21, 18,             5, 1 );
INSERT INTO node VALUES (             20, 18,             6, 1 );
INSERT INTO node VALUES (         19,  5,             8, 1 );

Answer 1

诀窍是递归地选择具有最小排序值的同级行 - 它是当前父行的最左边的子行:

WITH cte AS
 (SELECT Id, ParentId, Sort, 0 as Depth FROM node WHERE ParentId IS NULL
 UNION ALL
  SELECT c.Id, c.ParentId, c.Sort, p.Depth + 1
  FROM node AS c
  JOIN cte AS p ON c.ParentId = p.Id
  WHERE c.Sort = (SELECT min(Sort) FROM node AS t WHERE t.ParentId = p.Id))
SELECT * FROM cte ORDER BY Depth;

Id          ParentId    Sort        Depth     
----------  ----------  ----------  ----------
1                       9           0         
2           1           1           1         
6           2           5           2