SQLite查询树形表中无下级data的node节点实现方法

场景与问题 #

业务中树形结构数据存储在SQLite表treeTable中，表核心字段如下：

• id：记录唯一主键
• name：记录展示名称
• type：记录类型，仅支持两个取值：node（中间/叶子节点）、data（业务数据）
• depth：记录所在树的层级深度
• parentId：父记录ID，为空表示是根节点，通过该字段实现父子层级关联

筛选目标：返回所有type = 'node'，且以该节点为根的任意层级子树中，完全不存在type='data'记录的节点。参考示例数据集，符合条件的节点为id=6、7、8的节点。

现有实现仅能筛选出树最深处无任何子记录的叶子node节点，SQL如下：

SELECT id
FROM treeTable
WHERE type = 'node'
    AND id NOT IN
        (SELECT DISTINCT parentId
        FROM treeTable
        WHERE parentId IS NOT NULL)

该实现存在漏判：类似id=6的节点，虽然存在子node节点，但整棵子树没有任何data类型记录，本应被返回却无法被现有逻辑筛选出来。

最优实现方案（支持Android API 21及以上） #

Android从API 21开始内置的SQLite版本为3.8.3以上，支持递归CTE语法，用反向追溯的递归逻辑实现，性能远高于逐节点向下遍历子树的方案。
核心逻辑：只要一个node节点是任意一条data记录的祖先节点，它就不符合要求；反之，所有不在data记录祖先链上的node节点，子树必然没有任何data记录。
具体SQL如下：

WITH RECURSIVE invalid_node AS (
    -- 锚点：所有data记录的直接父节点，属于不符合要求的节点
    SELECT DISTINCT parentId AS node_id
    FROM treeTable
    WHERE type = 'data' AND parentId IS NOT NULL

    UNION

    -- 递归向上：不符合要求节点的所有上层父节点，同样不符合要求
    SELECT t.parentId AS node_id
    FROM treeTable t
    JOIN invalid_node iv ON t.id = iv.node_id
    WHERE t.parentId IS NOT NULL
)
-- 筛选所有type为node、且不在无效节点列表中的记录
SELECT id
FROM treeTable
WHERE type = 'node'
AND id NOT IN (SELECT node_id FROM invalid_node);

该写法可以正确覆盖所有场景：

• 没有任何子记录的叶子node节点（比如id=7、8），因为不是任何data的祖先，会被正常返回
• 有子node节点、但子树全是node无data的节点（比如id=6），同样不在data的祖先链上，会被正常返回
• 任意层级子节点存在data的node节点，都会被标记为invalid_node被排除

低版本兼容方案（API <21） #

如果需要兼容API 21以下的极老设备，SQLite不支持递归CTE，可以在业务层做遍历校验，千级以内数据量性能无压力：

1. 全量查询表中所有记录，在内存中构建id -> 子节点列表的映射关系
2. 从树的叶子节点（没有子节点的记录）开始向上做后序遍历，给每个节点打has_data标记：
   • 记录本身type为data时，has_data = true
   • 记录type为node时，只要任意一个直接子节点的has_data = true，当前节点has_data = true；否则has_data = false
3. 遍历完成后，所有type='node' AND has_data = false的节点就是目标结果

内容的提问来源于stack exchange，提问作者Daniel Schröder