请问如果一棵树存在数据表中，有没有办法将其一次查出？

[jackiejkl]

也就是 SQL 可以写 DFS 吗？是不是需要用到存储过程？或者有更优解？

首先感谢各位的建议，我是倾向于采用增加一个字段指向父节点的，树的类型是 N 叉树不是二叉树，层数也不能确定。
问题描述得不够清楚，我是想问这种情况是不是只能通过后端代码来 DFS ？感觉这样查询很频繁。
另外，感谢 @aguesuka @wxf666 @mayli @kkkiio @linuxyz 等大佬提到的 mysql8.0 的 CTE 为我提供了新思路。不知道上述提到的两种方法性能哪个好？
图数据库目前应该是不考虑的，老项目不方便引入新依赖。
还有一点可以确定的是会从根节点开始查，应该不会出现根据某个节点获取整棵树的情况。
还有感觉用 redis 之类的 nosql 来持久化保存这种数据根据不太妥。。
似乎还有一种方法，字段设计为 “主键 id-父节点 id-整棵树 root 的 id ”，这样第一步可以通过 root id 拿到这棵树所有的数据，再到后端慢慢渲染。

[colorfuldays]

关键看你怎么设计这个存储表.
table name：tree_node_table
columns: id, tree_id, parent_node_id, node_data, ctime, mtime
如果是这样的表结构，一个 SQL 就能把某个 tree_id 对应的全面数据都查出来，然后自己在内存里面构建相应的树结构。
当然为了简单你还可以加上 root_id 等

[dqzcwxb]

关键词 并查集

[learningman]

@dqzcwxb sql 不适合用并查集，你没法开值域数组

[wxf666]

（递归） Common Table Expressions ？深度广度优先搜索都可

[dqzcwxb]

@learningman #3 使用并查集的根节点标记,跟 1 楼的思路一样查出来后在内存构建树,不是用 sql 实现并查集

[DonaldY]

闭包。
父节点跟其下子孙节点均建立关系。

[mayli]

正规做法是 CTE 。

[Suddoo]

可以看下《 SQL 反模式》里面解决方案比较多

如果存的时候限制层数、直接 join 自身 n 次即可

或者存的时候，把所有父节点 id 用逗号分隔后存储

[mingl0280]

加上 tree_id 或者 root_node_id 都可以，前者更好（更新根结点无需更改所有关联项）

[tabris17]

每个节点加一个根节点字段

[tabris17]

另外还有左右值方案： https://developer.aliyun.com/article/42501

[jorneyr]

一般一个表存储树的数据，存储了很多棵树的数据（按 Node 存储），每棵树的数据量一般不会很大，那就一次查出某个树的数据，然后内存处理。

[netnr]

1
1.1
1.1.1

like '1%'

[aguesuka]

mysql8 支持递归查询

https://dev.mysql.com/doc/refman/8.0/en/with.html#common-table-expressions-recursive

[Tidusy]

顺便问下如果树不大的话直接一列里存整棵树的结构（比如 json ），节点的数据单独存一个表，是合理的设计吗？

[Saxton]

我是拿一个 pids 来存这个节点的所有根，查的时候直接 find_in_set(pids) 就可以把整一棵树查回来

[BBCCBB]

实现这个最好的&最简单的方案应该是闭包表?

反正我喜欢用这个...

[wxf666]

数据库新手，拿 SQLite 练练 CTE

实现了一条语句将 json：

{"书": {"章 1": ["节 1", "节 2"], "章 2": "节 3"}}

逐项添加进表中：

+----+-----------+------+
| id | parent_id | data |
+----+-----------+------+
| 2 | 0 | 书 |
| 4 | 2 | 章 1 |
| 5 | 4 | 节 1 |
| 6 | 4 | 节 2 |
| 7 | 2 | 章 2 |
| 8 | 7 | 节 3 |
+----+-----------+------+

再用一条语句，将某节点（如“节 2”）所在的整棵树查询出来：

+-----------+
| result |
+-----------+
| 书 |
| 章 1 |
| 节 1 |
| 节 2 |
| 章 2 |
| 节 3 |
+-----------+

功力不够，想转化成 json ，却不懂咋写了


CREATE TABLE node (id INTEGER PRIMARY KEY, parent_id INT, data);
INSERT INTO node (parent_id, data) VALUES (0, '书 0'); -- 测试表非空时 下面 INSERT 是否正常

-- =================================
-- 以下将 json 字符串 逐项添加进表中
-- =================================

WITH
my_data(json) AS (
SELECT '{
"书 1": {
"书 1 章 1": ["书 1 章 1 节 1", "书 1 章 1 节 2"],
"书 1 章 2": {
"书 1 章 2 节 1": {"书 1 章 2 节 1 段 1": "书 1 章 2 节 1 段 1 字 1"},
"书 1 章 2 节 2": ["书 1 章 2 节 2 段 1", "书 1 章 2 节 2 段 2"]
}
},
"书 2": ["书 2 章 1", "书 2 章 2"]
}'
),

node_info(max_id) AS (
SELECT IFNULL(max(id), 0) FROM node
)

-- 添加搜集好的 key 和 value
INSERT INTO node (id, parent_id, data)

-- 遇到 object 时，取其 key
SELECT max_id + id - (type NOT IN ('array', 'object')) AS id,
CASE WHEN parent THEN max_id + parent
ELSE 0
END AS parent_id,
key AS data
FROM node_info, my_data, json_tree(my_data.json)
WHERE typeof(key) = 'text'
UNION ALL

