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

[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 一下看看数据库是怎么给你优化查询的，你就明白它俩有啥区别了。