AI 助理
备案控制台
开发者社区 数据库 文章 正文

MySQL实现嵌套集合模型

2017-11-16 1695
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
RDS MySQL Serverless 基础系列，0.5-2RCU 50GB
推荐场景：
学生管理系统数据库设计 搭建个人博客
RDS MySQL Serverless 高可用系列，价值2615元额度，1个月
云数据库 RDS MySQL，高可用系列 2核4GB
简介：

译文主要是介绍如何用MySQL来存储嵌套集合数据。在其中会增加一些自己的理解，也会删除掉一些自认为无用的废话。
这篇文章主要讲的是嵌套集合模型，所以邻接表不是本文的重点，简单略过就好。

也许这是原文地址，因为我也不知道这是不是原文。

介绍

什么是分层数据？

类似于树形结构，除了根节点和叶子节点外，所有节点都有用一个父节点和多个子节点。

那么，在MySQL中如何处理分层数据呢？

原文中介绍了两种分层结构模型：邻接表模型和嵌套集合模型。

邻接表模型(The Adjacency List Model)

首先，建立测试表，导入测试数据，

CREATE TABLE category(
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        parent INT DEFAULT NULL
);

INSERT INTO category VALUES
        (1,'ELECTRONICS',NULL),
        (2,'TELEVISIONS',1),
        (3,'TUBE',2),
        (4,'LCD',2),
        (5,'PLASMA',2),
        (6,'PORTABLE ELECTRONICS',1),
        (7,'MP3 PLAYERS',6),
        (8,'FLASH',7),
        (9,'CD PLAYERS',6),
        (10,'2 WAY RADIOS',6);

SELECT * FROM category ORDER BY category_id;
+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+
10 rows in set (0.00 sec)

在邻接表中，所有的数据均拥有一个Parent字段，用来存储它的父节点。当前节点为根节点的话，它的父节点则为NULL。
那么在遍历的时候，可以使用递归来实现查询整棵树，从根节点开始，不断寻找子节点（父节点->子节点->父节点->子节点）。

检索分层路径

一般需要获取一个分层结构的路径问题，那么

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

+-------------+----------------------+--------------+-------+
| lev1        | lev2                 | lev3         | lev4  |
+-------------+----------------------+--------------+-------+
| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+-------------+----------------------+--------------+-------+
6 rows in set (0.00 sec)

检索叶子节点

SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

检索指定路径

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

+-------------+----------------------+-------------+-------+
| lev1        | lev2                 | lev3        | lev4  |
+-------------+----------------------+-------------+-------+
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
+-------------+----------------------+-------------+-------+
1 row in set (0.01 sec)

邻接表的缺点

在检索路径的过程中，除了本层外，每一层都会对应一个LEFT JOIN，那么如果层数不定怎么办？或者层数过多？
在删除中间层的节点时，需要同时删除该节点下的所有节点，否则会出现孤立节点。

嵌套集合模型Nested Set Model

原文中主要的目的是介绍嵌套集合模型，如下

通过集合的包含关系，嵌套结合模型可以表示分层结构，每一个分层可以用一个Set来表示（一个圈），父节点所在的圈包含所有子节点所在的圈。

为了用MySQL来表示集合关系，需要定义连个字段left和right（表示一个集合的范围）。

CREATE TABLE nested_category (
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        lft INT NOT NULL,
        rgt INT NOT NULL
);

INSERT INTO nested_category VALUES
  (1,'ELECTRONICS',1,20),
  (2,'TELEVISIONS',2,9),
  (3,'TUBE',3,4),
  (4,'LCD',5,6),
  (5,'PLASMA',7,8),
  (6,'PORTABLE ELECTRONICS',10,19),
  (7,'MP3 PLAYERS',11,14),
  (8,'FLASH',12,13),
  (9,'CD PLAYERS',15,16),
  (10,'2 WAY RADIOS',17,18);

SELECT * FROM nested_category ORDER BY category_id;

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

由于left和right是MySQL的保留字，因此，字段名称用lft和rgt代替。每一个集合都是从lft开始到rgt结束，也就是集合的两个边界。

在树中也同样适用，

当为树状结构编号时，我们从左到右，一次一层，赋值按照从左到右的顺序遍历其子节点，这种方法称为先序遍历算法。

