数据库新手求问，用于解决树形结构存储的闭包表，为何能快速获取某个节点的祖先节点/父节点/子节点？

[wxf666]

前言

看到网上很多文章吐槽，邻接表模型用递归获取祖先节点 /后代节点，导致性能很差。而用闭包表就能空间换时间，很快获取。

可是我看着闭包表的结构，没搞懂它是如何走索引，来快速获取祖先节点 /父节点 /子节点的。

闭包表结构

引入一个实际例子说吧。假设闭包表结构为：（简化，后续用 节点指代的名称 代替 节点 ID）

CREATE TABLE 闭包表 (
    祖先节点 ID INT,
    后代节点 ID INT,
    这俩节点距离 INT,
    PRIMARY KEY (祖先节点 ID, 后代节点 ID)
);

现有一张约 66W 行数据的 5 级地区表，各级数量为：*(参考自 中华人民共和国行政区划（五级）)*

省	市	区	街	村
31	342	2990	41356	618134

那么，建立的闭包表的行数量为：

1*1 (根, 根) + 31*2 (根, 省), (省, 省) + 342*3 + 2990*4 + 41356*5 + 618134*6 = 3928633 行

1. 如何快速获取 31 个省份？

网上很多的 SQL 是这样的：

SELECT 后代节点 FROM 闭包表 WHERE 祖先节点 = '根节点' AND /* 缺失：后代节点 = ? AND */ 距离 = 1

可是，根据最左匹配原则，距离 = 1 是无法利用的，所以上述 SQL 要扫描 66W 行（每个地区都有到根节点的记录），才能获得结果？？

2. 如何获取“杭州”所属省份？

网上的 SQL：

SELECT 祖先节点 FROM 闭包表 WHERE /* 缺失：祖先节点 = ? AND */ 后代节点 = '杭州' AND 距离 = 1

根据最左匹配原则，利用不了索引，所以上述 SQL 要扫描 390W 行，才能获得“杭州”的父节点？？

3. 如何获取“哈尔滨市 zf 亚布力滑雪度假区管理委员会虚拟社区”的省市区街村全称？（挑了个名字最长的。。）

网上的 SQL：

SELECT 祖先节点 FROM 闭包表 WHERE /* 缺失：祖先节点 = ? AND */ 后代节点 = '...' ORDER BY 距离 DESC

同理，这也是要扫描 390W 行，才能得到结果？？

[joooooker21]

> SELECT 祖先节点 FROM 闭包表 WHERE /* 缺失：祖先节点 = ? AND */ 后代节点 = '杭州' AND 距离 = 1
> 根据最左匹配原则，利用不了索引，所以上述 SQL 要扫描 390W 行，才能获得“杭州”的父节点？？

最左匹配指的是联合索引，你这段查询语句为什么利用不了索引？

[wxf666]

@joooooker21 表是联合主键，这个 SQL 没给出第一个主键，为啥能用聚集索引呢？

[wxf666]

@joooooker21 我改下措辞（肯定能用聚集索引，否则查不了数据）

闭包表是联合主键，这个 SQL 没给出第一个主键，为啥能不扫表，也可以高效找到所有 第二个主键为 '杭州' 的第一个主键呢？

换句话说，你觉得要扫多少行的表，就能定位到 (?, 杭州) ？

[xinxingi]

数据库新手，你考不考虑加个层级字段 Level 。1 2 3 4 5 级

[wangxin3]

用了“闭包表”，就不能自己加索引吗？

[wxf666]

@xinxingi

> 数据库新手，你考不考虑加个层级字段 Level 。1 2 3 4 5 级

`这俩节点距离` 还不足够使用吗？而且文中的三个问题，都是求某节点的父节点、子节点、祖先节点 这类不关心绝对层级的。加了真的有用吗？


@wangxin3

> 用了“闭包表”，就不能自己加索引吗？

