精华内容
下载资源
问答
  • 如何将树形结构存储在数据库
    千次阅读
    更多相关内容
  • 数据库树形结构存储方法的选择

    千次阅读 2021-02-04 17:27:58
    树形结构存储方法的选择 简单的方法跟踪多级回复构成的树形分支:parent_id 一开始的思路 使用parent_id跟踪分支 使用先找出所有节点,按照一定顺序整合成树形结构 缺陷: 在深度过深时仅用parent_id需要执行很多...

    树形结构存储方法的选择

    简单的方法跟踪多级回复构成的树形分支:parent_id

    一开始的思路

    1. 使用parent_id跟踪分支
    2. 使用先找出所有节点,按照一定顺序整合成树形结构

    缺陷:

    • 在深度过深时仅用parent_id需要执行很多次SQL才能获取给定主题的所有数据
    • 每天的数据变动可能非常大,每访问一次整合一次过于浪费时间且不切实际

    目标:一个更好的存储多级结构及简单高效获取一个完整分支的方法

    分层存储合查询

    树形结构举例:组织架构图、线程化讨论

    解决方案

    邻接表

    依赖父节点构成的邻接表,由parent_id指向另一个元素的id作为父节点

    在这里插入图片描述

    缺陷:无法查询一个节点的所有后代

    可使用关联查询来获取一条评论和它的直接后代

    select * from c1.*,c2.* 
    from Comments c1 left outer join Comments c2
    on c2.parent_id = c1.id
    

    只能获取两层数据

    树的特性:可以任意深地扩展

    缺陷:

    • 每想多查一层就得多一个连接,而SQL查询最多4层

    • 聚合函数的使用很困难例如count()

    • 可能只需部分子树信息/聚合信息

    • 删除困难,要删除某个节点困难必须删除某颗子树,通过多次查询找到所有后代 ,再从最低级逐个删除满足外键完整性,parent_id也是一个外键,只不过连接的表还是本表

    在这里插入图片描述

    • 如果想删除某个节点并提升其子节点就必须修改子节点parent_id再删除这个节点

    优势:

    • 增加一个叶子节点

      insert into Comments(bug_id,parent_id,author,comment)
      values(1234,7,'kukla','Thanks!')
      
    • 修改一个节点的位置或者一颗子树的位置

      update comments set parent_id = 3 where comment_id = 6
      
    小结

    简单,但有些操作例如删除、查询、提升子节点要付出额外代价,增加/修改简单

    如果有一下问题,说明需要考虑其他实现方案

    1. 我们的树结构支持多少层

      在纠结不适用递归查询获取一个给定节点的所有祖先或者后代

      只支持有限层级操作,但多少层才能满足需求

    2. 我总是很怕解除那些管理树结构的代码

      每一项技术都能使一些任务变得很简单,但通常是以其他任务变得复杂为代价的,选择方案应该应对合适的场景

    3. 我需要一个脚本定期清理树种孤立节点的数据

      因为删除非叶子节点产生了一些迷失节点,采用其他数据结构后也要保证树结构的数据一致性

    合理使用反模式

    如果获取直接父子节点/插入新节点 如果这两个操作能满足现下所有需求,那么使用邻接表就能很好的工作了

    不要过度设计

    其他解决方案

    路径枚举

    解决邻接表获取祖先节点困难的问题

    使用path字段将层级信息组合,例如/usr/local/lib这种类似的存储结构

    在这里插入图片描述

    可通过比较每个节点的路径来查询一个节点的祖先

    缺陷:

    1. 数据库不能确保路径的格式总是正确或者路径种的节点确实存在。
    2. 依赖于应用程序的逻辑代码来维护路径的字符串,并且验证字符串的正确性的开销很大。
    3. 无论path设置为多大都存在长度限制,无法达到树形结构无限扩展的特性

    优势:

    1. 很好的支持祖先的查找
    2. 支持深度查询

    嵌套集

    存储子孙节点的相关信息而不是节点的直接祖先。通过两个数字nsleft及nsright来存储

    在这里插入图片描述

    nsleft:所有小于该节点的后代id

    nsright:所有大于该节点的后代id

    这些数字和comment_id没有任何关系,通过深度遍历逐层分配nsleft的值,并在返回时依次递增地分配nsleft的值并在返回时一次递增地分配nsright的值。

    在这里插入图片描述

    根据他们来找到给定节点的祖先/后裔

    栗子:

    寻找4的所有后裔

    select * from comment c1 join comment c2

    on c2.nsleft between c1.nsleft and c2.nsright

    where c1.comment_id = 4

    优势:

    1. 想删除某个非叶子节点,它的后代会自动代替被删除的节点,称为其直接祖先节点的直接后代。节点虽然是有序分配,但删除一个并不会队范围查询造成影响。

    缺陷:

    1. 获取直接父节点/后代变得比较复杂
    2. 对树进行操作,比如插入和移动比其他设计复杂得多,需要重新遍历计算n左右值

    优势:

    如果简单快速的查询是重要部门,嵌套集是最佳选择

    频繁的插入、删除就不适合

    闭包表

    额外创建TreePaths的表,包含两列,每一列都是指向Comments种comment_id的外键

    在这里插入图片描述

    在这里插入图片描述

    获取祖先/后代更加直接

    获取评论4的后代:

    等同于查询所有祖先节点是4的节点信息

    select c.*

    from comments as c

    join treepaths as t on c.comment_id = t.descendant

    where t.ancestor = 4;

    获取6的祖先:

    查询所有后裔为6的节点

    select c.*

    from comments c join treepaths t on c.comment_id = t.ancestor

    where t.descendant = 6;

    插入一个5的新的叶子节点:

    首先插入一条自己到自己的关系,然后搜索treepaths 表中后代是评论5的节点,增加该节点和新插入节点的“祖先-后代”关系

    然后插入新节点“祖先-后代”的关系

    insert into treepaths (ancestor,decendant)

    select t.ancestor,8

    from treepaths as t

    where t.descendant = 5

    union all

    select 8,8

    删除一颗完整子树

    删除评论4及其后代

    删除所有在treepaths表中后代为4的行以及那些以评论#4的后代为后代的行

    删除4及其子节点的关系,删除其他节点到4的子节点的关系

    delete from treepaths

    where descendant in (

    select descendant from treepaths where ancestor = 4

    )

    这样的删除并非删除掉节点,只是删除了关系,把层次结构分离使得设计更加灵活

    移动

    要移动树则先端开子树与祖先们的关系:找到这颗子树的顶点,删除它的所有子节点和它的所有祖先节点之间的关系。

    比如把6移动到3下

    首先把自我引用删掉

    delete from treepaths where descendant in (

    ​ select descendant from treepaths where ancestor = 6

    )and ancestor in (

    ​ select ancestor from treepaths where descendant = 6 and ancestor != descendant

    )

    查询评论6的祖先(不包括自身)以及评论6的后代(包括自身),然后删除他们之间的关系,正确地移除评论6的祖先到评论6和它的后代之间的路径。删除 (1,6 )(1,7 )(4,6 )(4,7 )不会删除(6,6 )(6,7 )

    再建立关系

    对比

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

    总结

    1. 邻接表最方便
    2. 如果支持with/connect by prior的递归查询能使邻接表更为高效
    3. 枚举路径直观展示出祖先到后代之间的路径,但同时由于它不能确保引用完整性,设计非常脆弱。存储也冗余
    4. 嵌套集是一个聪明的解决方案,但不能确保引用完整性。最好在一个查询性能要求高而对其他要求一般的场合使用
    5. 闭包表是最通用的设计,并且上述的设计中只有它能允许一个节点属于多棵树。它要求一张额外的表来存储关系,使用空间换时间的方案减少操作过程中由冗余的计算锁造成的消耗

    如果简单就用邻接表但如果复杂,要查询整个树结构就用闭包表

    跟着需求进行分析与设计

    展开全文
  • 现在有一个要存储一下公司的人员结构,大致层次结构如下 怎么存储这个结构?并且要获取以下信息: 1.查询小天的直接上司; 2.查询老宋管理下的直属员工; 3.查询小天的所有上司; 4.查询老王管理的所有员工。 方案...

    问题

    现在有一个要存储一下公司的人员结构,大致层次结构如下

    在这里插入图片描述
    怎么存储这个结构?并且要获取以下信息:
    1.查询小天的直接上司;
    2.查询老宋管理下的直属员工;
    3.查询小天的所有上司;
    4.查询老王管理的所有员工。

    方案一 Adjacency List(存储父节点)

    Adjacency List(邻接表)是只存储当前节点的父节点ID。

    数据库存储结构

    -- ----------------------------
    -- Table structure for employees
    -- ----------------------------
    DROP TABLE IF EXISTS `employees`;
    CREATE TABLE `employees`  (
      `eid` int(11) NOT NULL COMMENT '主键ID',
      `ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名',
      `position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置',
      `parent_id` int(11) NULL DEFAULT NULL COMMENT '上级ID',
      PRIMARY KEY (`eid`) USING BTREE
    ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
    
    -- ----------------------------
    -- Records of employees
    -- ----------------------------
    INSERT INTO `employees` VALUES (1, '老王', '高管', 0);
    INSERT INTO `employees` VALUES (2, '老宋', '产品部主管', 1);
    INSERT INTO `employees` VALUES (3, '老牛', '技术部主管', 1);
    INSERT INTO `employees` VALUES (4, '小吴', '产品A组长', 2);
    INSERT INTO `employees` VALUES (5, '小李', '产品B组长', 2);
    INSERT INTO `employees` VALUES (6, '小欢', '产品经理', 3);
    INSERT INTO `employees` VALUES (7, '小小', '产品经理', 3);
    INSERT INTO `employees` VALUES (8, '小天', '产品部员工', 4);
    INSERT INTO `employees` VALUES (9, '小里', '产品部员工', 4);
    INSERT INTO `employees` VALUES (10, '小黑', '产品部员工', 5);
    INSERT INTO `employees` VALUES (11, '小胡', '产品部员工', 5);
    INSERT INTO `employees` VALUES (12, '小丽', '技术部员工', 6);
    INSERT INTO `employees` VALUES (13, '小蓝', '技术部员工', 6);
    INSERT INTO `employees` VALUES (14, '小黄', '技术部员工', 7);
    INSERT INTO `employees` VALUES (15, '小真', '技术部员工', 7);
    

    如图所示:
    在这里插入图片描述

    SQL示例

    1.添加节点

    比如在小吴节点下,再次插入一个M节点

    INSERT INTO employees ( eid, ename, position, parent_id )
    VALUES ( 16, 'M', '产品部员工', 4 );
    

    2.查询小天的直接上司

    SELECT
    	e2.eid,
    	e2.ename 
    FROM
    	employees e1,
    	employees e2 
    WHERE
    	e1.parent_id = e2.eid 
    	AND e1.ename = '小天';
    

    在这里插入图片描述

    3.查询老宋管理下的直属员工

    SELECT
    	e1.eid,
    	e1.ename 
    FROM
    	employees e1,
    	employees e2 
    WHERE
    	e1.parent_id = e2.eid 
    	AND e2.ename = '老宋';
    

    在这里插入图片描述

    4.查询小天的所有上司

    这里肯定没法直接查,只能用循环进行循环查询,先查直接上司,再查直接上司的直接上司,依次循环,这样麻烦的事情,得先建立一个函数:

    -- 函数
    CREATE DEFINER=`root`@`localhost` FUNCTION `getSuperiors`(`uid` int) RETURNS varchar(1000) CHARSET utf8mb4
    BEGIN
        DECLARE superiors VARCHAR(1000) DEFAULT '';
        DECLARE sTemp INTEGER DEFAULT uid;
        DECLARE tmpName VARCHAR(20);
    
        WHILE (sTemp>0) DO
            SELECT parent_id into sTemp FROM employees where eid = sTemp;
            SELECT ename into tmpName FROM employees where eid = sTemp;
            IF(sTemp>0)THEN
                SET superiors = concat(tmpName,',',superiors);
            END IF;
        END WHILE;
            SET superiors = LEFT(superiors,CHARACTER_LENGTH(superiors)-1);
        RETURN superiors;
    END;
    
    -- 查询子节点的全部父节点
    select getSuperiors(11) as superior;
    
    

    在这里插入图片描述
    ps:显然获取子节点的全部父节点的时候很麻烦

    5.查询老王管理的所有员工

    先获取所有父节点为老王id的员工id,然后将员工姓名加入结果列表里,在调用一个神奇的查找函数,即可进行神奇的查找:

    -- 函数
    CREATE DEFINER=`root`@`localhost` FUNCTION `getSubordinate`(`uid` int) RETURNS varchar(2000) CHARSET utf8mb4
    BEGIN   
    DECLARE str varchar(1000);  
    DECLARE cid varchar(100);
    DECLARE result VARCHAR(1000);
    DECLARE tmpName VARCHAR(100);
    SET str = '$';   
    SET cid = CAST(uid as char(10));   
    WHILE cid is not null DO   
      SET str = concat(str, ',', cid); 
      SELECT group_concat(eid) INTO cid FROM employees where FIND_IN_SET(parent_id,cid);         
    END WHILE;
      SELECT GROUP_CONCAT(ename) INTO result FROM employees WHERE FIND_IN_SET(parent_id,str);
    RETURN result;   
    END;
    
    -- 查询父节点下的所有子节点
    SELECT getSubordinate(2);
    

    在这里插入图片描述

    总结:
    优点:存储的信息少,查直接上司和直接下属的时候很方便;
    缺点:多级查询时较复杂,无论是SELECT还是DELETE都可能涉及到获取所有子节点的问题;
    这种方法适合只需要用到直接上下级关系的时候,可以节省很多空间。

    方案二 Path Enumeration(存储路径)

    Path Enumeration 路径枚举法,存储根节点到每个子节点的路径

    数据库存储结构

    -- ----------------------------
    -- Table structure for employees2
    -- ----------------------------
    DROP TABLE IF EXISTS `employees2`;
    CREATE TABLE `employees2`  (
      `eid` int(11) NOT NULL COMMENT '主键ID',
      `ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名',
      `position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置',
      `path` varchar(200) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '所在路径',
      PRIMARY KEY (`eid`) USING BTREE
    ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
    
    -- ----------------------------
    -- Records of employees2
    -- ----------------------------
    INSERT INTO `employees2` VALUES (1, '老王', '高管', '/1');
    INSERT INTO `employees2` VALUES (2, '老宋', '产品部主管', '/1/2');
    INSERT INTO `employees2` VALUES (3, '老牛', '技术部主管', '/1/3');
    INSERT INTO `employees2` VALUES (4, '小吴', '产品A组长', '/1/2/4');
    INSERT INTO `employees2` VALUES (5, '小李', '产品B组长', '/1/2/5');
    INSERT INTO `employees2` VALUES (6, '小欢', '产品经理', '/1/3/6');
    INSERT INTO `employees2` VALUES (7, '小小', '产品经理', '/1/3/7');
    INSERT INTO `employees2` VALUES (8, '小天', '产品部员工', '/1/2/4/8');
    INSERT INTO `employees2` VALUES (9, '小里', '产品部员工', '/1/2/4/9');
    INSERT INTO `employees2` VALUES (10, '小黑', '产品部员工', '/1/2/5/10');
    INSERT INTO `employees2` VALUES (11, '小胡', '产品部员工', '/1/2/5/11');
    INSERT INTO `employees2` VALUES (12, '小丽', '技术部员工', '/1/3/6/12');
    INSERT INTO `employees2` VALUES (13, '小蓝', '技术部员工', '/1/3/6/13');
    INSERT INTO `employees2` VALUES (14, '小黄', '技术部员工', '/1/3/7/14');
    INSERT INTO `employees2` VALUES (15, '小真', '技术部员工', '/1/3/7/15');
    
    

    如图所示:
    在这里插入图片描述

    SQL示例

    1.添加节点

    要插入自己,然后查出父节点的Path,并且把自己生成的ID更新到path中去。比如,要在小吴节点后面插入M节点

    -- 1.插入自己M,eid为16
    INSERT INTO employees2 ( eid, ename, position, path )
    VALUES ( 16, 'M', '产品部员工', '' );
    -- 2.查出小吴的path为/1/2/4
    SELECT path FROM employees2  WHERE eid=4
    -- 3.更新M的path为/1/2/4/16
    UPDATE employees2 SET path='/1/2/4/16' WHERE eid= 16; 
    

    2.查询小天的直接上司

    在上一个解决方案中能轻而易举做到的事情,在这个方案中却有些麻烦了,因为需要对path字段进行字符串处理,去掉“/”+自身id才是直接上司的path值。

    SELECT
    	e1.eid,
    	e1.ename 
    FROM
    	employees2 e1,
    	employees2 e2 
    WHERE
    	e2.ename = '小天' 
    	AND e1.path = REPLACE ( e2.path, CONCAT( '/', e2.eid ), '' );
    

    在这里插入图片描述

    3.查询老宋管理下的直属员工

    怎么查管理下的直属员工呢?那就要用模糊查询了;使用正则匹配,匹配所有path符合规则的记录

    SELECT
    	e2.eid,
    	e2.ename 
    FROM
    	employees2 e1,
    	employees2 e2 
    WHERE
    	e1.ename = '老宋' 
    	AND e2.path REGEXP CONCAT( e1.path, '/[0-9]{1,}$' );
    

    在这里插入图片描述

    4.查询小天的所有上司

    这里就能体现这种存储结构的优势了。不看效率的话,还是很方便的

    SELECT
    	e1.eid,
    	e1.ename 
    FROM
    	employees2 e1,
    	employees2 e2 
    WHERE
    	e2.ename = '小天' 
    	AND e2.path LIKE concat( e1.path, '/%' );
    

    在这里插入图片描述

    5.查询老王管理的所有员工

    不用像之前那样写一大段存储过程了,简单粗暴

    SELECT
    	e2.eid,
    	e2.ename 
    FROM
    	employees2 e1,
    	employees2 e2 
    WHERE
    	e1.ename = '老王' 
    	AND e2.path LIKE concat( e1.path, '/%' );
    

    在这里插入图片描述

    总结:
    优点:多级查询十分方便;
    缺点:插入节点稍微麻烦些;查询直接上下级的时候稍微复杂;path字段的长度是有限的,不能无限制的增加节点深度;
    这种方法适用于存储小型的树结构。

    方案三 Closure Table(存储关系表和深度)

    Closure Table 终结表法,保存每个节点与其各个子节点的关系,也就是记录以其为根节点的全部子节点信息。

    数据库存储结构

    -- ----------------------------
    -- Table structure for employees3
    -- ----------------------------
    DROP TABLE IF EXISTS `employees3`;
    CREATE TABLE `employees3`  (
      `eid` int(11) NOT NULL COMMENT '主键ID',
      `ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名',
      `position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置',
      PRIMARY KEY (`eid`) USING BTREE
    ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
    
    -- ----------------------------
    -- Records of employees3
    -- ----------------------------
    INSERT INTO `employees3` VALUES (1, '老王', '高管');
    INSERT INTO `employees3` VALUES (2, '老宋', '产品部主管');
    INSERT INTO `employees3` VALUES (3, '老牛', '技术部主管');
    INSERT INTO `employees3` VALUES (4, '小吴', '产品A组长');
    INSERT INTO `employees3` VALUES (5, '小李', '产品B组长');
    INSERT INTO `employees3` VALUES (6, '小欢', '产品经理');
    INSERT INTO `employees3` VALUES (7, '小小', '产品经理');
    INSERT INTO `employees3` VALUES (8, '小天', '产品部员工');
    INSERT INTO `employees3` VALUES (9, '小里', '产品部员工');
    INSERT INTO `employees3` VALUES (10, '小黑', '产品部员工');
    INSERT INTO `employees3` VALUES (11, '小胡', '产品部员工');
    INSERT INTO `employees3` VALUES (12, '小丽', '技术部员工');
    INSERT INTO `employees3` VALUES (13, '小蓝', '技术部员工');
    INSERT INTO `employees3` VALUES (14, '小黄', '技术部员工');
    INSERT INTO `employees3` VALUES (15, '小真', '技术部员工');
    
    -- ----------------------------
    -- Table structure for emp_relations
    -- ----------------------------
    DROP TABLE IF EXISTS `emp_relations`;
    CREATE TABLE `emp_relations`  (
      `root_id` int(11) NULL DEFAULT NULL COMMENT '根节点的eid',
      `depth` int(11) NULL DEFAULT NULL COMMENT '根节点到该节点的深度',
      `is_leaf` tinyint(1) NULL DEFAULT NULL COMMENT '该节点是否为叶子节点',
      `node_id` int(11) NULL DEFAULT NULL COMMENT '该节点的eid'
    ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
    
    -- ----------------------------
    -- Records of emp_relations
    -- ----------------------------
    INSERT INTO `emp_relations` VALUES (1, 0, 0, 1);
    INSERT INTO `emp_relations` VALUES (1, 1, 0, 2);
    INSERT INTO `emp_relations` VALUES (1, 1, 0, 3);
    INSERT INTO `emp_relations` VALUES (1, 2, 0, 4);
    INSERT INTO `emp_relations` VALUES (1, 2, 0, 5);
    INSERT INTO `emp_relations` VALUES (1, 2, 0, 6);
    INSERT INTO `emp_relations` VALUES (1, 2, 0, 7);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 8);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 9);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 10);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 11);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 12);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 13);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 14);
    INSERT INTO `emp_relations` VALUES (1, 3, 1, 15);
    INSERT INTO `emp_relations` VALUES (2, 0, 0, 2);
    INSERT INTO `emp_relations` VALUES (2, 1, 0, 4);
    INSERT INTO `emp_relations` VALUES (2, 1, 0, 5);
    INSERT INTO `emp_relations` VALUES (2, 2, 1, 8);
    INSERT INTO `emp_relations` VALUES (2, 2, 1, 9);
    INSERT INTO `emp_relations` VALUES (2, 2, 1, 0);
    INSERT INTO `emp_relations` VALUES (2, 2, 1, 11);
    INSERT INTO `emp_relations` VALUES (3, 0, 0, 3);
    INSERT INTO `emp_relations` VALUES (3, 1, 0, 6);
    INSERT INTO `emp_relations` VALUES (3, 1, 0, 7);
    INSERT INTO `emp_relations` VALUES (3, 2, 1, 12);
    INSERT INTO `emp_relations` VALUES (3, 2, 1, 13);
    INSERT INTO `emp_relations` VALUES (3, 2, 1, 14);
    INSERT INTO `emp_relations` VALUES (3, 2, 1, 15);
    INSERT INTO `emp_relations` VALUES (4, 0, 0, 4);
    INSERT INTO `emp_relations` VALUES (4, 1, 1, 8);
    INSERT INTO `emp_relations` VALUES (4, 1, 1, 9);
    INSERT INTO `emp_relations` VALUES (5, 0, 0, 5);
    INSERT INTO `emp_relations` VALUES (5, 1, 1, 10);
    INSERT INTO `emp_relations` VALUES (5, 1, 1, 11);
    INSERT INTO `emp_relations` VALUES (5, 1, 1, 12);
    

    表数据如下:
    在这里插入图片描述

    在这里插入图片描述

    SQL示例

    1.插入节点

    比如,要在小吴节点后面插入M节点:
    在插入M节点后,找出以小吴节点为后代的那些节点作为和M节点之间有后代关系,插入到数据表。

    -- 1.插入自己M,eid为16
    INSERT INTO employees2 ( eid, ename, position )
    VALUES ( 16, 'M', '产品部员工' );
    -- 2.查出以小吴为后代的节点数据
    SELECT * FROM emp_relations WHERE node_id=4
    -- 3.插入到数据表:深度+1作为和M节点的深度 
    INSERT INTO emp_relations ( root_id, depth, is_leaf, node_id )
    VALUES
    ( 1, 3, 0, 16 ),
    ( 2, 2, 0, 16 ),
    ( 4, 1, 0, 16 ),
    ( 16, 0, 1, 16 );
    

    2.查询小天的直接上司

    在关系表中找到node_id为小天id,depth为1的根节点id即可

    SELECT
    	e2.ename BOSS 
    FROM
    	employees3 e1,
    	employees3 e2,
    	emp_relations rel 
    WHERE
    	e1.ename = '小天' 
    	AND rel.node_id = e1.eid 
    	AND rel.depth = 1 
    	AND e2.eid = rel.root_id
    

    在这里插入图片描述

    3.查询老宋管理下的直属员工

    只要查询root_id为老宋eid且深度为1的node_id即为其直接下属员工id

    SELECT
    	e1.eid,
    	e1.ename 直接下属 
    FROM
    	employees3 e1,
    	employees3 e2,
    	emp_relations rel 
    WHERE
    	e2.ename = '老宋' 
    	AND rel.root_id = e2.eid 
    	AND rel.depth = 1 
    	AND e1.eid = rel.node_id
    

    在这里插入图片描述

    4.查询小天的所有上司。

    只要在关系表中找到node_id为小天eid且depth大于0的root_id即可

    SELECT
    	e2.eid,
    	e2.ename 上司 
    FROM
    	employees3 e1,
    	employees3 e2,
    	emp_relations rel 
    WHERE
    	e1.ename = '小天' 
    	AND rel.node_id = e1.eid 
    	AND rel.depth > 0 
    	AND e2.eid = rel.root_id
    

    在这里插入图片描述

    5.查询老王管理的所有员工

    SELECT
    	e1.eid,
    	e1.ename 下属 
    FROM
    	employees3 e1,
    	employees3 e2,
    	emp_relations rel 
    WHERE
    	e2.ename = '老王' 
    	AND rel.root_id = e2.eid 
    	AND rel.depth > 0 
    	AND e1.eid = rel.node_id
    

    在这里插入图片描述

    总结:
    优点:四个查询的复杂程度是一样的,而且可以让另一张表只存储跟节点紧密相关的信息,看起来更简洁;
    缺点:关系表会很庞大,当层次很深,结构很庞大的时候,关系表数据的增长会越来越快,相当于用空间效率来换取了查找上的时间效率

    对比

    树形结构在数据库中存储的三种方式就介绍完了,接下来对比一下三种方法:

    • 方案一:Adjacency List
      优点:只存储上级id,存储数据少,结构类似于单链表,在查询相邻节点的时候很方便,添加删除节点都比较简单。
      缺点:查询多级结构的时候会显得力不从心(无论是SELECT还是DELETE都可能涉及到获取所有子节点的问题)。
      适用场合:对多级查询需求不大的场景比较适用。

    • 方案二:Path Enumeration
      优点:查询多级结构的时候比较方便。查询相邻节点时也比较ok。增加或者删除节点的时候比较简单。
      缺点:需要存储的path值可能会很大,甚至超过设置的最大值范围,理论上无法无限扩张。
      适用场合:结构相对简单的场景比较适合。

    • 方案三:Closure Table
      优点:在查询树形结构的任意关系时都很方便。
      缺点:需要存储的数据量比较多,索引表需要的空间比较大,增加和删除节点相对麻烦。
      适用场合:纵向结构不是很深,增删操作不频繁的场景比较适用。

    参考:
    【MySQL疑难杂症】如何将树形结构存储在数据库中(方案一 Adjacency List)
    【MySQL疑难杂症】如何将树形结构存储在数据库中(方案二Path Enumeration)
    【MySQL疑难杂症】如何将树形结构存储在数据库中(方案三 Closure Table)
    mysql存储树形结构的数据

    展开全文
  • 崇德易城市数据
  • 今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢?  像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这样有深度的人,就很难驾驭了。  举个栗子:现在有一个...

      今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢?

      像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这样有深度的人,就很难驾驭了。

      举个栗子:现在有一个要存储一下公司的人员结构,大致层次结构如下:

     

      (画个图真不容易。。)

      那么怎么存储这个结构?并且要获取以下信息:

      1.查询小天的直接上司。

      2.查询老宋管理下的直属员工。

      3.查询小天的所有上司。

      4.查询老王管理的所有员工。

      

    方案一、(Adjacency List)只存储当前节点的父节点信息。

      CREATE TABLE Employees(
      eid int,
      ename VARCHAR(100),
            position VARCHAR(100),
      parent_id int
      )

      记录信息简单粗暴,那么现在存储一下这个结构信息:

      

      好的,现在开始进入回答环节:

      1.查询小天的直接上司:

       SELECT e2.eid,e2.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e1.ename='小天';

      

      2.查询老宋管理下的直属员工:

      SELECT e1.eid,e1.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e2.ename='老宋';

      

      3.查询小天的所有上司。

      这里肯定没法直接查,只能用循环进行循环查询,先查直接上司,再查直接上司的直接上司,依次循环,这样麻烦的事情,还是得先建立一个存储过程:

      睁大眼睛看仔细了,接下来是骚操作环节:

    CREATE DEFINER=`root`@`localhost` FUNCTION `getSuperiors`(`uid` int) RETURNS varchar(1000) CHARSET gb2312
    BEGIN
        DECLARE superiors VARCHAR(1000) DEFAULT '';
        DECLARE sTemp INTEGER DEFAULT uid;
        DECLARE tmpName VARCHAR(20);
    
        WHILE (sTemp>0) DO
            SELECT parent_id into sTemp FROM employees where eid = sTemp;
            SELECT ename into tmpName FROM employees where eid = sTemp;
            IF(sTemp>0)THEN
                SET superiors = concat(tmpName,',',superiors);
            END IF;
        END WHILE;
            SET superiors = LEFT(superiors,CHARACTER_LENGTH(superiors)-1);
        RETURN superiors;
    END

      这一段存储过程可以查询子节点的所有父节点,来试验一下 

     

      好的,骚操作完成。

      显然,这样。获取子节点的全部父节点的时候很麻烦。。

      4.查询老王管理的所有员工。

      思路如下:先获取所有父节点为老王id的员工id,然后将员工姓名加入结果列表里,在调用一个神奇的查找函数,即可进行神奇的查找:

    CREATE DEFINER=`root`@`localhost` FUNCTION `getSubordinate`(`uid` int) RETURNS varchar(2000) CHARSET gb2312
    BEGIN   
    DECLARE str varchar(1000);  
    DECLARE cid varchar(100);
    DECLARE result VARCHAR(1000);
    DECLARE tmpName VARCHAR(100);
    SET str = '$';   
    SET cid = CAST(uid as char(10));   
    WHILE cid is not null DO   
      SET str = concat(str, ',', cid);
      SELECT group_concat(eid) INTO cid FROM employees where FIND_IN_SET(parent_id,cid);         
    END WHILE;
      SELECT GROUP_CONCAT(ename) INTO result FROM employees WHERE FIND_IN_SET(parent_id,str);
    RETURN result;   
    END

      看神奇的结果:

     

      虽然搞出来了,但说实话,真是不容易。。。

      这种方法的优点是存储的信息少,查直接上司和直接下属的时候很方便,缺点是多级查询的时候很费劲。所以当只需要用到直接上下级关系的时候,用这种方法还是不错的,可以节省很多空间。后续还会介绍其它存储方案,并没有绝对的优劣之分,适用场合不同而已。

      本篇至此告一段落,欢迎大家继续关注。

     

    真正重要的东西,用眼睛是看不见的。
    展开全文
  • mysql 树形结构查询

    2014-04-29 16:20:37
    mysql 树形结构查询,使用存储过程,实现mysql的树形结构查询
  • Oracle SQL树形结构查询

    2020-12-16 11:19:59
    简单说来是将一个树状结构存储在一张表里,比如一个表中存在两个字段: id,parentid那么通过表示每一条记录的parent是谁,就可以形成一个树状结构。 用上述语法的查询可以取得这棵的所有记录。 其中COND1是根结点的...
  • Python数据结构之树形结构——数组存储 树:一种非线性结构,主要使用链表来存储,也可以使用数组存储。 本代码使用两种数组 元素数组:0,6,3,5,4,7,8,9,2 由于 0 索引不存储元素,所以用0代替 树数组: [0]...
  • Djangomptt是个Django第三方组件,目标是使Django项目能在数据库中存储层级数据(树形数据)。它主要实现了修改过的前序遍历算法,如果你对原理还不是很了解,可以看我的这篇文章。当然,使用mptt时,原理是可以不用...
  • mysql 存储树形结构

    千次阅读 2021-01-05 15:04:06
    像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这样有深度的人,就很难驾驭了。  举个栗子:现在有一个要存储一下公司的人员结构,大致层次结构如下:  (画个图真...
  • 使用路径存储法生成树结构,可以快速查找节点的后裔,以达到树结构维护过程中能高效率地执行操作。实验证明,将二者进行技术整合后,查找子树节点的效率将提高21%,不但可以进一步提升维护性能,而且使用户的操作...
  • 关系数据库表存储树形结构的方法; 单数据库表的实现; 多数据库表的实现;
  • 简单可用,适用于数据量较少的的树形结构。 2、 物化路径 这个简单,原来父节点位置记录了整个url。 id name url 1 a /4/3/2/1 2 b /4/3/2 3 c /4/3 4 ...
  • 一、数据库父子结构数据设计  大部分采用 parentId的形式来存储父id,并且只存储父id,祖父Id不存储。也可以添加存储层级级别或者层级关系等字段。 CREATE TABLE `t_resource` ( `id` varchar(255) NOT NULL ...
  • 以下内容给大家介绍了MYSQL通过Adjacency List (邻接表)来存储树形结构的过程介绍和解决办法,并把存储后的图例做了分析。 今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢? 像mysql这样的关系型...
  • 数据库存储树形结构的数据
  • 主要介绍了php实现的树形结构数据存取类,实例演示了以树形数据结构存取数据的实现方法,对于学习基于PHP的数据结构有一定的参考借鉴价值,需要的朋友可以参考下
  • 在数据库中储存树形结构

    千次阅读 2021-01-14 17:02:37
    以树状结构表示和存储数据是软件开发中的常见问题: XML / Markup语法解析器(例如Apache Xerces和Xalan XSLt)使用; PDF使用以下树结构:根节点->目录节点->页面节点->子页面节点。通常,PDF文件在...
  • 为了避免对于树形结构查询时的“递归”过程,基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案,来保存该树的数据。 第一次看见这种表结构,相信大部分人都不清楚左值(Lft)和右值(Rgt)是...
  • oracle中有connect by来实现,mysql没有这样的便捷途径,所以MySQL遍历数据表是我们经常会遇到的头痛问题,下面给大家介绍在Mysql数据库里通过存储过程实现树形的遍历,一起看看吧
  • 最近在开发jSqlBox过程中,想研究一下树形结构的和VO对象树的转换,突然发现一种新的树结构数据库存储方案,主要特点是用很多的数据库列来存储一个占位符(1或空值)。在网上搜索了一下,没有找到雷同的(也可能是我花...
  • 实验题目:二叉树存储结构的建立、遍历和应用 实验内容: 树型结构的遍历是树型结构算法的基础,本实验要求编写程序演示二叉树 的存储结构的建立方法、遍历过程以及应用。 实验要求: 1.至少采用两种方法,编写建立...
  • 在MongoDB中使用NoSQL数据库存储树状结构的三种方法
  • 今天小编就为大家分享一篇关于树存储结构的几种表示方法,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 关系数据库存储树形结构数据的理想实践, slideshare 搬运而来,非常不错
  • 树形结构数据存储方案之闭包表

    千次阅读 2019-03-13 19:05:50
    本人目前的项目是微信公众号的一个小型电商系统,需要将邀请好友模块优化成5级分销流程,参考此文章,我选用【闭包表】模式,树形结构数据存储方案全部介绍见另一篇文章。待本人项目完成奉上自己的项目流程及数据库...
  • MongoDB树形数据存储

    千次阅读 2017-11-14 01:25:34
    树形结构存储是一种非常典型的需求,例如菜单、省市区、栏目等等。 1. 关系型数据库 实现方式1 id、name、pid 将树形结构的每个节点作为一行存储,每个节点保存父节点的指针(pid)。优点是简单易懂,插入修改比较...
  • Query DSL + Java API 总结ES结构倒排索引元数据MappingDocument APISearch APIAggregations ES结构 倒排索引 元数据 Mapping Document API Search API Aggregations
  • 讨论在关系数据库中压缩存放树形数据结构的方法;数据一致性的保证;分析存储、检索算法的时空复杂度。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 103,529
精华内容 41,411
关键字:

树形结构存储

友情链接: Simple Subtraction.rar