SQLite递归查询获取树的第一个分支

Question

我正在构建一个 Xamarin.Forms 应用程序。我的 SQLite 数据库中有一个 table，它以树形保存分层数据。我们称它为树节点：

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 个节点）。树中的兄弟姐妹有一个 Sort 值来设置顺序。属性的目的是：

我可以按任意顺序显示菜单元素。
当节点被 selected 时，我可以计算默认子树 selection。

让我们关注第 2 点。考虑到 Sort 属性.

，我想 select 第一个分支直到第一个叶子

作为示例，让我们看一下以下表示菜单的树（摘自 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，第二个是同一级别中每个兄弟的排序。因此，对于 Id = 2 的节点，Sort = 1，Id = 93 的 Sort = 2，等等

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

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

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;

但是这个查询 returns 我在初始 select 中从给定节点开始的所有分支。所以对于当前查询它 returns me:

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

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

我的问题是：如果同一级别的兄弟姐妹已排序，我如何进行递归查询以获得树的第一个分支？

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

感谢您的帮助！

更新：我添加了创建 table 和插入语句：

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

诀窍是递归地 select 仅具有最小排序值的兄弟行 - 这是当前父行的最左边的子行：

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

SQLite递归查询获取树的第一个分支

SQLite recursive query to get first branch of tree

c#

sqlite

tree

recursive-query

xamarin.forms