你打算怎么加索引呢？是在主表加 `parent_id`，和 邻接表模型 结合在一起用吗？

[wxf666]

@Mithril 我在这个帖子说吧，因为是有关这个帖子主题的


> 比如你这帖子前两个需求，压根用不着数据库。直接硬编码数组进去就行了。

只是举个『获取某节点的子节点 /父节点』的例子，前一两级硬编码没问题。但实际上，这 66W 行，获取任何一行的子节点 /父节点，都会大规模扫 66W 行或 390W 行的表。。


> 对于第三个需求，你可以直接按村级记录存，每条记录带着完整 path 就可以。这也就是一个非常简单的表

我也知道有嵌套集、路径枚举模型。只是，这个帖子是讨论『闭包表』的合理性，才举了文中的例子的，不是讨论该用哪种模型存储最好


> 它举例的几种树形结构优化方案，都是针对于不限制深度的树来说的。在你这个需求里，树的结构实际上是固定的，深度也是固定的

即使是我这个固定 5 层的简单树形结构，『闭包表』都不能很好适应啊？何谈任意深度呢？

[wxf666]

@Mithril 有句话说错了：

但实际上，这 66W 行，获取任何一行的子节点 /父节点，都会大规模扫 （该节点后代节点总数） 行或 390W 行的表。。

[Mithril]

@wxf666
> 但实际上，这 66W 行，获取任何一行的子节点 /父节点，都会大规模扫 66W 行或 390W 行的表。。
这个跟你用什么结构存储没关系，单纯从 66W 行的表里检索一条记录而已，处理好索引就行了，并不会扫全表。
而且你只存村级的 62W 数据就够了，用不着 66W 。

> 只是，这个帖子是讨论『闭包表』的合理性，才举了文中的例子的，不是讨论该用哪种模型存储最好
> 即使是我这个固定 5 层的简单树形结构，『闭包表』都不能很好适应啊？何谈任意深度呢？
你实际上是在一个不适合用“闭包表”来处理的需求中，讨论如何使用“闭包表”。在这种场景下没什么使用闭包表的合理性，它当然不能很好适应了，完全是没必要的额外设计。

就算你用闭包表去存这个信息，也根本不必扫这么多数据。取决于你是怎么建立索引的，你给深度列单独建个索引不就行了。

[wxf666]

@Mithril

> 单纯从 66W 行的表里检索一条记录而已，处理好索引就行了，并不会扫全表。

是用了『闭包表』记录树形关系后，从 66W 行的表里检索一条记录的『子节点 /父节点』，会导致大范围扫表


> 而且你只存村级的 62W 数据就够了，用不着 66W 。

跳出我这个例子，这样的多列结构，没法处理任意深度的树了


> 你实际上是在一个不适合用“闭包表”来处理的需求中，讨论如何使用“闭包表”

你觉得『闭包表』的适用场景是啥呢？


> 就算你用闭包表去存这个信息，也根本不必扫这么多数据。取决于你是怎么建立索引的，你给深度列单独建个索引不就行了

你是说，表结构变成这样吗：

```sql
CREATE TABLE 闭包表 (
　祖先节点 ID INT,
　后代节点 ID INT,
　这俩节点距离 INT,
　 PRIMARY KEY (祖先节点 ID, 后代节点 ID),
　 KEY (这俩节点距离)
);
```

如果你的意思是这样：

1. 第一个问题解决

2. 第二个问题会变成扫 66W 行表（因为有 66W 个节点与其父节点的距离为 1 ，而 (距离, 祖先, 后代) 的索引结构表明，`WHERE 距离 = 1 AND /* 缺失：祖先节点 = ? AND */ 后代节点 = '杭州'` 的 `后代节点 = '杭州'`，由于最左匹配原则，是无法被利用的，所以需要扫 66W 行 `距离 = 1` 的索引）

3. 第三个问题还是要扫 390W 行表，因为你的 (距离, 祖先, 后代) 的索引结构不起作用。。