检索分层路径

由于子节点的lft值总在父节点的lft和rgt值之间，所以可以通过父节点连接到子节点上来检索整棵树。

SELECT node.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND parent.name = 'ELECTRONICS'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| TELEVISIONS          |
| TUBE                 |
| LCD                  |
| PLASMA               |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
| CD PLAYERS           |
| 2 WAY RADIOS         |
+----------------------+</pre>

这个方法并不需要考虑层数，而且不需要考虑节点的rgt。

检索所有叶子节点

由于每一个叶子节点的rgt=lft+1，那么只需要这一个条件即可。

SELECT name
FROM nested_category
WHERE rgt = lft + 1;

+--------------+
| name         |
+--------------+
| TUBE         |
| LCD          |
| PLASMA       |
| FLASH        |
| CD PLAYERS   |
| 2 WAY RADIOS |
+--------------+

检索节点路径

不再需要多个join连接操作。

SELECT parent.name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = 'FLASH'
ORDER BY node.lft;

+----------------------+
| name                 |
+----------------------+
| ELECTRONICS          |
| PORTABLE ELECTRONICS |
| MP3 PLAYERS          |
| FLASH                |
+----------------------+

检索节点深度

通过COUNT和GROUP BY函数来获取父节点的个数。

SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| ELECTRONICS          |     0 |
| TELEVISIONS          |     1 |
| TUBE                 |     2 |
| LCD                  |     2 |
| PLASMA               |     2 |
| PORTABLE ELECTRONICS |     1 |
| MP3 PLAYERS          |     2 |
| FLASH                |     3 |
| CD PLAYERS           |     2 |
| 2 WAY RADIOS         |     2 |
+----------------------+-------+

甚至可以得到分层的缩进结果，

SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+-----------------------+
| name                  |
+-----------------------+
| ELECTRONICS           |
|  TELEVISIONS          |
|   TUBE                |
|   LCD                 |
|   PLASMA              |
|  PORTABLE ELECTRONICS |
|   MP3 PLAYERS         |
|    FLASH              |
|   CD PLAYERS          |
|   2 WAY RADIOS        |
+-----------------------+

检索子树的深度

考虑到检索中需要自连接的node或parent，因此需要增加一个额外的连接来作为子查询来限制子树。

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| FLASH                |     2 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

检索节点的直接子节点

假设一个场景，当用户点击网站上电子产品的一个分类时，将呈现该分类下的产品，同时需要列出所有子分类，并不是全部分类。
为了限制显示分类的层数，需要使用HAVING字句，

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
        nested_category AS parent,
        nested_category AS sub_parent,
        (
                SELECT node.name, (COUNT(parent.name) - 1) AS depth
                FROM nested_category AS node,
                        nested_category AS parent
                WHERE node.lft BETWEEN parent.lft AND parent.rgt
                        AND node.name = 'PORTABLE ELECTRONICS'
                GROUP BY node.name
                ORDER BY node.lft
        )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
        AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth &lt;= 1
ORDER BY node.lft;

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| PORTABLE ELECTRONICS |     0 |
| MP3 PLAYERS          |     1 |
| CD PLAYERS           |     1 |
| 2 WAY RADIOS         |     1 |
+----------------------+-------+

增加新节点

上面已经介绍了如何检索结果，那么如何才能增加新的节点呢？

如果希望在TELEVISIONS和PROTABLE ELECTRONICS节点之间增加一个新的节点，那么新节点的lft和rgt的值应该是10和11，那么所有大于10的节点（新节点右侧的节点）的lft和rgt都应该加2，如上图所示。

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt &gt; @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft &gt; @myRight;

INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES

如果希望在叶子节点下增加节点，需要修改下查询语句，

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category

