分层数据Hierarchical Data探索(2.邻接表模型)

Scott 发布于2019-07-01 12:48 / 877人阅读

摘要：分层数据探索例如无限级分类多级菜单省份城市引言第一篇分层数据探索递归已经介绍了分层数据以及使用递归算法实现了无限极分类，但是递归即浪费时间，又浪费空间内存尤其是在数据量大的情况下效率显著下降。

分层数据Hierarchical Data探索（例如：无限级分类、多级菜单、省份城市） 引言

第一篇分层数据Hierarchical Data探索(1.递归)已经介绍了分层数据以及使用递归算法实现了无限极分类，但是递归即浪费时间，又浪费空间（内存）,尤其是在数据量大的情况下效率显著下降。
那么，在MySQL中如何处理分层数据呢？下面我们来说一说数据模型邻接表模型

分层数据Hierarchical Data探索(1.递归 recursion)

分层数据Hierarchical Data探索(2.邻接表模型 Adjacency List Model)

分层数据Hierarchical Data探索(3.嵌套集合模型 Nested Set Model)

邻接表模型(Adjacency List Model)

更多 邻接表模型（Adjacency List Model）的介绍请见:wiki

# 为了模拟，我们创建一个表category包含三个字段：id，title，和parent_id如下：
CREATE TABLE category (
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
  title varchar(255) NOT NULL,
  parent_id int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (id),
  FOREIGN KEY (parent_id) REFERENCES category (id) 
    ON DELETE CASCADE ON UPDATE CASCADE
);

# 插入模拟数据
INSERT INTO category(title,parent_id) VALUES("Electronics",NULL);

INSERT INTO category(title,parent_id) VALUES("Laptops & PC",1);
 
INSERT INTO category(title,parent_id) VALUES("Laptops",2);
INSERT INTO category(title,parent_id) VALUES("PC",2);
 
INSERT INTO category(title,parent_id) VALUES("Cameras & photo",1);
INSERT INTO category(title,parent_id) VALUES("Camera",5);
 
INSERT INTO category(title,parent_id) VALUES("Phones & Accessories",1);
INSERT INTO category(title,parent_id) VALUES("Smartphones",7);
 
INSERT INTO category(title,parent_id) VALUES("Android",8);
INSERT INTO category(title,parent_id) VALUES("iOS",8);
INSERT INTO category(title,parent_id) VALUES("Other Smartphones",8);
 
INSERT INTO category(title,parent_id) VALUES("Batteries",7);
INSERT INTO category(title,parent_id) VALUES("Headsets",7);
INSERT INTO category(title,parent_id) VALUES("Screen Protectors",7);

select * from category;
+----+----------------------+-----------+
| id | title                | parent_id |
+----+----------------------+-----------+
|  1 | Electronics          |      NULL |
|  2 | Laptops & PC         |         1 |
|  3 | Laptops              |         2 |
|  4 | PC                   |         2 |
|  5 | Cameras & photo      |         1 |
|  6 | Camera               |         5 |
|  7 | Phones & Accessories |         1 |
|  8 | Smartphones          |         7 |
|  9 | Android              |         8 |
| 10 | iOS                  |         8 |
| 11 | Other Smartphones    |         8 |
| 12 | Batteries            |         7 |
| 13 | Headsets             |         7 |
| 14 | Screen Protectors    |         7 |
+----+----------------------+-----------+
14 rows in set (0.00 sec)

检索根节点

SELECT * FROM category WHERE parent_id IS NULL;
+----+-------------+-----------+
| id | title       | parent_id |
+----+-------------+-----------+
|  1 | Electronics |      NULL |
+----+-------------+-----------+
1 row in set (0.00 sec)

检索所有叶子节点

SELECT
    c1.id, c1.title
FROM
    category c1
        LEFT JOIN
    category c2 ON c2.parent_id = c1.id
WHERE
    c2.id IS NULL;
+----+-------------------+
| id | title             |
+----+-------------------+
|  3 | Laptops           |
|  4 | PC                |
|  6 | Camera            |
|  9 | Android           |
| 10 | iOS               |
| 11 | Other Smartphones |
| 12 | Batteries         |
| 13 | Headsets          |
| 14 | Screen Protectors |
+----+-------------------+
9 rows in set (0.00 sec)

检索整棵树的分层路径