[wxf666]

@Mithril 我再概括下文章意思


> 你实际上是在一个不适合用“闭包表”来处理的需求中，讨论如何使用“闭包表”。在这种场景下没什么使用闭包表的合理性，它当然不能很好适应了，完全是没必要的额外设计。


1. 我实际是在说，『闭包表』对于任何一棵树都成立：如果要查询某个节点的祖先节点 /父节点 /子节点，都会导致大范围不合理的扫表

哪怕只是如文中所说的，查询根节点的子节点、第二层节点的父节点 /祖先节点，这些你口中说的『完全可以硬编码的数据』，都会大范围不合理扫表


2. 文中举了 5 级地区表的例子，是为了定量展示『闭包表』的『大范围不合理的扫表』可能为 66W 行、390W 行级别的，突出『闭包表』的『不合理』


3. 不知你说的『不适合用“闭包表”来处理的需求』，是否包含『查询某节点的祖先节点 /父节点 /子节点』呢？

[Mithril]

@wxf666 大概明白你的问题了。
数据库索引不是只能有一个的，聚类索引只能有一个，但普通索引你可以多加几个。如果一条查询会命中多个索引，那么会用其中选择性最大的。

比如你在祖先节点，后代节点和距离列上都建立单独的索引，这样优化器会自动挑个最大的。或者根据你的查询条件，把它们和距离组合上建立几个联合索引。

你这种情况，（祖先节点，距离）和（后代节点，距离）两个索引就够了。

[wangxin3]

@wxf666 我认为加联合索引 key(后代节点 ID, 距离)，可以使得 2 、3 问题查询时走索引。具体可以 explain 分析下。

[wxf666]

@Mithril

## 解决问题了

确实，更改表结构，并建立索引，使得有如下两种索引：

- 聚集索引：`(<后代, 距离>, 祖先)`
- 二级索引：`(<祖先, 距离>, 后代)`

就能高效应对下列查询了：

- (孙)子 /后代节点：走二级索引 `(✔️查询节点, ✔️1 或 2 或 任意, ❓<要获取的后代节点>)`
- (祖)父 /祖先节点：走聚集索引 `(✔️查询节点, ✔️1 或 2 或 任意, ❓<要获取的祖先节点>)`

下列查询会小范围扫表，但问题不大：

- 某后代节点与某祖先节点的距离：走聚集索引 `(✔️查询后代节点, ❓<要获取的距离>, ❌查询祖先节点)`

只要 `查询后代节点` 层级没有深到离谱，扫表范围也就连续的几行几十行而已。

*（为嘛网上关于『闭包表』的文章，都不谈这些必要的索引呢？他们用了后，都没性能问题嘛？）*


## 值得付出这么大的空间代价吗？

算下来，一个 66W 的 5 级地区表，就要配套一个相当于 780W 的闭包表，快接近 12 倍于主表的辅助表了。。

不知如此恐怖的空间换时间方案，相比于其他（如邻接表的）模型，到底能快多少呢？真的值得投入这么多空间来提速吗？

[Mithril]

@wxf666
> 为嘛网上关于『闭包表』的文章，都不谈这些必要的索引呢？他们用了后，都没性能问题嘛？
一般来说建立索引和优化是数据库基础操作，都不会写在这种文章里。

> 不知如此恐怖的空间换时间方案，相比于其他（如邻接表的）模型，到底能快多少呢？真的值得投入这么多空间来提速吗
所以我早就说了，你这种情况并不适合用闭包表。它是一种通用的设计，但不代表在任何情况下都是最优选择。
而且更重要的，不是说所有“看起来像棵树”的东西都要按照“树的结构”去保存。
你这种情况下，一个表就可以解决问题。你可以打开这个库带的那个 sqlite 文件，里面那个 village 表就足够满足你所有需求了。

[wxf666]

@Mithril

