专栏首页用户4352451的专栏如何使用MySQL关系型数据库存储树结构

如何使用MySQL关系型数据库存储树结构

背景

  1. 需求存储一个组织结构或者档案仓库,看到这个需求我们的第一个反应肯定就是树状结构,并且是一个多层多节点无限级树状机构。
  2. 我们目前使用的是mysql关系型数据库。那我们应该如何来实现这个结构关系呢?
  • 有3种存储的方式: 到目前为止我在实战中曾使用过三种方式来实现这种hierarchical-data:
    • Adjacency list (邻接表)
    • Closure table (闭包表)
    • Path enumeration (路径枚举)

基于个人需要这里主要了解闭包表。

Closure table (闭包表)

什么是闭包表

  1. 个人理解:通过一个表来存储树节点中任何两个节点之间的关系。
  2. 核心字段有三个值:
    • ancestor 父节点的id
    • descendant子节点的ID
    • depth 子节点与父节点之间的深度关系
  3. 根据真实数据模型理解一下
  1. 闭包表的SQL结构
CREATE TABLE `comment_path` (

  `ancestor` INT NOT NULL,
  `descendant` INT NOT NULL,
  `depth` TINYINT(5) NOT NULL,
  PRIMARY KEY (`ancestor`, `descendant`),
  INDEX `fk_comment_path_descendant_idx` (`descendant` ASC),
  INDEX `fk_comment_path_ancestor_idx` (`ancestor` ASC),
  CONSTRAINT `fk_comment_path_comment1`
    FOREIGN KEY (`ancestor`)
    REFERENCES `comment` (`id`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION,
  CONSTRAINT `fk_comment_path_comment2`
    FOREIGN KEY (`descendant`)
    REFERENCES `comment` (`id`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;
  1. 存放节点信息表
<-可以不要这个表->
CREATE TABLE `topic` (
  `id` INT NOT NULL AUTO_INCREMENT,
  `title` VARCHAR(256) NOT NULL,
  PRIMARY KEY (`id`))
ENGINE = InnoDB;

<-用户信息,可以是用户中心的表,也可以和票据信息表放一块->
CREATE TABLE `user` (
  `id` INT NOT NULL AUTO_INCREMENT,
  `name` VARCHAR(128) NOT NULL,
  PRIMARY KEY (`id`))
ENGINE = InnoDB;

<-票据信息表->
CREATE TABLE `comment` (
  `id` INT NOT NULL AUTO_INCREMENT,
  `value` VARCHAR(2048) NULL,
  `topic_id` INT NOT NULL,
  `user_id` INT NOT NULL,
  PRIMARY KEY (`id`),
  INDEX `fk_comment_topic_idx` (`topic_id` ASC),
  INDEX `fk_comment_user1_idx` (`user_id` ASC),
  CONSTRAINT `fk_comment_topic2`
    FOREIGN KEY (`topic_id`)
    REFERENCES `topic` (`id`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION,
  CONSTRAINT `fk_comment_user1`
    FOREIGN KEY (`user_id`)
    REFERENCES `user` (`id`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;
  1. 根据闭包表的关系我们怎么来表示库1的位置呢?
  • 从图中可知我们库1的位置会在闭包表中存储18条数据。因为库1有一个父节点还有16个子节点还有自己与自己的关系。
  • 在闭包表插入库1与柜1的关系。根据前序遍历规则,库1被标记为2 柜1被标记为3 两者的深度关系是1,所以插入的SQL是:
INSERT INTO `comment_path` (`ancestor`, `descendant`, `depth`) VALUES (2, 3, 1);
  1. 现在我们需要查询这个库1的所有子节点信息
  • 你把这些数据肯定都是以库1多为父节点的所以直接查库1的前序遍历的序号等于2就可以了。
  • 还有就是想查看库1中有多少个册,那我门加上depth =1就可以了。或者说子子节点有多少个凭证信息的数据那就是depth = 2
select c.* from comment c join comment_path cp on (c.id = cp.descendant) where cp.ancestor = 1 and depth = 1;
  1. 在这个树上添加一个票据1
    • 先在详情信息表进行插入信息(这个value其实也不用遵循前序遍历的的规则是自增的也OK的)
    • 然后在闭包表进行创建所有的关联关系。也就是说创建票据1我们得插入6条数据 5条父节点1条自己对自己。
    • 我们知道是从哪里插入的,也就是他的父节点是已知的。也就是他的父节点我们得动态查出来,得到这个父节点我们可以找到他的同一个子树下的几点,因为他两拥有的父节点都是一样的,或者找到他的上一层级的所有父节点包括他自己都属于新加的节点的父节点。 他自己是insert后的值是10
     insert into comment(value, topic_id, user_id) values('(10)我以gin食阼啦', 1, 2);
     
      insert into comment_path (ancestor, descendant, depth) select cp.ancestor, 10, cp.depth+1 from comment_path as cp where cp.descendant=6 union all select 10, 10, 0;
  1. 删除柜1下的所有数据
    • 那意思就是将以柜1为父节点的数据都删除掉。
    • 柜1的value为3
delete a from comment_path a join comment_path b on (a.descendant = b.descendant) where b.ancestor=3;
  1. 将册1移动到柜2底下
    • 将凭证1凭证2册1的父节点除了和自身相关的都进行删除。
    • 然后再插入除和他们自己相关的path之外的k节点再进行插入。
delete a from comment_path as a join comment_path as d on a.descendant = d.descendant left join comment_path as x on x.ancestor = d.ancestor and x.descendant = a.ancestor where d.ancestor = 册1 and x.ancestor is null;

insert into comment_path (ancestor, descendant, depth) select supertree.ancestor, subtree.descendant, supertree.depth+subtree.depth+1 from comment_path as supertree join comment_path as subtree where subtree.ancestor = 柜2 and supertree.descendant = 册1;

参考

https://www.jianshu.com/p/951b742fd137 https://time.geekbang.org/column/article/67856 https://github.com/Agileaq/Hierarchical_Design/blob/master/Closure.sql https://juejin.cn/post/6844903906112176141 https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E6%A0%91

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关系型数据库 MySQL 之 InnoDB 体系结构

    InnoDB 存储引擎是 MySQL 5.5 版本后的默认存储引擎,支持事务 ACID,回滚,系统崩溃恢复能力及多版本并发控制的事务安全,主要用于 OLTP 数...

    JiekeXu之路
  • 关系型数据库 MySQL 体系结构详解

    通过前面几篇文章学会如何安装 MySQL 以及基础知识后,我们还需要学习体系结构,MySQL 和 Oracle 体系结构类似,如果学过 Oracle 可以类比记...

    JiekeXu之路
  • MySQL数据库(六):体系结构和存储引擎

    一、mysql 体系结构 连接池:内存/cpu/进程数 管理工具:提供mysql数据库服务的软件自带的命令 sql接口:传递sql命令给mysqld进程 ...

    行 者
  • 【MySQL疑难杂症】如何将树形结构存储在数据库中(方案三 Closure Table)

      今天介绍将树形结构存储在数据库中的第三种方法——终结表(原谅我这生硬的翻译。。)。   继续用上一篇的栗子,下面是要存储的结构图: image.png  ...

    弗兰克的猫
  • 【MySQL疑难杂症】如何将树形结构存储在数据库中(方案二 Path Enumeration)

      今天来介绍把树形结构存入数据库的第二种方法——路径枚举法。   还是借用上一篇的栗子,为了方便大家查阅,我把图又原样搬过来了。 image.png   需...

    弗兰克的猫
  • 【MySQL疑难杂症】如何将树形结构存储在数据库中(方案一 Adjacency List)

      今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢?   像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这...

    弗兰克的猫
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    帅地
  • 【图文动画详解原理系列】1.MySQL 索引原理详解

    MySQL是一个开放源代码的关系数据库管理系统。原开发者为瑞典的MySQL AB公司,最早是在2001年MySQL3.23进入到管理员的视野并在之后获得广泛的应...

    一个会写诗的程序员
  • Nebula Graph 技术总监陈恒:图数据库怎么和深度学习框架进行结合?

    Nebula Graph 的技术总监在 09.24 - 09.30 期间同开源中国·高手问答的小伙伴们以「图数据库的设计和实践」为切入点展开讨论,包括:「图数据...

    NebulaGraph
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    Java3y
  • mysql索引结构与深分页优化

    B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

    开发架构二三事
  • 你不得不知道的 MySQL 优化原理(一)

    说起MySQL的查询优化,相信大家收藏了一堆奇淫技巧:不能使用SELECT *、不使用NULL字段、合理创建索引、为字段选择合适的数据类型….. 你是否真的理解...

    哲洛不闹
  • 大厂面试系列(八):数据库mysql相关

    zhaozhen
  • 从另外一个角度看什么是数据库

    或许你还能想到 Redis、Zookeeper,甚至是 Elasticsearch ……

    Java3y
  • 2020最新版MySQL数据库面试题(一)

    结构化查询语言(Structured Query Language)简称SQL,是一种数据库查询语言。

    July
  • SQL重要知识点梳理!

    有读者留言面试有点虚,数据库都忘的差不多了,与其临时抱佛脚,不如我们把MySQL的知识点梳理一遍,心中有知识点,面试不慌。

    Datawhale
  • MySQL性能优化(三):深入理解索引的这点事

    索引,对于良好的数据库性能非常关键。只要提及到数据库性能优化,都会首先想到“索引”,看看表中是否添加索引。尤其是当表中的数据量越来越大时,索引对性能的影响尤为突...

    xcbeyond
  • Mysql索引优化初体验(一)

    简单回顾一下Mysql的历史,Mysql 是一个关系型数据库管理系统,由瑞典 Mysql AB 公司开发,目前属于 Oracle 公司。关系型数据库将数据保存在...

    程序员小明
  • 精通CRUD,却搞不懂数据库的基本原理?

    作为一个程序员,不了解数据库怎么能行,那么数据库到底是个啥呢,作为一个Java工程师,平时和数据库打交道着实不少,所谓的CRUD其实就是对数据库进行增删改查的操...

    Java技术江湖

扫码关注云+社区

领取腾讯云代金券