SELECT t1.title AS lev1, t2.title as lev2, t3.title as lev3, t4.title as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent_id = t1.id
LEFT JOIN category AS t3 ON t3.parent_id = t2.id
LEFT JOIN category AS t4 ON t4.parent_id = t3.id
WHERE t1.title = "Electronics";
-------------+----------------------+-------------------+-------------------+
| lev1        | lev2                 | lev3              | lev4              |
+-------------+----------------------+-------------------+-------------------+
| Electronics | Laptops & PC         | Laptops           | NULL              |
| Electronics | Laptops & PC         | PC                | NULL              |
| Electronics | Cameras & photo      | Camera            | NULL              |
| Electronics | Phones & Accessories | Smartphones       | Android           |
| Electronics | Phones & Accessories | Smartphones       | iOS               |
| Electronics | Phones & Accessories | Smartphones       | Other Smartphones |
| Electronics | Phones & Accessories | Batteries         | NULL              |
| Electronics | Phones & Accessories | Headsets          | NULL              |
| Electronics | Phones & Accessories | Screen Protectors | NULL              |
+-------------+----------------------+-------------------+-------------------+
9 rows in set (0.00 sec)

检索单一指定路径

SELECT t1.title AS lev1, t2.title as lev2, t3.title as lev3, t4.title as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent_id = t1.id
LEFT JOIN category AS t3 ON t3.parent_id = t2.id
LEFT JOIN category AS t4 ON t4.parent_id = t3.id
WHERE t1.title = "Electronics" AND t4.title = "iOS";
+-------------+----------------------+-------------+------+
| lev1        | lev2                 | lev3        | lev4 |
+-------------+----------------------+-------------+------+
| Electronics | Phones & Accessories | Smartphones | iOS  |
+-------------+----------------------+-------------+------+
1 row in set (0.00 sec)

以下递归公用表达式（CTE）检索。请注意，MySQL 8.0以上版本，CTE功能已经支持

CTE 查询整棵树

