前言
众所周知，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 这一语法很容易理解：
- 在队列里产生初始数据
- 取出队列中的元素，输出该元素
- 将2步取出的元素，获取它的所有子节点，放入队列
- 继续进行第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 等语句里。因此可以利用它的功能来实现递归更新等功能。不过如果递归更新含有顺序上的强关联，比如必须在子节点更新完了以后再更新父节点，恐怕光靠递归表查询还不够，需要自己写代码额外控制（比如先利用递归查询查出所有的节点并排好序，再依次执行更新语句）。
