树型结构数据存储实践

很多业务场景会遇到树形结构的数据，如公司的人员职级树、行政区划树等。
使用类似MySQL的数据库进行存储，需要将树形结构（二维）存储到行格式（一维）的db中。

本文介绍了树型结构数据存储的三种方式：Adjacency Table , Nested Set , Bridge Table (Closure Table)。

以下方法均基于场景：
设想一个职员团队树，节点中为职工工号id和职工名称，节点1指向2表示职工1属于职工2的团队：
在这里插入图片描述

我们有如下的操作：

  • 新增职工节点
  • 删除职工节点
  • 查询该职工节点下属的-1职工节点
  • 查询该职工节点的所有下属职工节点
  • 查询该职工节点的+1领导节点
  • 查询该职工节点的所有领导节点

Adjacency Table

最简单的，我们构建一个邻接表，表中记录了当前职工id及其领导职工id（pid），数据组织结构如下：

id 职工idname 职工姓名pid 职工+1领导的职工id
101Anull
102Bnull
103C101
104D101
………

则我们可以生成如下的sql建表语句：

CREATE TABLE `employee_adjacency_table` (
  `id` bigint NOT NULL COMMENT '职工id',
  `name` varchar(64) NOT NULL COMMENT '职工姓名',
  `pid` bigint COMMENT '+1领导的职工id',
  `deleted` tinyint DEFAULT 0 COMMENT '软删标记',
  PRIMARY KEY (`id`),
  KEY `idx_pid` (`pid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

新增职工节点

在节点108下插入叶子节点113:

INSERT INTO employee_adjacency_table (id,name,pid) VALUE (113,'M',108);

在105节点下插入非叶子节点113:

INSERT INTO employee_adjacency_table VALUE (113,'M',105);
-- 将105的-1子节点移植到113下
UPDATE employee_adjacency_table SET pid = 108 WHERE pid = 105;

删除职工节点

删除叶子节点111:

UPDATE employee_adjacency_table SET deleted = 1 where id = 111;

删除非叶子节点107，其叶子节点移植到107的+1领导节点下:

UPDATE employee_adjacency_table SET deleted = 1 where id = 107;
-- 查出107的领导节点，即105
SELECT pid FROM employee_adjacency_table WHERE id = 107 and deleted = 0 FOR UPDATE;
UPDATE employee_adjacency_table SET pid = 105 WHERE pid = 107;

查询该职工节点下属的-1职工节点

查询节点105下的-1子节点

SELECT * FROM employee_adjacency_table WHERE pid = 105 and deleted = 0

查询该职工节点的所有下属职工节点

查询节点105下的所有下属节点
需要每次查询一层数据，每次将查处的id作为pid查询条件继续查下一层，直到结果为空。

查询该职工节点的+1领导节点

查询节点109的+1领导节点

-- 查到109的+1领导节点，即105
SELECT pid FROM employee_adjacency_table WHERE id = 109 and deleted = 0;
SELECT * FROM  employee_adjacency_table WHERE id = 105 and deleted = 0;

查询该职工节点的所有领导节点

查询节点112的所有领导节点
需要每次查询一层数据，每次将查处的pid作为id查询条件继续查上一层，直到pid为null。

优缺点及适用场景

优点：结构简单，节点变更简单
缺点：查询多层级节点效率低

一般树形数据会在服务启动时从数据库导入全量数据到缓存中。适合节点数量不大，变更少，变更实时性要求低的场景

Nested Set

相比与Adjacency Table 使用pid记录父级节点， Nested Set使用一对值（left & right）刻画树的父子关系。

以102为root的树为例，将其转化为Nested Set形式，每个节点转化为一个数值范围 [left, right]，如下图所示：

在这里插入图片描述

层级关系由数据范围的包含关系表示。比如工号102的职工的范围是 [1,12], 其下属职工105的范围是 [2,9]，注意到叶子节点的left和right差值都是1。

则我们可以生成如下的sql建表语句：

CREATE TABLE employee_nested_set (
        `id` bigint NOT NULL COMMENT '职工id',
        `name` varchar(64) NOT NULL COMMENT '职工姓名',
        `left` int NOT NULL,
        `right` int NOT NULL,
        `deleted` tinyint DEFAULT 0 COMMENT '软删标记',
        PRIMARY KEY (`id`),
        KEY `idx_left` (`left`),
        KEY `idx_right` (`right`)
);

新增职工节点

我们要在职工110下面新增一个职工113，由于113是叶子结点，所以其left和right差值为1，且值必须在110的数值范围内，这样
只能将110的范围扩大，随之而来的是其右边值的统一扩大。

则新增的sql语句为(不能并发更新)：

-- 找到节点110的左右值，即[7,8]
SELECT left,right FROM employee_nested_set where id = 110 and deleted = 0 FOR UPDATE;

-- 更新右侧left和right值
UPDATE employee_nested_set SET left = left + 2 WHERE left > 8  and deleted = 0;
UPDATE employee_nested_set SET right = right + 2 WHERE right >= 8  and deleted = 0;

-- 插入值范围
INSERT INTO employee_nested_set (id,name,left,right) VALUE (113, "M", 8 , 9);

我们要在职工110下面新增一个职工113，由于113是叶子结点，所以其left和right差值为1，且值必须在110的数值范围内，这样
只能将110的范围扩大，随之而来的是其右边值的统一扩大。

如果要在105和109之间插入新节点114呢？

-- 找到109的左右值，即 [3,6]
SELECT left,right FROM employee_nested_set WHERE id = 109 AND deleted = 0;

UPDATE employee_nested_set SET left = left + 1 , right = right + 1 WHERE left >= 3 and deleted = 0;
UPDATE employee_nested_set SET left = left + 1 , right = right + 1 WHERE left >= 6+1+1 and deleted = 0;
INSERT INTO employee_nested_set (id,name,left,right) VALUE (114,'N',3,8);

删除职工节点

比如删除节点109，109的从属节点继承到109的领导节点下：

-- 找到109的左右值，即 [3,6]
SELECT left,right FROM employee_nested_set WHERE id = 109 AND deleted = 1;

UPDATE employee_nested_set SET left = left - 1,right = right - 1 WHERE left BETWEEN 3 AND 6;
UPDATE employee_nested_set SET left = left - 1,right = right - 1 WHERE left > 7;

查询该职工节点下属的-1职工节点

很麻烦，比如找到105的-1职工节点：

SELECT node.id, (COUNT(parent.id) - (sub_tree.depth + 1)) AS depth
FROM employee_nested_set AS node,
        employee_nested_set AS parent,
        employee_nested_set AS sub_parent,
        (
                SELECT node.id, (COUNT(parent.id) - 1) AS depth
                FROM employee_nested_set AS node,
                        employee_nested_set AS parent
                WHERE node.left BETWEEN parent.left AND parent.right
                        AND node.id = 105
                GROUP BY node.name
                ORDER BY node.left
        )AS sub_tree
WHERE node.left BETWEEN parent.left AND parent.right
        AND node.left BETWEEN sub_parent.left AND sub_parent.right
        AND sub_parent.id = sub_tree.id
GROUP BY node.id
HAVING depth <= 1
ORDER BY node.left;

查询该职工节点的所有下属职工节点

很方便，比如找职工105下所有的职工id：

-- 找到105的left和right，即[2,9]
SELECT left,right FROM employee_nested_set WHERE id = 105 and deleted = 0;
-- 找到2和9之间的left的节点
SELECT id FROM employee_nested_set WHERE left BETWEEN 2 AND 9 and deleted = 0;

查询该职工节点的+1领导节点

找到职工105的+1领导节点，即102。

比较trick的写法：

SELECT parent.id 
FROM employee_nested_set AS node, employee_nested_set AS parent 
WHERE parent.left < node.left 
AND parent.right > node.right 
AND node.id =105 
ORDER BY ( parent.right - parent.left ) ASC LIMIT 1;

查询该职工节点的所有领导节点

也很方便，比如找到职工110所有的领导节点：

-- 找到节点110的left和right，即[7,8]
SELECT left,right FROM employee_nested_set WEHERE id = 110 and deleted = 0;
-- 找到left<7 && right>8的节点即为其领导节点
SELECT id FROM employee_nested_set WHERE left < 7 and right > 8 and deleted = 0;

优缺点及适用场景

优点：适合查询所有下属节点的场景
缺点：数据从属关系不直观，变更操作复杂，时间复杂度高，且其他查询场景的sql语句复杂

适用于查询所有下属节点且节点变更频率低的场景，可以配合邻接表，邻接表作为变更入口，而Nested Set根据邻接表构造而成，查询所有下属节点的场景走NestSet

Bridge Table (Closure Table)

闭包表使用两张表记录数据，一张记录节点信息，一张记录ancestor节点到descendant节点之间的距离。

在这里插入图片描述

-- 节点信息表
CREATE TABLE `employee_node` (
  `id` bigint NOT NULL,
  `name` int NOT NULL,
  `deleted` tinyint NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 

-- 节点与下属节点之间的距离表
CREATE TABLE `employee_node_distance` (
  `id` bigint NOT NULL,
  `ancestor_id` bigint NOT NULL,
  `descendant_id` bigint NOT NULL,
  `distance` int NOT NULL,
  `deleted` tinyint NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `idx_anc_dist` (`ancestor_id`,`distance`),
  KEY `idx_desc_dist` (`descendant_id`,`distance`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4

新增职工节点

在节点110下插入叶子节点113:

INSERT INTO employee_node (id,name) VALUE (113,'M');

-- 查处descendant_id为110的所有ancestor_id和到110的距离
SELECT ancestor_id , distance FROM employee_node_distance
WHERE descendant_id = 110;

-- 根据上面查处的id和distance插入113的数据
INSERT INTO employee_node_distance (ancestor_id, descendant_id, distance) 
VALUES (113,113,0),(ancestorIdOf110,113,distanceOf110+1);

在105节点和109节点间插入非叶子节点113:

INSERT INTO employee_node (id,name) VALUE (113,'M');

-- 查出105的所有领导节点

-- 插入113和领导节点的距离

-- 查处所有109的下属节点

-- 插入113和下属节点的距离

-- 根据109及其下属节点到他们领导节点的距离（+1）

删除职工节点

删除节点105:

查询该职工节点下属的-1职工节点

很方便，比如查询105的-1职工节点：

SELECT descendant_id FROM employee_node_distance
WHERE ancestor_id = 105 and distance = 1 and deleted = 0;

查询该职工节点的所有下属职工节点

很方便，比如查询105下所有下属节点：

SELECT descendant_id FROM employee_node_distance 
WHERE ancestor_id = 105 and descendant_id != 105 and deleted = 0;

查询该职工节点的+1领导节点

很方便，比如查询109的+1领导节点，即105：

SELECT ancestor_id FROM employee_node_distance 
WHERE descendant_id = 109 and distance = 1 and deleted = 0;

查询该职工节点的所有领导节点

很方便，比如查询112的所有领导节点

SELECT ancestor_id FROM employee_node_distance 
WHERE descendant_id = 102 and ancestor_id != 102 and deleted = 0;

优缺点及适用场景

优点：满足各种场景查询，sql语句简单好理解
缺点：占用表空间大，空间复杂度O(N^2) N为节点个数，子节点变动需要更新所有领导节点数据

适用于节点数量少，但查询复杂的场景

参考

  • What are the options for storing hierarchical data in a relational database?
  • Managing Hierarchical Data in MySQL
  • Convert an Adjacency List to Nested Sets

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/778986.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【6】图像分类部署

【6】图像分类部署

【6】图像分类部署 文章目录 前言一、将pytorch模型转为ONNX二、本地终端部署2.1. ONNX Runtime部署2.2. pytorch模型部署&#xff08;补充&#xff09; 三、使用flask的web网页部署四、微信小程序部署五、使用pyqt界面化部署总结 前言 包括将训练好的模型部署在本地终端、web…
阅读更多...
ubuntu22 sshd设置

ubuntu22 sshd设置

专栏总目录 一、安装sshd服务 sudo apt updatesudo apt install -y openssh-server 二、配置sshd 使用文本编辑器打开/etc/ssh/sshd_config sudo vi /etc/ssh/sshd_config &#xff08;一&#xff09;配置sshd服务的侦听端口 建议将ssh的侦听端口改为7000以上的端口&#…
阅读更多...
Autosar Dcm配置-0x85服务配置及使用-基于ETAS软件

Autosar Dcm配置-0x85服务配置及使用-基于ETAS软件

文章目录 前言Dcm配置DcmDsdDcmDsp代码实现总结前言 0x85服务用来控制DTC设置的开启和关闭。某OEM3.0架构强制支持0x85服务，本文介绍ETAS工具中的配置 Dcm配置 DcmDsd 配置0x85服务 此处配置只在扩展会话下支持(具体需要根据需求决定)，两个子服务Disable为0x02,Enable…
阅读更多...
pytest使用报错（以及解决pytest所谓的“抑制print输出”）

pytest使用报错（以及解决pytest所谓的“抑制print输出”）

1. 测试类的类名问题 #codingutf-8import pytestclass TestClass1:def setup(self) -> None:print(setup)def test_01(self) -> None:print(test_01111111111111111111111)def test_02(self) -> None:print(test_02)以上述代码为例&#xff0c;如果类名是Test开头&am…
阅读更多...
Docker部署Seata与Nacos整合

Docker部署Seata与Nacos整合

本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 Docker部署Seata与Nacos整合 Docker 部署 Seata 与 Nacos 整合 运行所使用的 demo项目地址 …
阅读更多...
I2C接口+高度集成的电源管理芯片（PMIC）-iML1942

I2C接口+高度集成的电源管理芯片（PMIC）-iML1942

电源管理芯片 - iML1942是一个高度集成的电源管理IC为TFT液晶面板。它具有完整的I2C接口来编程各种参数。该设备包括一个针对AVDD的电流模式升压调节器&#xff0c;一个针对VBK1的同步升压转换器。VGL可选的反相转换器或负电荷泵调节器&#xff0c;VSS1负线性调节器&#xff0c…
阅读更多...
【C++：类的基础认识和this指针】

【C++：类的基础认识和this指针】

C的类与C语言的struct结构体有啥区别&#xff1f; 默认的访问限定符不同 类的简要 关键字&#xff1a;class{}里面是类的主体&#xff0c;特别注意&#xff1a;{}后面的&#xff1b;不可以省略类中的变量叫做成员变量&#xff0c;类中的函数叫做成员函数类中访问有三种访问权限…
阅读更多...
系统集成项目管理工程师第12章思维导图发布

系统集成项目管理工程师第12章思维导图发布

今天发布系统集成项目管理工程师新版第12章脑图的图片版
阅读更多...
Ubuntu基本环境配置

Ubuntu基本环境配置

#Jdk 安装 #--查看 已安装 的jdk软件 java -version # 安装jdk软件(如果有选择请选 y) sudo apt install openjdk-11-jdk # 自行学习 vi 或 vim 学习网址如下&#xff1a; # https://www.runoob.com/linux/linux-vim.html #-- 修改系统级 path : /etc/profile 文件 (注意要…
阅读更多...
加入新数据预测，基于黏菌优化算法SMA优化SVM支持向量机回归预测（多输入单输出）

加入新数据预测，基于黏菌优化算法SMA优化SVM支持向量机回归预测（多输入单输出）

加入新数据预测&#xff0c;基于黏菌优化算法SMA优化SVM支持向量机回归预测&#xff08;多输入单输出&#xff09; 1.数据均为Excel数据&#xff0c;直接替换数据就可以运行程序。 2.所有程序都经过验证&#xff0c;保证程序可以运行。 3.具有良好的编程习惯&#xff0c;程序…
阅读更多...
浏览器打不开网页、但是电脑有网络，解决办法(win11)

浏览器打不开网页、但是电脑有网络，解决办法(win11)

2023.07.06测试有效 华为电脑拿去免费拆机保养后&#xff0c;发现浏览器连接不上网了&#xff0c;但是&#xff01;微信又能登录得上&#xff0c;也就是说电脑还是有网的。 原文链接 一、问题截图 二、解决方法 1.右键打开“网络和Internet设置” 2.打开“代理” 3.将该选项设…
阅读更多...
Linux网络管理

Linux网络管理

一、linux网络管理 1.获取计算机的网络信息 基本语法&#xff1a; #ifconfig #ip address &#xff08;ip a&#xff09; 解析&#xff1a; ens33&#xff1a;默认网卡 lo&#xff1a;环回网卡&#xff0c;127.0.0.1作为固定ip代表本机 virbr0&#xff1a;虚拟网络接口&…
阅读更多...
centos执行yum相关命令报错的可能原因

centos执行yum相关命令报错的可能原因

文章目录 1. 执行yum命令是报下面一大帕拉2. 安装某个包报错&#xff0c;找不到这个包 1. 执行yum命令是报下面一大帕拉 最后一行报错&#xff0c;在repo文件中找不到空baseurl&#xff1a;xxx / x86_64 执行这行命令把这个找不到的 xxx 禁掉即可sudo yum-config-manager --di…
阅读更多...
Go 依赖注入设计模式

Go 依赖注入设计模式

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…
阅读更多...
《QT从基础到进阶·四十三》QPlugin插件多线程问题和只有插件dll没有头文件和lib文件时调用插件中的方法

《QT从基础到进阶·四十三》QPlugin插件多线程问题和只有插件dll没有头文件和lib文件时调用插件中的方法

1、插件和多线程问题&#xff1a; 创建插件对象不能放到多线程执行&#xff0c;不然报错&#xff1a;ASSERT failure in QWidget: "Widgets must be created in the GUlthread. //不能放在多线程执行 QPluginLoader pluginLoader(pluginsDir.absoluteFilePath(fileName))…
阅读更多...
系统测试-缺陷管理学习

系统测试-缺陷管理学习

目录 1、什么是缺陷 2、缺陷的类型 3、缺陷的交付物 4、缺陷报告的基本格式 1、什么是缺陷 就是软件最终的功能实现跟需求不一致的现象就是缺陷 2、缺陷的类型 做少了&#xff0c;做错了&#xff0c;做多了&#xff0c;做差了 3、缺陷的交付物 缺陷报告&#xff1a;也叫…
阅读更多...
Vue中Class数据绑定

Vue中Class数据绑定

Class数据绑定 数据绑定的一个常见需求场景是操作CSS class列表&#xff0c;因为class是attribute&#xff08;属性&#xff09;&#xff0c;我们可以和其他attribute一样使用v-bind 将它们和动态的字符串绑定。但是&#xff0c;在处理比较复杂的绑定时&#xff0c;通过拼接生…
阅读更多...
Wish卖家必读：如何安全有效地进行店铺测评

Wish卖家必读：如何安全有效地进行店铺测评

Wish以其独特的商业模式和先进的技术在电商领域独树一帜。作为北美和欧洲最大的移动电商平台之一&#xff0c;Wish拥有庞大的用户基础&#xff0c;其中90%的卖家来自中国&#xff0c;这不仅显示了其在全球电商市场中的影响力&#xff0c;也反映了其对中国卖家的吸引力。 Wish平…
阅读更多...
免费去马赛克软件，亲测支持视频和图片，这AI功能逆天了！

免费去马赛克软件，亲测支持视频和图片，这AI功能逆天了！

有小伙伴私信问阿星有什么去除马赛克的免费软件&#xff0c;求推荐好用的去马赛克软件。 市面上去马赛克的软件多如牛毛&#xff0c;但真正好用的真不多&#xff0c;而免费的是更少。今天阿星就分享一款 AI智能去马赛克软件&#xff0c;免费使用。软件支持去除图片和视频的马赛…
阅读更多...
打卡第4天----链表

打卡第4天----链表

通过学习基础，发现我的基本功还得需要再练练，思路得再更加清晰明了，这样子做算法题才能驾轻就熟。每天记录自己的进步。 一、两两交换 题目编号：24 题目描述： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本…
阅读更多...
最新文章

Copyright @ 2022~2023