分层数据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...
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

查看所有标签

猜你喜欢:

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

码农书籍

Python Algorithms

Magnus Lie Hetland / Apress / 2010-11-24 / USD 49.99

Python Algorithms explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it......一起来看看《Python Algorithms》这本书的介绍吧!

码农工具