> 一般来说建立索引和优化是数据库基础操作，都不会写在这种文章里。

不光文章，我看他们实际开源的仓库，也没有这些措施。。就直接按照《 SQL 反模式》上介绍的表结构来实现的（所以我很疑惑性能问题）

比如： https://github.com/Kaciras/ClosureTable ，开源四年多，今早才改的表结构和加索引（我也去和那个博主聊了，在昨晚给出了和你类似的解决办法）


> 所以我早就说了，你这种情况并不适合用闭包表。它是一种通用的设计，但不代表在任何情况下都是最优选择。

我咋觉得，数据量小，其他模型也能很快；数据量大，『闭包表』就不划算，陷入一种尴尬情境。。

另外，有没有可能，也存在着某种通用模型设计，大部分时候性能和『闭包表』相当，但空间占用远低于『闭包表』？


> 你这种情况下，一个表就可以解决问题。你可以打开这个库带的那个 sqlite 文件，里面那个 village 表就足够满足你所有需求了。

好像一直纠结我如何存储那 5 级表的。。

我是用邻接表模型实现的，拿区划代码作为主键。（没用自增主键，算是针对地区库的优化？）

之前在（ i5-8250U 笔记本）浏览器上用 `wasm` 实现的 `SQLite` 进行测试，5 级 66W 行数据的地区表，能存成 16.8 MB 的数据库（`gzip` 后 5.72 MB ，`zstd` 后 4.32 MB ），并且纯 `SQL` 就可以：

1. 每秒计算出 25W 个区划代码的省 /市 /区 /街 /村全名（通过 4 次 `LEFT JOIN` 实现，也就是每秒能有 100W 次 `LEFT JOIN`）

