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

分层数据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;

参考资源

本作品采用《CC 协议》,转载必须注明作者和本文链接
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 文章来源blog.arunfung.com
arunfung
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!