WHERE name = '2 WAY RADIOS';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt &gt; @myLeft;
UPDATE nested_category SET lft = lft + 2 WHERE lft &gt; @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES('FRS', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;```



###删除节点

删除叶子节点比较容易，只需要删除自己，而删除一个中间层节点就需要删除其所有子节点。在这个模型中，所有子节点的节点正好在lft和rgt之间。

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;


在某些情况下，只需要删除某个节点，但是并不希望删除该节点下的子节点数据。
通过把右侧所有节点的左右值-2，当前节点的子节点左右值-1

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';

DELETE FROM nested_category WHERE lft = @myLeft;

UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;

UNLOCK TABLES;


本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/p/4827757.html，如需转载请自行联系原作者

文章标签：
云数据库 RDS MySQL 版
关系型数据库
内存技术
MySQL
算法
存储
相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发，帮助IT从业者们通过“阿里云Web应用上云解决方案”，了解一个企业级Web应用上云的常见架构，了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。 &nbsp; 相关的阿里云产品：云数据库RDS MySQL 版 阿里云关系型数据库RDS（Relational Database Service）是一种稳定可靠、可弹性伸缩的在线数据库服务，提供容灾、备份、恢复、迁移等方面的全套解决方案，彻底解决数据库运维的烦恼。 了解产品详情:&nbsp;https://www.aliyun.com/product/rds/mysql&nbsp;
文艺小青年
目录
相关文章
ghost丶桃子
|
MySQL 关系型数据库 内存技术
MySQL实现嵌套集合模型
ghost丶桃子
3535 0
数据库知识分享者小北
|
19天前
|
存储 人工智能 OLAP
AI Agent越用越笨？阿里云AnalyticDB「AI上下文工程」一招破解！
AI 上下文工程是管理大模型输入信息的系统化框架，解决提示工程中的幻觉、上下文溢出与信息冲突等问题。通过上下文的采集、存储、加工与调度，提升AI推理准确性与交互体验。AnalyticDB PostgreSQL 版提供增强 RAG、长记忆、Supabase 等能力，助力企业构建高效、稳定的 AI 应用。
数据库知识分享者小北
275 2
阿里云瑶池数据库_
|
4月前
|
运维 算法 机器人
阿里云AnalyticDB具身智能方案：破解机器人仿真数据、算力与运维之困
本文将介绍阿里云瑶池旗下的云原生数据仓库AnalyticDB MySQL推出的全托管云上仿真解决方案，方案采用云原生架构，为开发者提供从开发环境、仿真计算到数据管理的全链路支持。
阿里云瑶池数据库_
957 2
阿里云瑶池数据库_
|
17天前
|
存储 人工智能 OLAP
AI Agent越用越笨？阿里云AnalyticDB「AI上下文工程」一招破解！
AI上下文工程是优化大模型交互的系统化框架，通过管理指令、记忆、知识库等上下文要素，解决信息缺失、长度溢出与上下文失效等问题。依托AnalyticDB等技术，实现上下文的采集、存储、组装与调度，提升AI Agent的准确性与协同效率，助力企业构建高效、稳定的智能应用。
阿里云瑶池数据库_
119 0
云浠Cherry
|
2月前
|
存储 人工智能 关系型数据库
阿里云AnalyticDB for PostgreSQL 入选VLDB 2025：统一架构破局HTAP，Beam+Laser引擎赋能Data+AI融合新范式
在数据驱动与人工智能深度融合的时代，企业对数据仓库的需求早已超越“查得快”这一基础能力。面对传统数仓挑战，阿里云瑶池数据库AnalyticDB for PostgreSQL（简称ADB-PG）创新性地构建了统一架构下的Shared-Nothing与Shared-Storage双模融合体系，并自主研发Beam混合存储引擎与Laser向量化执行引擎，全面解决HTAP场景下性能、弹性、成本与实时性的矛盾。 近日，相关研究成果发表于在英国伦敦召开的数据库领域顶级会议 VLDB 2025，标志着中国自研云数仓技术再次登上国际舞台。
云浠Cherry
263 0
阿里云瑶池数据库_
|
3月前
|
存储 人工智能 分布式计算
数据不用搬，AI直接炼！阿里云AnalyticDB AI数据湖仓一站式融合AI+BI
阿里云瑶池旗下的云原生数据仓库AnalyticDB MySQL版（以下简称ADB）诞生于高性能实时数仓时代，实现了PB级结构化数据的高效处理和分析。在前几年，为拥抱大数据的浪潮，ADB从传统数仓拓展到数据湖仓，支持Paimon/Iceberg/Delta Lake/Hudi湖格式，为开放的数据湖提供数据库级别的性能、可靠性和管理能力，从而更好地服务以SQL为核心的大规模数据处理和BI分析，奠定了坚实的湖仓一体基础。
阿里云瑶池数据库_
664 2
阿里云瑶池数据库_
|
4月前
|
存储 人工智能 关系型数据库
从“听指令”到“当参谋”，阿里云AnalyticDB GraphRAG如何让AI开窍
阿里云瑶池旗下的云原生数据仓库 AnalyticDB PostgreSQL 版 GraphRAG 技术，创新融合知识图谱动态推理+向量语义检索，通过实体关系映射与多跳路径优化，构建可应对复杂场景的决策引擎。本文将通过家电故障诊断和医疗预问诊两大高价值场景，解析其如何实现从“被动应答”到“主动决策”的跨越。
阿里云瑶池数据库_
448 0
探索云世界
|
5月前
|
分布式计算 运维 监控
Fusion 引擎赋能：流利说如何用阿里云 Serverless Spark 实现数仓计算加速
本文介绍了流利说与阿里云合作，利用EMR Serverless Spark优化数据处理的全过程。流利说是科技驱动的教育公司，通过AI技术提升用户英语水平。原有架构存在资源管理、成本和性能等痛点，采用EMR Serverless Spark后，实现弹性资源管理、按需计费及性能优化。方案涵盖数据采集、存储、计算到查询的完整能力，支持多种接入方式与高效调度。迁移后任务耗时减少40%，失败率降低80%，成本下降30%。未来将深化合作，探索更多行业解决方案。
探索云世界
284 1
探索云世界
|
5月前
|
SQL 存储 缓存
海量数据分页查询效率低？一文解析阿里云AnalyticDB深分页优化方案
本文介绍了AnalyticDB（简称ADB）针对深分页问题的优化方案。深分页是指从海量数据中获取靠后页码的数据，常导致性能下降。ADB通过快照缓存技术解决此问题：首次查询生成结果集快照并缓存，后续分页请求直接读取缓存数据。该方案在数据导出、全量结果分页展示及业务报表并发控制等场景下表现出色。测试结果显示，相比普通分页查询，开启深分页优化后查询RT提升102倍，CPU使用率显著降低，峰值内存减少至原方案的几分之一。实际应用中，某互联网金融客户典型慢查询从30秒优化至0.5秒，性能提升60+倍。
探索云世界
357 1

热门文章

最新文章

  • 1
    AI Agent越用越笨？阿里云AnalyticDB「AI上下文工程」一招破解！
  • 2
    AI Agent越用越笨？阿里云AnalyticDB「AI上下文工程」一招破解！
  • 3
    流计算迎来代际变革：流式湖仓 Flink + Paimon 加速落地、Flink CDC 重磅升级
  • 4
    【最佳实践】实时计算 Flink 版在金融行业的实时数仓建设实践
  • 5
    分析型数据库+数据传输，构建企业级实时数仓
  • 6
    AnalyticDB错误码文档
  • 7
    小打卡基于阿里云构建企业级数仓的实践及总结
  • 8
    实时数仓入门训练营：实时计算Flink版总体介绍
  • 9
    阿里云“玩转云上 StarRocks3.0 湖仓分析”训练营火热报名中，开启数据分析新范式
  • 10
    基于Flink构建全场景实时数仓
  • 1
    数仓高频操作JSON篇
    178
  • 2
    数仓面试重灾区之-Generic User-defined Table Generating Function(UDTF)
    128
  • 3
    闲侃数仓优化-大数据治理和优化
    177
  • 4
    AnalyticDB MySQL新购页面融合升级，提供企业版购买选项
    489
  • 5
    性能30%↑｜阿里云AnalyticDB*AMD EPYC，数据分析步入Next Level
    74615
  • 6
    性能30%↑｜阿里云AnalyticDB X AMD EPYC，数据分析步入Next Level
    718
  • 7
    阿里云 EMR Serverless StarRocks3.x，极速统一的湖仓新范式
    1294
  • 8
    大数据数仓建模基础理论【维度表、事实表、数仓分层及示例】
    4950
  • 9
    数仓常用分层与维度建模
    2583
  • 10
    企业数仓架构设计实践
    675

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云对象存储OSS收费标准：500G存储118元1年、