@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 ）

@uil330

> 1.50TB 放在 cloud 的数据我想不出比 sql 更有效率的方法了

这是要取回本地嘛？还是更新 /追加云端的数据？

若取回本地的话，写个脚本应该会更快吧？*（至少，稀疏数据传得会快些？）*



@sun522198558 数据库新手，好奇想问下，连 1~2 MB 的 `SQLite` 功能都开始丰富多样起来了，为啥还坚持旧版本 `MySQL` 呢？

未定义行为，摸透了也确实能用 *（反正我没摸透，不知为啥那个帖子里的赋值是异常的）*

不支持窗口函数，那就用基础 `SQL` 吧：*（感觉会比窗口函数慢）*

```sqlite
WITH
　 data(id, data, time) AS (
　　 VALUES
　　　(1, 10, '00:03'),
　　　(1, 50, '04:23'),
　　　(1, 20, '07:03')
　),

　 ids(id) AS (
　　 SELECT DISTINCT id
　　　 FROM data
　),

　 time(time) AS (
　　 SELECT format('%02d:00', value)
　　　 FROM json_each('[1, 2, 3, 4, 5, 6, 7, 8]')
　)

-- 方法一
SELECT i.id, t.time,
　　　 (SELECT data
　　　　　 FROM data
　　　　 WHERE id = i.id
　　　　　 AND time < t.time
　　　　 ORDER BY time DESC
　　　　 LIMIT 1) data,
　　　 NULL useless
　 FROM ids i
　 JOIN time t

UNION ALL
VALUES ('----', '----', '----', '----')
UNION ALL

-- 方法二
SELECT i.id, t.time, d.data, MAX(d.time) useless
　 FROM ids i
　 JOIN time t
　 LEFT JOIN data d ON i.id = d.id AND t.time > d.time
GROUP BY i.id, t.time;
```

@shiyanfei5 我查了查 `PostgreSQL` 关于窗口函数的 [文档]( https://www.postgresql.org/docs/current/functions-window.html )，pg 也不支持使用 `IGNORE NULLS` 取上一个非 `NULL` 值呀：

> The SQL standard defines a RESPECT NULLS or IGNORE NULLS option for lead, lag, first_value, last_value, and nth_value. This is not implemented in PostgreSQL: the behavior is always the same as the standard's default, namely RESPECT NULLS

你是咋做的呢？

@sun522198558 对于 `MySQL`，官方不建议这样使用 *（两周前就有人 [发帖]( /t/883301 ) 说赋值异常的）*

- 『在同一条语句内赋值和读取一个用户变量』的行为未定义
- 『在 `SELECT` 中赋值用户变量』已被弃用，未来会移除


@uil330 你是啥数据库啊？

我看 `MySQL` 的 `LAG()`、`LAST_VALUE()` 等窗口函数，都还不支持 `IGNORE NULLS`

`SQLite` 也还不支持在 `LAG()` 等窗口函数上使用 `FILTER (WHERE xxx IS NOT NULL)`，但能用在聚合函数上

所以用 `SQLite` 写了试试：

*（ V 站排版原因，开头有全角空格。若要复制运行，记得删除）*

```sqlite
WITH
　 data(id, data, time) AS (
　　 VALUES
　　　(1, 10, '00:03'),
　　　(1, 50, '04:23'),
　　　(1, 20, '07:03')
　),
　
　 ids(id) AS (
　　 SELECT DISTINCT id
　　　 FROM data
　),
　
　 time(hour) AS (
　　 SELECT value
　　　 FROM json_each('[1, 2, 3, 4, 5, 6, 7, 8]')
　),
　
　 formated(id, hour, data) AS (
　　 SELECT id, strftime('%H', time) + 1, data
　　　 FROM data
　)

-- 按 id 分组，hour 为顺序，窗口范围为 [组内第一行, 当前行]，并过滤掉 NULL 值，
-- 剩余值合并成 json 数组，然后取数组最后一位（这个数组至多 24 个数嘛，不算大）
SELECT id,
　　　 json_group_array(data) FILTER(WHERE data IS NOT NULL) OVER win ->> '$[#-1]' data,
　　　 format('%02d:00', hour) time
　 FROM ids
　 JOIN time
　 LEFT JOIN formated USING(id, hour)
WINDOW win AS (PARTITION BY id ORDER BY hour);
```

@sylpha 那 20 多个系统不能配合提供 “当前系统还在用着哪些文件” 的话。。那就留着呗。。

就算删掉一半文件，能快多少呢？

你不会是所有文件，都塞到一个文件夹里吧？？