V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
MySQL 5.5 Community Server
MySQL 5.6 Community Server
Percona Configuration Wizard
XtraBackup 搭建主从复制
Great Sites on MySQL
Percona
MySQL Performance Blog
Severalnines
推荐管理工具
Sequel Pro
phpMyAdmin
推荐书目
MySQL Cookbook
MySQL 相关项目
MariaDB
Drizzle
参考文档
http://mysql-python.sourceforge.net/MySQLdb.html
jackiejkl
V2EX  ›  MySQL

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

  •  
  •   jackiejkl · 2022-06-28 00:30:37 +08:00 · 4717 次点击
    这是一个创建于 898 天前的主题,其中的信息可能已经有所发展或是发生改变。
    也就是 SQL 可以写 DFS 吗?是不是需要用到存储过程?或者有更优解?
    第 1 条附言  ·  2022-06-29 23:29:06 +08:00
    首先感谢各位的建议,我是倾向于采用增加一个字段指向父节点的,树的类型是 N 叉树不是二叉树,层数也不能确定。
    问题描述得不够清楚,我是想问这种情况是不是只能通过后端代码来 DFS ?感觉这样查询很频繁。
    另外,感谢 @aguesuka @wxf666 @mayli @kkkiio @linuxyz 等大佬提到的 mysql8.0 的 CTE 为我提供了新思路。不知道上述提到的两种方法性能哪个好?
    图数据库目前应该是不考虑的,老项目不方便引入新依赖。
    还有一点可以确定的是会从根节点开始查,应该不会出现根据某个节点获取整棵树的情况。
    还有感觉用 redis 之类的 nosql 来持久化保存这种数据根据不太妥。。
    似乎还有一种方法,字段设计为 “主键 id-父节点 id-整棵树 root 的 id ”,这样第一步可以通过 root id 拿到这棵树所有的数据,再到后端慢慢渲染。
    35 条回复    2022-07-15 10:21:28 +08:00
    colorfuldays
        1
    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
        2
    dqzcwxb  
       2022-06-28 00:54:09 +08:00
    关键词 并查集
    learningman
        3
    learningman  
       2022-06-28 01:09:53 +08:00 via Android
    @dqzcwxb sql 不适合用并查集,你没法开值域数组
    wxf666
        4
    wxf666  
       2022-06-28 01:33:57 +08:00
    (递归) Common Table Expressions ?深度广度优先搜索都可
    dqzcwxb
        5
    dqzcwxb  
       2022-06-28 01:36:13 +08:00   ❤️ 1
    @learningman #3 使用并查集的根节点标记,跟 1 楼的思路一样查出来后在内存构建树,不是用 sql 实现并查集
    DonaldY
        6
    DonaldY  
       2022-06-28 02:02:08 +08:00
    闭包。
    父节点跟其下子孙节点均建立关系。
    mayli
        7
    mayli  
       2022-06-28 04:48:09 +08:00   ❤️ 1
    正规做法是 CTE 。
    Suddoo
        8
    Suddoo  
       2022-06-28 07:38:17 +08:00 via iPhone   ❤️ 1
    可以看下《 SQL 反模式》里面解决方案比较多

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

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

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

    反正我喜欢用这个...
    wxf666
        18
    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
        19
    wxf666  
       2022-06-28 13:43:06 +08:00
    为毛缩进全没了
    Nich0la5
        20
    Nich0la5  
       2022-06-28 14:02:56 +08:00
    我能想到的几个方案
    1 每行数据都存父子节点 ID
    2 直接存 JSON 格式 是可以支持节点查询的
    3 或者咱干脆换 nosql 吧
    kkkiio
        21
    kkkiio  
       2022-06-28 14:12:49 +08:00
    @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
        22
    tabris17  
       2022-06-28 14:23:32 +08:00
    @kkkiio 这个“Nested Set Model”的优势是可以一条语句获取任意节点的全部子孙节点。适合树结构不庞大,且不会频繁修改插入的场景,比如栏目分类,部门组织什么的
    banmuyutian
        23
    banmuyutian  
       2022-06-28 14:25:13 +08:00
    闭包表修改的时候麻烦点,查询的时候比较灵活
    kkkiio
        24
    kkkiio  
       2022-06-28 14:52:12 +08:00
    @tabris17 “一条语句”强调的是性能吗?感觉可以做个测试对比一下 Nested Set Model 和 Recursive CTE 的性能,个人猜测如果树结构不庞大,CTE 性能也不差
    Vaspike
        25
    Vaspike  
       2022-06-28 15:31:51 +08:00
    存进数据库的是完全展开的树信息,一行只有当前节点的父节点和自己节点的 id(自己节点的其他信息)
    全量查,查出来后递归渲染这棵树
    issakchill
        26
    issakchill  
       2022-06-28 15:53:50 +08:00
    弄个路径字段 每次插入更新路径
    m16FJ06l0m6I2amP
        27
    m16FJ06l0m6I2amP  
       2022-06-28 16:07:30 +08:00
    如果需要移动节点路径的话真没啥万全法。
    linuxyz
        28
    linuxyz  
       2022-06-28 16:57:15 +08:00   ❤️ 1
    LLaMA2
        29
    LLaMA2  
       2022-06-28 17:07:45 +08:00
    https://typeorm.bootcss.com/tree-entities
    看看 ORM 中怎么做的,然后自己取舍
    linuxyz
        30
    linuxyz  
       2022-06-28 18:27:35 +08:00
    @linuxyz 從首頁跳過來的,沒注意是在 MySQL 版, 看起來是樓主是問比較老版本的 MySQL 了, 看看能不能把數據導入内存重建 Tree ?
    wxf666
        31
    wxf666  
       2022-06-28 18:35:28 +08:00
    @n0trace 邻接表类型,移动节点,不是一条 update xxx set parent_id = ? 即可吗
    someonedeng
        32
    someonedeng  
       2022-06-28 18:54:22 +08:00
    冗余 path

    a,b,c,d

    select a,b*
    wxf666
        33
    wxf666  
       2022-06-28 19:04:41 +08:00
    @kkkiio 树结构庞大,CTE 比不过原因是啥?查 parent_id 索引难命中缓存?

    那加个 root_id 字段,索引 (root_id, parent_id),是不是同一棵树的索引都尽量集中到一块儿去就好了
    Nooooobycat
        34
    Nooooobycat  
       2022-06-28 19:08:26 +08:00
    这种情况下,能否考虑一下图数据库?
    pank
        35
    pank  
       2022-07-15 10:21:28 +08:00
    @Nooooobycat ,图数据库肯定可以做到,我之前写过一个 demo 专门测过,把部门和人全部导入到了 neo4j, 查询部门及子部门下所有用户,实测在本地性能并不高。也有可能是我本地电脑性能不够好。后来领导担心这个没人用过,而且有杀鸡用牛刀的嫌疑,就放弃这个方案了。这么多方案综合考虑下来,还是左右值编码的方案最简单,但是它也不完美,查询一批部门下的用户的时候,就需要用 or
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5577 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 02:22 · PVG 10:22 · LAX 18:22 · JFK 21:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.