-- 不是 array 和 object 时，取其 value
SELECT max_id + id + (parent = 0 AND key IS NULL) AS id,
CASE WHEN typeof(key) = 'text' THEN max_id + id - 1 -- object 的值
WHEN parent THEN max_id + parent -- array 的值
ELSE 0 -- 根处的值
END AS parent_id,
value AS data
FROM node_info, my_data, json_tree(my_data.json)
WHERE type NOT IN ('array', 'object');

SELECT * FROM node;

-- =====================================================
-- 以下将 某节点所在的整棵树 转化成 有缩进的列表 和 json
-- =====================================================

WITH RECURSIVE
my_data(node_id) AS (
SELECT id FROM node WHERE data = '书 1 章 2 节 1 段 1 字 1' LIMIT 1
),

-- 列举 my_data 的 node_id 的所有父节点
parent_of(id, parent_id) AS (
SELECT id, parent_id
FROM my_data JOIN node ON node_id = node.id
UNION ALL
SELECT p.id, p.parent_id
FROM parent_of n JOIN node p ON n.parent_id = p.id
),

-- 获取 my_data 的 node_id 的根节点
root(id) AS (
SELECT id FROM parent_of WHERE parent_id = 0
),

-- 列举 tree
list(id, data, level) AS (
SELECT id, data, 0
FROM root JOIN node USING(id)
UNION ALL
SELECT n.id, n.data, level + 1
FROM node n JOIN list p ON n.parent_id = p.id
ORDER BY 3 DESC, 1
)

-- -- json 化 tree
-- jsonify() AS (
-- -- 功力不够，写不出来
-- )

SELECT format('%*s', level*3, '') || data FROM list;

[wxf666]

为毛缩进全没了

[Nich0la5]

我能想到的几个方案
1 每行数据都存父子节点 ID
2 直接存 JSON 格式 是可以支持节点查询的
3 或者咱干脆换 nosql 吧

[kkkiio]

@tabris17 我查一下，这个“左右值”方案英文叫 Nested Set Model ，有篇老文 http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ 讲了这个，感觉很有意思，就是改结构时更新数据有点多。

Stack Overflow "Adjacency List Model vs Nested Set Model for MySQL hierarchical data?" 有个回答 https://stackoverflow.com/a/31642680/5008141 认为 Nested Set Model 过于复杂，推荐用 Recursive Common Table Expressions ，也就是楼上说的 Recursive CTE 。

[tabris17]

@kkkiio 这个“Nested Set Model”的优势是可以一条语句获取任意节点的全部子孙节点。适合树结构不庞大，且不会频繁修改插入的场景，比如栏目分类，部门组织什么的

[banmuyutian]

闭包表修改的时候麻烦点，查询的时候比较灵活

[kkkiio]

@tabris17 “一条语句”强调的是性能吗？感觉可以做个测试对比一下 Nested Set Model 和 Recursive CTE 的性能，个人猜测如果树结构不庞大，CTE 性能也不差

[Vaspike]

存进数据库的是完全展开的树信息,一行只有当前节点的父节点和自己节点的 id(自己节点的其他信息)
全量查,查出来后递归渲染这棵树

[issakchill]

弄个路径字段 每次插入更新路径

[n0trace]

如果需要移动节点路径的话真没啥万全法。

[linuxyz]

Oracle 可以用 Hierarchical Queries https://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm
SQL Server 可以用 Hierarchical Data https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server?view=sql-server-2016
PostgreSQL 可以用 ltree https://www.postgresql.org/docs/current/ltree.html
MySQL 8.0 (MariaDB 10.2.2) 以上 可以用 recursive common table expression (CTE) https://www.mysqltutorial.org/mysql-adjacency-list-tree/
SQLite 可以用 WITH RECURSIVE https://yshurik.github.io/post/sqlite-tree-structures-and-queries-to-get-sub-trees/

[LLaMA2]

https://typeorm.bootcss.com/tree-entities
看看 ORM 中怎么做的，然后自己取舍

[linuxyz]

@linuxyz 從首頁跳過來的，沒注意是在 MySQL 版， 看起來是樓主是問比較老版本的 MySQL 了， 看看能不能把數據導入内存重建 Tree ？

[wxf666]

@n0trace 邻接表类型，移动节点，不是一条 update xxx set parent_id = ? 即可吗

[someonedeng]

冗余 path

a,b,c,d

select a,b*

[wxf666]

@kkkiio 树结构庞大，CTE 比不过原因是啥？查 parent_id 索引难命中缓存？

那加个 root_id 字段，索引 (root_id, parent_id)，是不是同一棵树的索引都尽量集中到一块儿去就好了

[Nooooobycat]

这种情况下，能否考虑一下图数据库？

[pank]

@Nooooobycat ，图数据库肯定可以做到，我之前写过一个 demo 专门测过，把部门和人全部导入到了 neo4j, 查询部门及子部门下所有用户，实测在本地性能并不高。也有可能是我本地电脑性能不够好。后来领导担心这个没人用过，而且有杀鸡用牛刀的嫌疑，就放弃这个方案了。这么多方案综合考虑下来，还是左右值编码的方案最简单，但是它也不完美，查询一批部门下的用户的时候，就需要用 or