MENU

MySQL Tree 存储方案

December 7, 2021 • Read: 2633 • 编码,MySQL

Tree 数据设计方案比较

设计表数量查询子查询树插入删除引用完整性
邻接表1简单困难简单简单
递归查询1简单简单简单简单
枚举路径1简单简单简单简单
闭包表2简单简单简单简单

邻接表

邻接表是存储树形结构最普通的一种方案了,通过添加 parent_id 字段来确定树的父子关系。

下面就是一个相邻表是定义语句:

CREATE TABLE `adjoin_comment` (
  `comment_id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '评论主键',
  `parent_id` int(11) DEFAULT NULL COMMENT '父级评论id',
  `author` varchar(20) COLLATE utf8_unicode_ci DEFAULT NULL COMMENT '评论用户',
  `comment` varchar(255) COLLATE utf8_unicode_ci DEFAULT '' COMMENT '评论内容',
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci COMMENT='邻接回复表';
4 rows in set (0.00 sec)

下面是这棵评论树的数据:

mysql> SELECT * FROM adjoin_comment;
+------------+-----------+--------+-----------------------+
| comment_id | parent_id | author | comment               |
+------------+-----------+--------+-----------------------+
|          1 |      NULL | 张三   | 远上寒山石径斜        |
|          2 |         1 | 李四   | 白云生出有人家        |
|          3 |         2 | 王五   | 停车坐爱枫林晚        |
|          4 |         3 | 赵六   | 霜叶红于二月花        |
+------------+-----------+--------+-----------------------+
4 rows in set (0.00 sec)

查询

虽然很多人将邻接表作为属性数据的存储方案,但它仍然可能成为一个反模式,原因在于他无法完成树操作中最普通的一项:查询一个节点的所有后代。

只能使用关联查询来获取这个节点的直接后代:

mysql> SELECT * FROM adjoin_comment as c1
    -> LEFT JOIN adjoin_comment as c2 ON c2.parent_id = c1.comment_id
    -> WHERE c1.comment_id = 1 \G;
*************************** 1. row ***************************
comment_id: 1
 parent_id: NULL
    author: 张三
   comment: 远上寒山石径斜
comment_id: 2
 parent_id: 1
    author: 李四
   comment: 白云生出有人家
1 row in set (0.00 sec)

然而这样只能获取到两层数据。树的特性就是可以任意深的扩展,因而需要有其他方法来获取任意深度的数据。

使用邻接表时,查询变得非常不优雅,每增加一层数据查询都需要额外的扩展一个表连接,而SQL 的查询链接的次数是有上限的。

还有另一种方式通过邻接表来获取树结构数据的方法,先查询出所有行,在代码中自上而下的重新构造这棵树,再像树一样的使用这些数据。

这种方法是非常低效的,有可能你只需要一颗子树,而不是从根开始完整的树;
或者仅仅需要这些数据的聚合信息,比如 一个评论下面有多少子评论。

维护

无可否认的是,一部分操作通过相邻表来处理是非常方便的。

新增叶子节点

mysql> INSERT INTO adjoin_comment(parent_id,author,comment) VALUES(2,'李四','两岸猿声啼不住');
Query OK, 1 row affected (0.06 sec)

修改节点位置

mysql> UPDATE adjoin_comment SET parent_id = 3 WHERE comment_id = 5;
Query OK, 1 row affected (0.06 sec)
Rows matched: 1  Changed: 1  Warnings: 0

删除节点
如果要删除一个树的节点,就相对麻烦一些,不得不执行多次查询来找到所有的后代,然后从级别最低的节点开始逐级删除,以满足外键的完整性。
可以使用一个带 ON DELETE CASEADE 修饰符的外键约束来自动完成这些操作。

删除并移动节点
如果像删除一个节点并且提升它的子节点,或将子节点移动到另一个节点下。那么需要先修改子节点的 parent_id,然后才能删除这个节点

这些都是使用邻接表时需要多步操作才能完成的例子,不得不需要编写很多额外的代码,而其实数据库设计本身就能够做的很简单和高效。

递归查询

SQL Server 2005、Oracle 11、IBM DB2 和 PostgreSQL 8.4 这些数据库都支持递归查询,而 MySQL、SQLite 和 Infomix 是少数不支持的数据库。

如果递归查询语法被所有主流数据库所支持,那么使用邻接表的设计不会再有这么多限制了。

路径枚举

邻接表的问题之一是从树中获取一个给定节点的所有祖先开销很大。路径枚举的设计通过将所有的祖先信息联合成一个字符串,并保存为每个节点的一个属性,很巧妙的解决了这个问题。

path_comment 表中,我们使用 path 字段来代替原来的 parent_id 字段,将从这个结点开始到最顶级节点的所有 id 存储起来,就像文件目录一样。

定义语句:

CREATE TABLE `path_comment` (
  `comment_id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '评论主键',
  `path` varchar(1000) COLLATE utf8_unicode_ci DEFAULT NULL COMMENT '祖先路径',
  `author` varchar(20) COLLATE utf8_unicode_ci DEFAULT NULL COMMENT '评论用户',
  `comment` varchar(255) COLLATE utf8_unicode_ci DEFAULT '' COMMENT '评论内容',
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci COMMENT='路径回复表';

路径枚举数据:

mysql> SELECT * FROM path_comment;
+------------+----------+--------+----------------+
| comment_id | path     | author | comment        |
+------------+----------+--------+----------------+
|          1 | 1,       | 张三   | 远上寒山石径斜 |
|          2 | 1,2,     | 李四   | 白云生出有人家 |
|          3 | 1,2,3,   | 王五   | 停车坐爱枫林晚 |
|          4 | 1,2,3,4, | 赵六   | 霜叶红于二月花 |
+------------+----------+--------+----------------+
4 rows in set (0.04 sec)

查询

查询节点祖先

可以通过比较每一个节点的路径来查找祖先,例如要查找 comment_id 4 的祖先:

mysql> SELECT * FROM path_comment WHERE '1,2,3,4,' LIKE CONCAT(path,'%');
+------------+----------+--------+----------------+
| comment_id | path     | author | comment        |
+------------+----------+--------+----------------+
|          1 | 1,       | 张三   | 远上寒山石径斜 |
|          2 | 1,2,     | 李四   | 白云生出有人家 |
|          3 | 1,2,3,   | 王五   | 停车坐爱枫林晚 |
|          4 | 1,2,3,4, | 赵六   | 霜叶红于二月花 |
+------------+----------+--------+----------------+
4 rows in set (0.04 sec)

这条语句会匹配到 1,2,3,4,%1,2,3,%1,2,% 以及 1,% 的节点,而这些节点就是 comment_id 4 的祖先。

查找后代

查询 路径 1,2, 节点的所有后代:

mysql> SELECT * FROM path_comment WHERE path LIKE "1,2,%";
+------------+----------+--------+----------------+
| comment_id | path     | author | comment        |
+------------+----------+--------+----------------+
|          2 | 1,2,     | 李四   | 白云生出有人家 |
|          3 | 1,2,3,   | 王五   | 停车坐爱枫林晚 |
|          4 | 1,2,3,4, | 赵六   | 霜叶红于二月花 |
+------------+----------+--------+----------------+
3 rows in set (0.05 sec)
mysql> 

聚合查询

一旦可以获取到一个节点的所有 祖先节点 或 所有子节点,就可以实现更多的查询,比如计算某个部门 下面的小部门一共有多少人,或者只是计算节点的数量。又或者需要知道 某个评论下每个人的回复次数:

mysql> SELECT author,count(*) FROM path_comment WHERE path LIKE "1,2,%" GROUP BY author;
+--------+----------+
| author | count(*) |
+--------+----------+
| 李四   |        1 |
| 王五   |        1 |
| 赵六   |        1 |
+--------+----------+
3 rows in set (0.06 sec)

维护

插入节点
插入一个节点也很方便,步骤如下:

  1. 获取父节点的 path 字段
  2. 将插入的记录 id 追加到路径末尾 (如果是自增ID,那么需要先写入记录,然后再更新 path 字段)

小结

路径枚举的方案也存在一些问题,比如:

  • 数据库不能保证路径的格式总是正确或者路径中的节点确实存在。
  • 依赖于应用程序的代码逻辑来维护路径的字符串,并且验证字符串正确性的开销很大。
  • 无论 VARCHAR 的长度设定为多大,依旧存在长度限制,因此并不能够支持树结构的无限扩展。

闭包表

待补全

反模式

什么是反模式

反模式是一种试图解决问题的方法,但通常会同时引发别的问题。

如何辨别树的反模式

如果听到了以下的问题,你可能正在使用树的反模式。

  • 我们的树结构需要支持多少层?
    你正在纠结于不使用递归查询获取一个节点的所有祖先或后代。于是你做出让步,只支持有限层级数据的所有操作,所以紧跟着的问题就是:需要多少层才能满足需求?
  • 我总是很害怕接触那些管理树结构的代码
    你已经采用了一部分管理分层数据的比较复杂的方法,但使用的是错误的方法。每项技术都会使得一些任务变得很简单,但通常是以让其他任务变的更加复杂为代价。这是因为你选择的并不是最佳的解决方案来管理这些分层数据。
  • 我需要一个脚本定期的清理树中的孤独节点数据。
    你的应用程序因为删除了非叶子节点而产生了一些迷失节点。在数据库存储一些复杂结构时,要确保在任何变更之后,这个结构都处在一致的、有效的状态下。可以参考本文中描述的解决方案,同时配合触发器、级联外键等,是的数据存储的结构更加符合项目的需求

合理的使用反模式

某些情况下,在应用程序中使用临界表设计可能刚好适用。邻接表的设计优势是在于可以快速的获取一个给定节点的父子节点,也很容易插入新节点。如果这就是你对树节点操作的全部需求,那使用邻接表就可以更好的工作了。


参考:《SQL 反模式》 第三节 简单的树

Last Modified: January 21, 2022
Leave a Comment

4 Comments
  1. Zim Zim

    回忆了一下,你说的这几种模式我竟然都用过。当然我使用最多的还是邻接表模式,我在你文中举例的基础上增加了rootId与level两个索引字段,这样可以方便获取某个节点的所有子树或者与某个节点有父子关联的指定层级的树.
    使用案例见我的一篇经验总结之文:https://zhuanlan.zhihu.com/p/368808546

    1. @Zim是的,具体使用还是要根据业务需求来灵活组合实现方案,我一般会邻接表和枚举路径配合使用,既可以查出相邻的节点,也可以查出所有的父子节点

  2. 无名 无名

    MySQL 和 SQLite 在好多年前就支持递归查询了呀?

    MySQL 在 2017-04-10 发布的 8.0.1 版本已经支持 (Recursive) CTE 了:https://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-1.html (页面可搜索到 common table expressions)

    SQLite 更早,在 2014-02-03 发布的 3.8.3 版本就支持 (Recursive) CTE 了:https://sqlite.org/releaselog/3_8_3.html

    博主是转的十几年前的旧文吗?

    1. @无名关于递归查询的这段是摘抄《SQL 反模式》一书中的描述,结合目前各个数据库的发展来说确实有一些过时。写这篇文章的目的也是因为书中关于数据表的设计思路非常经典,值得参考学习,而不是为了让你抠字眼说版本过时。

      文章的内容并非你说的转载其他平台的文章,我博客所有的文章都是自己原创博文,若有参考资料均会在文章后面标明出处。