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

2022-06-28 00:30:37 +08:00
 jackiejkl
也就是 SQL 可以写 DFS 吗?是不是需要用到存储过程?或者有更优解?
4359 次点击
所在节点    MySQL
35 条回复
colorfuldays
2022-06-28 00:47:03 +08:00
关键看你怎么设计这个存储表.
table name:tree_node_table
columns: id, tree_id, parent_node_id, node_data, ctime, mtime
如果是这样的表结构,一个 SQL 就能把某个 tree_id 对应的全面数据都查出来,然后自己在内存里面构建相应的树结构。
当然为了简单你还可以加上 root_id 等
dqzcwxb
2022-06-28 00:54:09 +08:00
关键词 并查集
learningman
2022-06-28 01:09:53 +08:00
@dqzcwxb sql 不适合用并查集,你没法开值域数组
wxf666
2022-06-28 01:33:57 +08:00
(递归) Common Table Expressions ?深度广度优先搜索都可
dqzcwxb
2022-06-28 01:36:13 +08:00
@learningman #3 使用并查集的根节点标记,跟 1 楼的思路一样查出来后在内存构建树,不是用 sql 实现并查集
DonaldY
2022-06-28 02:02:08 +08:00
闭包。
父节点跟其下子孙节点均建立关系。
mayli
2022-06-28 04:48:09 +08:00
正规做法是 CTE 。
Suddoo
2022-06-28 07:38:17 +08:00
可以看下《 SQL 反模式》里面解决方案比较多

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

或者存的时候,把所有父节点 id 用逗号分隔后存储
mingl0280
2022-06-28 08:02:51 +08:00
加上 tree_id 或者 root_node_id 都可以,前者更好(更新根结点无需更改所有关联项)
tabris17
2022-06-28 08:09:57 +08:00
每个节点加一个根节点字段
tabris17
2022-06-28 08:10:36 +08:00
另外还有左右值方案: https://developer.aliyun.com/article/42501
jorneyr
2022-06-28 08:27:47 +08:00
一般一个表存储树的数据,存储了很多棵树的数据(按 Node 存储),每棵树的数据量一般不会很大,那就一次查出某个树的数据,然后内存处理。
netnr
2022-06-28 09:02:37 +08:00
1
1.1
1.1.1

like '1%'
aguesuka
2022-06-28 09:02:53 +08:00
Tidusy
2022-06-28 09:09:06 +08:00
顺便问下如果树不大的话直接一列里存整棵树的结构(比如 json ),节点的数据单独存一个表,是合理的设计吗?
Saxton
2022-06-28 09:16:56 +08:00
我是拿一个 pids 来存这个节点的所有根,查的时候直接 find_in_set(pids) 就可以把整一棵树查回来
BBCCBB
2022-06-28 09:26:32 +08:00
实现这个最好的&最简单的方案应该是闭包表?

反正我喜欢用这个...
wxf666
2022-06-28 13:39:57 +08:00
数据库新手,拿 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
2022-06-28 13:43:06 +08:00
为毛缩进全没了
Nich0la5
2022-06-28 14:02:56 +08:00
我能想到的几个方案
1 每行数据都存父子节点 ID
2 直接存 JSON 格式 是可以支持节点查询的
3 或者咱干脆换 nosql 吧

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/862587

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX