分層數據Hierarchical Data探索(2.鄰接表模型)

Scott 發布于2019-07-01 12:48 / 923人閱讀

摘要：分層數據探索例如無限級分類多級菜單省份城市引言第一篇分層數據探索遞歸已經介紹了分層數據以及使用遞歸算法實現了無限極分類，但是遞歸即浪費時間，又浪費空間內存尤其是在數據量大的情況下效率顯著下降。

分層數據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鄰接表圖類

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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