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

栏目: 数据库 · 发布时间: 5年前

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

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

引言

第一篇分层数据Hierarchical Data探索(1.递归)已经介绍了分层数据以及使用递归算法实现了无限极分类，但是递归即浪费时间，又浪费空间（内存）,尤其是在数据量大的情况下效率显著下降。

那么，在 MySQL 中如何处理分层数据呢？下面我们来说一说数据模型 邻接表模型

邻接表模型(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;

删除节点并提升其子节点
1. 首先，parent_id将节点的直接子节点更新为id新父节点的子节点。
2. 然后，删除该节点。

例如，要删除 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...
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

产品心经：产品经理应该知道的60件事（第2版）

闫荣 / 机械工业出版社 / 2016-4 / 69.00

本书第一版出版后广获好评，应广大读者要求，作者把自己在实践中新近总结的10个关于产品的最佳实践融入到了这本新书中。这"10件事"侧重于深挖产品需求和产品疯传背后的秘密，配合之前的"50件事"，不仅能帮产品经理打造出让用户尖叫并疯传的产品，还能帮助产品经理迅速全方位提升自己的能力。本书作者有超过10年的产品工作经验，在互联网产品领域公认的大咖，这本书从产品经理核心素养、产品认知、战略与规划、......一起来看看《产品心经：产品经理应该知道的60件事（第2版）》这本书的介绍吧!

码农工具