WITH RECURSIVE category_path (id, title, path) AS
(
  SELECT id, title, title as path
    FROM category
    WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.title, CONCAT(cp.path, " > ", c.title)
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
+------+----------------------+----------------------------------------------------------------------+
| id   | title                | path                                                                 |
+------+----------------------+----------------------------------------------------------------------+
|    1 | Electronics          | Electronics                                                          |
|    5 | Cameras & photo      | Electronics > Cameras & photo                                        |
|    6 | Camera               | Electronics > Cameras & photo > Camera                               |
|    2 | Laptops & PC         | Electronics > Laptops & PC                                           |
|    3 | Laptops              | Electronics > Laptops & PC > Laptops                                 |
|    4 | PC                   | Electronics > Laptops & PC > PC                                      |
|    7 | Phones & Accessories | Electronics > Phones & Accessories                                   |
|   12 | Batteries            | Electronics > Phones & Accessories > Batteries                       |
|   13 | Headsets             | Electronics > Phones & Accessories > Headsets                        |
|   14 | Screen Protectors    | Electronics > Phones & Accessories > Screen Protectors               |
|    8 | Smartphones          | Electronics > Phones & Accessories > Smartphones                     |
|    9 | Android              | Electronics > Phones & Accessories > Smartphones > Android           |
|   10 | iOS                  | Electronics > Phones & Accessories > Smartphones > iOS               |
|   11 | Other Smartphones    | Electronics > Phones & Accessories > Smartphones > Other Smartphones |
+------+----------------------+----------------------------------------------------------------------+
14 rows in set (0.01 sec)

CTE 查询指定子树

查询id为 7 的 Phone & Accessories 的子树

WITH RECURSIVE category_path (id, title, path) AS
(
  SELECT id, title, title as path
    FROM category
    WHERE parent_id = 7
  UNION ALL
  SELECT c.id, c.title, CONCAT(cp.path, " > ", c.title)
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
+------+-------------------+---------------------------------+
| id   | title             | path                            |
+------+-------------------+---------------------------------+
|   12 | Batteries         | Batteries                       |
|   13 | Headsets          | Headsets                        |
|   14 | Screen Protectors | Screen Protectors               |
|    8 | Smartphones       | Smartphones                     |
|    9 | Android           | Smartphones > Android           |
|   10 | iOS               | Smartphones > iOS               |
|   11 | Other Smartphones | Smartphones > Other Smartphones |
+------+-------------------+---------------------------------+
7 rows in set (0.01 sec)

CTE 查询单个枝叶路径

从底部 iOS 到顶部 Electronics 的单个路径

WITH RECURSIVE category_path (id, title, parent_id) AS
(
  SELECT id, title, parent_id
    FROM category
    WHERE id = 10 -- child node
  UNION ALL
  SELECT c.id, c.title, c.parent_id
    FROM category_path AS cp JOIN category AS c
      ON cp.parent_id = c.id
)
SELECT * FROM category_path;
+------+----------------------+-----------+
| id   | title                | parent_id |
+------+----------------------+-----------+
|   10 | iOS                  |         8 |
|    8 | Smartphones          |         7 |
|    7 | Phones & Accessories |         1 |
|    1 | Electronics          |      NULL |
+------+----------------------+-----------+
4 rows in set (0.00 sec)

CTE 计算每个节点的层级

根节点为 0，每个子节点等于父节点加 1

WITH RECURSIVE category_path (id, title, lvl) AS
(
  SELECT id, title, 0 AS lvl
    FROM category
    WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.title,cp.lvl + 1
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY lvl;
+------+----------------------+------+
| id   | title                | lvl  |
+------+----------------------+------+
|    1 | Electronics          |    0 |
|    2 | Laptops & PC         |    1 |
|    5 | Cameras & photo      |    1 |
|    7 | Phones & Accessories |    1 |
|    4 | PC                   |    2 |
|    6 | Camera               |    2 |
|    8 | Smartphones          |    2 |
|   12 | Batteries            |    2 |
|   13 | Headsets             |    2 |
|   14 | Screen Protectors    |    2 |
|    3 | Laptops              |    2 |
|   11 | Other Smartphones    |    3 |
|    9 | Android              |    3 |
|   10 | iOS                  |    3 |
+------+----------------------+------+
14 rows in set (0.00 sec)

删除节点及其子节点

要删除节点及其子节点，只需删除节点本身，所有子节点将由 DELETE CASCADE 外键约束自动删除
例如：要删除Laptops & PC节点及其子节点

DELETE FROM category WHERE id = 2;

删除节点并提升其子节点

首先，parent_id将节点的直接子节点更新为id新父节点的子节点。

然后，删除该节点。

例如，要删除 Smartphones 节点和更新 Android，iOS，Other Smartphones 节点：
两个语句都应该包含在一个事务中：

BEGIN;

UPDATE category 
SET 
    parent_id = 7 -- Phones & Accessories
WHERE
    parent_id = 5; -- Smartphones

DELETE FROM category 
WHERE 
    id = 8;
 
COMMIT;

参考资源

链接：http://mikehillyer.com/articl...

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

GPU云服务器云服务器邻接表存储结构无向图邻接表数最短路径算法邻接表 java邻接表图类

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31520.html

分层数据Hierarchical Data探索(1.递归)

摘要：分层数据探索例如无限级分类多级菜单省份城市引言什么是分层数据类似于树形结构，除了根节点和叶子节点外，所有节点都有一个父节点和一个或多个子节点。接下来我会先通过一般方法和递归方法来实现无限极分类，然后再通过两种数据模型来谈一谈分层数据的处理。分层数据Hierarchical Data探索（例如：无限级分类、多级菜单、省份城市）引言什么是分层数据？类似于树形结构，除了根节点和叶子节...

yzd 2019-07-01 12:47 评论0 收藏0
DeepMind 提出分层强化学习新模型 FuN，超越 LSTM

摘要：实验蒙特祖玛的复仇蒙特祖玛的复仇是上最难的游戏之一。图蒙特祖玛的复仇的学习曲线在第一个房间中学习的子目标的可视化呈现。结论如何创建一个能够学习将其行为分解为有意义的基元，然后重新利用它们以更有效地获取新的行为，这是一个长期存在的研究问题。论文题目：分层强化学习的 FeUdal 网络（FeUdal Networks for Hierarchical Reinforcement Learnin...

dailybird 2019-04-25 18:09 评论0 收藏0
学习JavaScript数据结构与算法 — 图

摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。定义图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和...

yiliang 2019-08-22 11:09 评论0 收藏0
算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0