利用 SQLite 的递归表处理树型结构的数据

前言

众所周知，SQLite 是一种基于关系型的数据库系统，而关系型的数据库是一种一维的结构，它的表可以视作一种记录的线性表。而在实践中，树型结构也是非常常见的，为了能将树型结构的数据被 SQL 语言进行有效的查询和管理，SQLite 的 with 从句提供了一种递归语法，可以有效地对树和图等结构进行查询。

示例

下图是曹魏世系表，是一株典型的家谱树结构。其中曹操是根结点，当过皇帝的以圆表示，数字是当皇帝的顺序。

曹魏世系表

上图的数据可以用如下的表来表示，其中 father 指向自己父亲的 id。

id	name	father	emperor_no
1	曹操
2	曹植	1
3	曹丕	1	1
4	曹彰	1
5	曹冲	1
6	曹宇	1
7	曹楷	4
8	曹芳	7	3
9	曹睿	3	2
10	曹霖	3
11	曹髦	10	4
12	曹奂	6	5

如果我们要求获取曹操所有的后代里，当过皇帝的人，并且按照代际顺序输出（子代->孙代->曾孙代）。这便是一个典型的广度优先搜索（Breadth First Search），该功能可用以下 SQL 语句进行查询：

with recursive
    cao as (
        select * from family where name = '曹操'
        union all
        select family.* from cao join family on cao.id = family.father
    )
select * from cao where emperor_no is not null;

SQLite 递归建表的核心是一条以 union(all) 连接的复合查询语句，其中 union 前面的语句构成递归搜索的起始数据，union 后的语句构成递归查询的生成语句（取出当前节点的所有子节点）。如果写过基于队列来对树形结构进行广度优先搜索，那么会对 SQLite 这一语法很容易理解：

1. 在队列里产生初始数据
2. 取出队列中的元素，输出该元素
3. 将2步取出的元素，获取它的所有子节点，放入队列
4. 继续进行第2步，直到队列为空

回到上面的例子，这一句就是取出根节点，也就是曹操

select * from family where name = '曹操'

而后面这一句，就是取出当前遍历节点的所有子节点，注意：虽然最终所有的输出结果都会到表cao里，但在生成语句里，cao指代的只是当前的遍历节点，它在生成语句里，只有一行数据。

select family.* from cao join family on cao.id = family.father

执行最终的搜索语句，结果如下：

id	name	father	emperor_no
3	曹丕	1	1
9	曹睿	3	2
12	曹奂	6	5
11	曹髦	10	4
8	曹芳	7	3

深入内容

性能优化

对于普通的用 union all 构造的递归查询，虽然从逻辑上，SQLite 似乎是把递归搜索出来的结果放在一个新的表里，但由于 SQLite 有强大的查询优化器，它这张递归的输出结果是直接输出的，不会暂存数据，最终只会消耗较少的内存，而 union需要去重，就只能被迫临时存储表结果，这样会带来较多的内存消耗，因此如果没有什么特别的必要，应尽可能使用 union all 而不是 union。

深度优先搜索

在默认的情况下，由于 SQLite 构造递归的模型是基于队列作为中间的遍历缓存结构，因此对于树型结构，最终的遍历顺序是广度优先，如果需要深度优先搜索的结果，可以在额外增加一个表示层次的字段，然后加上一个order by语句，以该字段降序排列即可。SQLite 的官方文档里有讨论：Controlling Depth-First Versus Breadth-First Search Of a Tree Using ORDER BY 。

限制递归表长度

在生成语句里加上 limit 从句即可。在 SQLite 的递归表查询的语境里，limit 的含义有了变化，它限制的不是生成语句所产生的记录总数，而是输出的递归表的总数，因此可以控制递归表的长度。

递归更新

SQLite 的递归查询功能是在 with 从句中实现的，该从句除了可以前置在 select 语句里，还可以前置在 update, delete, insert 等语句里。因此可以利用它的功能来实现递归更新等功能。不过如果递归更新含有顺序上的强关联，比如必须在子节点更新完了以后再更新父节点，恐怕光靠递归表查询还不够，需要自己写代码额外控制（比如先利用递归查询查出所有的节点并排好序，再依次执行更新语句）。