@zyxk `SQLite` 咋可能不行。。

`MySQL` 语法：*（就是觉得 `json_table` 繁杂，懒得查文档才用的 `SQLite`。。V 站排版原因，行首有全角空格）*

```mysql
WITH
　 t_name(id, name, zone_id) AS (
　　 VALUES
　　　 ROW(3, 't1', '23,24'),
　　　 ROW(4, 't2', '24,23')
　),

　 t_zone(zone_id, zone) AS (
　　 VALUES
　　　 ROW(23, '5 元区'),
　　　 ROW(24, '10 元区')
　)
　
SELECT a?id, a?name, a?zone_id, group_concat(c?zone) AS zone
FROM t_name AS a
JOIN json_table(concat('[', a?zone_id, ']'), '$[*]' COLUMNS(zone_id INT PATH '$')) AS b
JOIN t_zone AS c ON b?zone_id = c?zone_id
GROUP BY a?id
```

我是数据库新手，不知这是不是奇技淫巧。或许你等大佬来指出真正问题所在才是正道。。


V 站告诉我：

创建新回复过程中遇到一些问题：

- 请不要在每一个回复中都包括外链，这看起来像是在 spamming

我把所有的 . 换成 ? 了，记得替换回来

用 json 函数试试？

`SQLite` 测试通过：*（`MySQL` 可用 `json_table`。V 站排版原因，行首有全角空格）*

```sqlite
WITH
　 t_name(id, name, zone_id) AS (
　　 VALUES
　　　(3, 't1', '23,24'),
　　　(4, 't2', '24,23')
　),

　 t_zone(zone_id, zone) AS (
　　 VALUES
　　　(23, '5 元区'),
　　　(24, '10 元区')
　)

SELECT a.id, a.name, a.zone_id, b.value, GROUP_CONCAT(c.zone)
　 FROM t_name a
　 JOIN json_each(format('[%s]', a.zone_id)) b
　 LEFT JOIN t_zone c ON b.value = c.zone_id -- 只能 LEFT JOIN 。怀疑是 JOIN 时，b 表会提前排好序，加速 b.id = c.id 匹配
GROUP BY a.id;
```

@Mithril 打多了，应该是：

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

@Mithril

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

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

理由：

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

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

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

@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

## 解决问题了

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

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

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

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

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

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

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

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


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

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

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

@Mithril 我再概括下文章意思


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


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

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


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


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

好奇会不会有其他语言的人，跑来说：恭喜，从慢 200 倍提升到慢 150 倍了

回他一句，继续说：对不起，刺痛你的心，戳到你肺管子了

@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 行表，因为你的 (距离, 祖先, 后代) 的索引结构不起作用。。

@Mithril 有句话说错了：

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

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


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

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


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

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


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

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

@xinxingi

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

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


@wangxin3

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

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

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

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

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

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

@Mithril 可以请教一下，《 SQL 反模式》里提到的闭包表，是如何高效的呢？

具体我下午发了个帖子：[数据库新手求问，用于解决树形结构存储的闭包表，为何能快速获取某个节点的祖先节点 /父节点 /子节点？]( /t/889443 )

数据库新手求问，为嘛不能用 MySQL 呢？如果用 MySQL ，这种表结构行不行：

搜索日志表（
　　用户 ID INT ，时间 TIMESTAMP ，型号 TINYTEXT ，数量 INT ，
　　 PRIMARY KEY （用户 ID ，时间，型号，数量），
　　 INDEX （型号，数量）
）

理由：

1. 每个用户搜索的内容，会尽量聚集在几页（有点类似『一个用户一个文档』），并按时间排序（尽量顺序插入），方便用户端按时间搜索（分组只能临时计算。但问题不大，反正一个用户一段时间内应该也没多少数据）

2. 后台查询某关键词被谁搜索过，走索引也很快

转 sqlite 后，用 sqlite 的 FTS5 全文搜索，能满足需求吗？

（ Trigram 分词器支持 3 字及以上的 LIKE '%关键词%' 搜索。
或者，有个号称参考微信 sqlite 优化原理写的 simple 开源分词器，也支持中文分词？）

我在那个帖子里的 3 楼，也问了个类似的问题，也给出一点猜测（但没人理我。。）

反正 20 天前，在一个 [帖子]( https://www.v2ex.com/t/882773 ) 里，有很多人反映，MySQL 单表存 1~2 亿（#11 楼 #16 #18 #19 #21 #35 ）、4 亿（#27 ）、10 亿（#36 ）、20 亿（#28 ）都没问题，查询也很快（< 10 ms ，#27 #28 ）