2. 5~6 毫秒识别『疆维阿克苏温宿县博孜墩柯尔克孜族乡吾斯塘博村一组 306 号 tom800-8585222 』的各级地区名称为『新<疆维>吾尔自治区』、『<阿克苏>地区』、『<温宿县>』、『<博孜墩柯尔克孜族乡>』、『<吾斯塘博>依村』（模仿 [地址智能识别库]( https://github.com/wzc570738205/smartParsePro ) 的功能写的）

当然，用了很多递归 CTE ，但感觉速度还可以。（ v 站怎么发截图呢？我还从来没在这儿发过图片呢。。）

结果我看到文章说，邻接表用了很多递归，导致性能很差，所以我就仔细去看看『闭包表』的文章，看看能有多大提升了。然后没看懂，就有这篇文章了

[Mithril]

@wxf666
数据量大，但是每个分支深度差的比较多，每次检索的时候只找某条记录的子树这类的操作，闭包表就比较合适。
但实际上如果真的有很多需要查询路径，路径权重一类的操作，不如直接上图数据库了。

> 好像一直纠结我如何存储那 5 级表的
算不上纠结，只是觉得没必要。如果我做这个需求，直接一个表。
省全名 /市全名 /区全名 /街全名 /村全名
五个列上全建索引，你那三个需求都可以命中索引的。

这些技术都只是在现有 RDBMS 框架下的优化手段，知道有这个东西就可以了。练习的时候也没必要太过较真这些细节，知道怎么实现就行，真正项目里还得看需求。

[wxf666]

@Mithril

> 数据量大，但是每个分支深度差的比较多，每次检索的时候只找某条记录的子树这类的操作，闭包表就比较合适。

如果邻接表结构改成 `(父 ID, ID, 其他数据……, PRIMARY KEY (父 ID, ID), KEY (ID))`，能和『闭包表』一样快（甚至更快）且体积小吗？

理由：

- 虽然『闭包表』能一次性获取所有后代节点，但还要一一去主表找到这些散落各处的节点

- 对于邻接表，`(父 ID, ID)` 结构意味着，同层次的子节点都聚在一起，基本上要找多少层的后代，就查多少次表即可

即，『闭包表』要 (后代**总**数) 次 `WHERE id = ?`，但特殊结构邻接表只要 (后代**层**数) 次 `WHERE pid = ? AND id = ?`

[wxf666]

@Mithril 打多了，应该是：

即，『闭包表』要 (后代**总**数) 次 `WHERE id = ?`，但特殊结构邻接表只要 (后代**层**数) 次 `WHERE pid = ?`

[Mithril]

@wxf666

你说闭包表体积大，但实际上当你用来存节点的表有几十上百列，数据量也有几百万的时候，闭包表那点大小相对于邻接表区别就不是很大了。
而且当检索的深度不可预测时，可以一次性获取所有节点就远比需要递归的查询有用的多。

学习这些不同数据模型的时候，应该关注的是他们更加“抽象”意义上的区别，而不是这些实现细节。纠结这些细节意义并不大。
它们提供的是一种解决问题的方法和思路。真正在实际情况中，并不是非一即二的选择。比如你可以同时使用闭包表和邻接表，用邻接表的列去执行相邻节点查询，用闭包表去查所有子节点。如果闭包表可以很大程度上优化你的查询性能，那点多余空间根本无所谓。

就这两种模型来说，应该学到的大概就是。
- 当你只关注某个节点的父子结点，或者有限的几个相邻结点时，那么只保存邻接关系就够了。
- 如果你需要关注某个节点的所有父节点或者子节点，那么最好保存完整的“传递闭包”
只是两种思路而已。
如果你不需要父节点方向的查找，那就不用保存父节点关系。甚至闭包表你也可以不用保存完整的“传递闭包”，用不着的话，指向自身的关系可以不用存。

另外你说的查询次数，你可以 Explain 一下看看数据库是怎么给你优化查询的，你就明白它俩有啥区别了。

[wxf666]

@Mithril 我做了下『闭包表』和『改良后的邻接表』的测试 *（结尾附上一键建表和查询的 `SQL` 供测试）*

- 数据源：[2022 年中国全国 5 级行政区划]( https://github.com/adyliu/china_area/blob/master/area_code_2022.csv.gz)
- 数据库：`MySQL 8.0.29` 和 `SQLite 3.39.0`
- 表结构：『闭包表』和『 `(<pid, id>, is_leaf)` 型邻接表』
- 测试项：『查询根节点所有后代』和『查询根节点第 5 层后代』

结果如下 *（多次测试稳定后）*：



## 『查询根节点所有后代』速度对比

　　　　　表结构　　　　　　ＭｙＳＱＬ　ＳＱＬｉｔｅ

——————————————————————————

　　　　　闭包表　　　　　　　１．３秒　　０．１３秒

　　　　递归邻接表　　　　　　１．２秒　　０．６０秒

理想中递归损耗很小的邻接表　　０．６秒　　０．１２秒



Markdown 表格：

| 表结构 | `MySQL` | `SQLite` |
| :------------------------: | :-----: | :------: |
| 闭包表 | 1.3 秒 | 0.13 秒 |
| 递归邻接表 | 1.2 秒 | 0.60 秒 |
| 理想中递归损耗很小的邻接表 | 0.6 秒 | 0.12 秒 |



## 『查询根节点第 5 层后代』速度对比

　　　　　表结构　　　　　　ＭｙＳＱＬ　ＳＱＬｉｔｅ

——————————————————————————

　　　　　闭包表　　　　　　　１．２秒　　０．１２秒

　　　　递归邻接表　　　　　　０．５秒　　０．１３秒

理想中递归损耗很小的邻接表　　０．４秒　　０．１０秒



Markdown 表格：

| 表结构 | `MySQL` | `SQLite` |
| :------------------------: | :-----: | :------: |
| 闭包表 | 1.2 秒 | 0.12 秒 |
| 递归邻接表 | 0.5 秒 | 0.13 秒 |
| 理想中递归损耗很小的邻接表 | 0.4 秒 | 0.10 秒 |



## 目前观点

1. 4W 多次的 `ref` 级 `WHERE pid = ?`，还是能和 66W 次 `eq_ref` 级的 `WHERE id = ?` 过过招，甚至更快的。而且，磁盘 IO 越慢，这个差异应该越大。

2. 数据库们的 `WITH RECURSIVE` 查询，损耗有点大。

- `MySQL` 好歹每次递归都将上一次所有结果当作一张表来计算。但大概 5 次递归的耗时，就比非递归的多一倍了

- `SQLite` 最摆烂，每次递归只取以前结果的一行来计算，直到取完为止。所以有 66W 次的递归，耗时大概 5 倍。。😡

> Extract a single row from the queue.
>
> Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.



## 『查询根节点所有后代』通用 `SQL`

*（ V 站排版原因，行首有全角空格）*

```sql
PRAGMA cache_size = -204800; -- 允许 SQLite 缓存 200 MB

-- 闭包表查询
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
　 FROM closure_tree
FORCE INDEX (idx_closure_tree) -- 我这测试，MySQL 不加这行，耗时翻好几倍。SQLite 需去掉此行
　 JOIN closure ON id = descendant
WHERE ancestor = 0;

-- 递归邻接表查询
WITH RECURSIVE
　 find(id, code, name, is_leaf) AS (
　　 SELECT id, code, name, is_leaf
　　　 FROM adjacent
　　 WHERE pid = 0
　　 UNION ALL
　　 SELECT b.id, b.code, b.name, b.is_leaf
　　　 FROM find a
　　　 JOIN adjacent b ON NOT a.is_leaf AND b.pid = a.id
　)
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
　 FROM find;

-- 理想中，没有递归损耗的邻接表查询
SELECT COUNT(*), SUM(b.code), SUM(CHAR_LENGTH(b.name)) -- SQLite 写法：SUM(LENGTH(name))
　 FROM adjacent a
CROSS JOIN adjacent b ON b.pid = a.id -- SQLite 需要 CROSS JOIN ，否则耗时翻几倍
WHERE NOT a.is_leaf;
```



## 『查询根节点第 5 层后代』通用 `SQL`

*（ V 站排版原因，行首有全角空格）*

```sql
PRAGMA cache_size = -204800; -- 允许 SQLite 缓存 200 MB

-- 闭包表查询
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
　 FROM closure_tree
FORCE INDEX (idx_closure_tree) -- 我这测试，MySQL 不加这行，耗时翻好几倍。SQLite 需去掉此行
　 JOIN closure ON id = descendant
WHERE ancestor = 0
　 AND distance = 5;

-- 递归邻接表查询
WITH RECURSIVE
　 var(depth) AS (
　　 SELECT 5
　),

　-- 递归部分查前 N - 1 层
　 find(id, is_leaf, depth) AS (
　　 SELECT 0, FALSE, var.depth - 1
　　　 FROM var
　　 UNION ALL
　　 SELECT b.id, b.is_leaf, a.depth - 1
　　　 FROM find a
　　　 JOIN adjacent b ON b.pid = a.id
　　 WHERE a.depth > 0
　　　 AND NOT a.is_leaf
　)

-- 最后一次性 JOIN 第 N 层
SELECT COUNT(*), SUM(b.code), SUM(CHAR_LENGTH(b.name)) -- SQLite 写法：SUM(LENGTH(b.name))
　 FROM find a
CROSS JOIN adjacent b ON a.id = b.pid -- SQLite 要加 CROSS ，否则耗时翻几倍
WHERE a.depth = 0;

-- 理想中，没有递归损耗的邻接表查询（需要根据层数 N ，动态生成 SQL ）
SELECT COUNT(*), SUM(t5.code), SUM(CHAR_LENGTH(t5.name)) -- SQLite 写法：SUM(LENGTH(t5.name))
　 FROM adjacent t1
　 JOIN adjacent t2 ON t2.pid = t1.id
　 JOIN adjacent t3 ON t3.pid = t2.id
　 JOIN adjacent t4 ON t4.pid = t3.id
　 JOIN adjacent t5 ON t5.pid = t4.id
WHERE t1.pid = 0;
```



## `MySQL` 一键建表 `SQL`

*（在我低配笔记本和固态上，大约执行了 1 分钟）*

*（ V 站排版原因，行首有全角空格）*

```sql
-- 允许 200 MB 的内存表
SET max_heap_table_size = 200 << 20;

-- 建临时数据表，装载 csv 数据，以及计算序号和父子关系
CREATE TABLE data (
　　 code 　　 BIGINT 　　　 NOT NULL,
　　 p_code 　 BIGINT 　　　 NOT NULL,
　　 type 　　 TINYINT 　　 NOT NULL,
　　 name 　　 VARCHAR(25) NOT NULL,
　　 id 　　　 INT 　　　　 NOT NULL,
　　 pid 　　 INT 　　　　 NOT NULL,
　　 PRIMARY KEY (code) USING BTREE,
　　 INDEX USING BTREE (id),
　　 INDEX USING BTREE (pid, id)
) ENGINE = MEMORY;

-- 加载 csv
LOAD DATA INFILE 'area_code_2022.csv'
INTO TABLE data
CHARACTER SET UTF8MB4
FIELDS TERMINATED BY ','
ENCLOSED BY '"'
(code, name, type, p_code);

-- 按照 code 顺序计算 id
UPDATE data
　 JOIN (SELECT code, ROW_NUMBER() OVER win row_num
　　　　　 FROM data
　　　　 WINDOW win AS (ORDER BY code)) t USING(code)
　 SET id = row_num;

-- 计算 parent_id （不存在的标 0 ）
UPDATE data a
　 LEFT JOIN data b ON b.code = a.p_code
　 SET a.pid = IFNULL(b.id, 0);

-- 建邻接表，并从临时数据表填充数据
CREATE TABLE adjacent (
　　 id 　　　 INT 　　　　 NOT NULL,
　　 pid 　　 INT 　　　　 NOT NULL,
　　 is_leaf BOOL 　　　　 NOT NULL,
　　 type 　　 TINYINT 　　 NOT NULL,
　　 code 　　 BIGINT 　　　 NOT NULL,
　　 name 　　 VARCHAR(25) NOT NULL,
　　 PRIMARY KEY (pid, id)
)
SELECT -1 pid, 0 id, FALSE is_leaf, 0 type, 0 code, '' name
UNION ALL
SELECT pid, id, type = 5 is_leaf, type, code, name
　 FROM data;

-- 建闭包表主表，并从临时数据表填充数据
CREATE TABLE closure (
　　 id 　　　 INT 　　　　 NOT NULL,
　　 type 　　 TINYINT 　　 NOT NULL,
　　 code 　　 BIGINT 　　　 NOT NULL,
　　 name 　　 VARCHAR(25) NOT NULL,
　　 PRIMARY KEY (id)
)
SELECT 0 id, 0 type, 0 code, '' name
UNION ALL
SELECT id, type, code, name
　 FROM data;

-- 建闭包表树形关系表
CREATE TABLE closure_tree (
　　 ancestor 　　 INT 　　 NOT NULL,
　　 descendant 　 INT 　　 NOT NULL,
　　 distance 　　 TINYINT NOT NULL,
　　 PRIMARY KEY (descendant, distance)
);

-- 递归构建树形关系
INSERT INTO closure_tree(ancestor, descendant, distance)
WITH RECURSIVE
　 parent_of(orig_id, id, dist) AS (
　　 SELECT id, id, 0
　　　 FROM data
　　 UNION ALL
　　 SELECT orig_id, pid, dist + 1
　　　 FROM parent_of
　　　 JOIN data USING(id)
　　 WHERE id
　)
SELECT id, orig_id, dist
　 FROM parent_of;

-- 为闭包表树形关系表建二级索引
CREATE INDEX idx_closure_tree ON closure_tree (ancestor, distance);

-- 丢弃临时数据表
DROP TABLE data;
```



## `SQLite` 一键建表 `SQL`

下列 `SQL` 需要依赖 `SQLite Shell` 的 `.import --csv`，但核心 `SQLite` 库不提供此功能。

因此，需要使用命令行的 `SQLite` 来运行*（`Windows` 可去官网下载个 1~2 MB 的 `sqlite3.exe`）*。

下面使用 `Bash Shell` 来包装执行命令与 `SQL`，大约需要运行 30 秒，然后在同目录下生成 150 MB 左右的 `test.db`。

*（ V 站排版原因，行首有全角空格）*

```sql
#!/bin/bash

sqlite3 :memory: <<'EOF'

-- 在内存中计算，最后整理紧凑才写入文件
PRAGMA TEMP_STORE = MEMORY;

-- 导入 csv 文件至临时表
CREATE TEMP TABLE csv (code INTEGER PRIMARY KEY, name TEXT, type INT, p_code INT);
.import --csv area_code_2022.csv csv

-- 建邻接表
CREATE TABLE adjacent (
　　 id 　　　 INT 　　 NOT NULL,
　　 pid 　　 INT 　　 NOT NULL,
　　 is_leaf INT 　　 NOT NULL,
　　 type 　　 INT 　　 NOT NULL,
　　 code 　　 INT 　　 NOT NULL,
　　 name 　　 TEXT 　　 NOT NULL,
　　 PRIMARY KEY (pid, id)
) WITHOUT ROWID;

-- 填充邻接表
INSERT INTO adjacent (pid, id, is_leaf, type, code, name)
SELECT -1, 0, FALSE, 0, 0, ""
UNION ALL
SELECT p_code, ROW_NUMBER() OVER (), type = 5, type, code, name
　 FROM csv
ORDER BY code;

-- 建临时索引，提速 code 搜索
CREATE INDEX i ON adjacent (code);

-- 更新 pid
UPDATE adjacent
　 SET pid = t2.id
　 FROM adjacent t2
WHERE adjacent.pid = t2.code;

-- 丢弃临时索引
DROP INDEX i;

-- 建 id -> pid 索引
CREATE INDEX idx_adjacent_id ON adjacent (id);

-- 建闭包表主表
CREATE TABLE closure (
　　 id 　　　 INTEGER PRIMARY KEY,
　　 type 　　 INT 　　 NOT NULL,
　　 code 　　 INT 　　 NOT NULL,
　　 name 　　 TEXT 　　 NOT NULL
);

-- 建闭包表树形关系表
CREATE TABLE closure_tree (
　　 ancestor 　　 INT NOT NULL,
　　 descendant 　 INT NOT NULL,
　　 distance 　　 INT NOT NULL,
　　 PRIMARY KEY (descendant, distance)
) WITHOUT ROWID;

-- 填充闭包表主表
INSERT INTO closure (id, type, code, name)
SELECT id, type, code, name
　 FROM adjacent;

-- 递归构建树形关系
WITH RECURSIVE
　 parent_of(orig_id, id, dist) AS (
　　 SELECT id, id, 0
　　　 FROM adjacent
　　 UNION ALL
　　 SELECT orig_id, pid, dist + 1
　　　 FROM parent_of
　　　 JOIN adjacent USING(id)
　　 WHERE id
　)
INSERT INTO closure_tree (ancestor, descendant, distance)
SELECT id, orig_id, dist
　 FROM parent_of;

-- 为闭包表树形关系表建二级索引
CREATE INDEX idx_closure_tree ON closure_tree (ancestor, distance);

-- 整理紧实数据库后，写入磁盘
ANALYZE;
VACUUM INTO 'test.db';

EOF
```