query - mysql select recursive parent

在關係數據庫中存儲分層數據有哪些選項? (5)

良好的概述

一般而言，您正在快速讀取時間（例如，嵌套集）或快速寫入時間（鄰接列表）之間做出決定。通常情況下，您最終會得到最適合您需求的選項組合。以下內容提供了一些深入的解讀：

多一個嵌套間隔與鄰接列表比較：我發現的鄰接列表，物化路徑，嵌套集合和嵌套間隔的最佳比較 。
分層數據的模型：幻燈片中有很好的權衡解釋和示例用法
在MySQL中表示層次結構：特別是非常好的嵌套集概述
關係數據庫系統中的分層數據：我見過的最全面和組織良好的鏈接集，但解釋方式並不多

選項

我知道的和一般特徵：

鄰接表：
- 列：ID，ParentID
- 易於實施。
- 便宜的節點移動，插入和刪除。
- 昂貴的找到關卡（可以存儲為計算列），祖先和後代（橋表結合等級列可以解決），路徑（Lineage Column可以解決）。
- 在支持它們遍歷的數據庫中使用公用表表達式。
嵌套集合（又名修改先序樹遍歷）
- Joe Celko在眾多文章中以及他的書中的Trees and Hierarchies in SQL for Smarties中得到了推廣
- 列：左，右
- 便宜的水平，血統，後代
- 易失性編碼 - 移動，插入，刪除更昂貴。
- 需要特定的排序順序（例如創建）。因此，以不同順序排序所有後代需要額外的工作。
嵌套間隔
- 像嵌套集合，但與真正/浮點/小數，使編碼不揮發（便宜的移動/插入/刪除）
- 必須處理真實/浮點/小數表示問題
- 一個更複雜的矩陣編碼變體增加了祖先編碼的好處，就像物化路徑的“自由”
橋接表（又名Closure Table ：關於如何使用觸發器維護這種方法的一些好主意）
- 專欄：祖先，後代
- 與它描述的表格分開。
- 可以在一個以上的層次中包含一些節點。
- 廉價的祖先和後代（儘管不是以什麼順序）
- 對於層次結構的完整知識需要與另一個選項相結合。
平的表
- 鄰接列表的修改，為每條記錄添加級別和排名（例如排序）列。
- 昂貴的移動和刪除
- 廉價的祖先和後代
- 好用：線程討論 - 論壇/博客評論
沿襲列（又名物化路徑，路徑枚舉）
- 專欄：譜系（例如/父母/孩子/孫子/等等）
- 限制層次結構的深度。
- 後代便宜（例如LEFT(lineage, #) = '/enumerated/path' ）
- 祖先棘手（數據庫特定查詢）
多譜系列
- 列：每個血統級別的一個，指的是所有的父母直到根，從項目的水平下降的級別都設置為NULL
- 限制層次結構的深度
- 廉價的祖先，後代，水平
- 廉價的插入，刪除，移動的葉子
- 昂貴的插入，刪除，移動內部節點

數據庫特定註釋

MySQL的

使用鄰接列表的會話變量

神諭

使用CONNECT BY遍歷鄰接列表

PostgreSQL的

物化路徑的ltree數據類型

SQL Server

總結
2008提供HierarchyId數據類型似乎有助於使用Lineage Column方法並擴展可表示的深度。

鄰接模型+嵌套集模型

我為此付出了努力，因為我可以輕鬆地將新項目插入樹中（您只需要一個分支的ID來插入一個新項目），並且查詢速度相當快。

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

每次你需要任何父母的所有孩子時，你只需查詢parent列。
如果您需要任何父母的所有後代，則查詢其父母之間的lft和rgt之間的lft項目。
如果需要任何節點的所有父節點直到樹的根節點，則查詢比節點的lft和rgt低lft並且大於節點的rgt並按parent節點進行排序的項目。

我需要比插入更快地訪問和查詢樹，這就是我選擇它的原因

唯一的問題是在插入新項目時修復right列。那麼我為它創建了一個存儲過程，並在每次插入一個在我的例子中很少見的新項目時調用它，但它非常快。我從Joe Celko的書中獲得了這個想法，以及存儲過程以及我如何使用它的原因在DBA SE中解釋https://dba.stackexchange.com/q/89051/41481

如果您的數據庫支持數組，則還可以將父系列或物化路徑實現為父數據標識的數組。

特別是使用Postgres，您可以使用集合運算符來查詢層次結構，並使用GIN索引獲得出色的性能。這使得在單個查詢中找到父母，孩子和深度非常簡單。更新也相當易於管理。

如果你好奇，我已經寫了一些使用物理路徑的數組。

我正在使用PostgreSQL和我的層次結構的閉合表。我有一個通用的存儲過程為整個數據庫：

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

然後對於我有層次結構的每個表，我創建一個觸發器

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

為了填充現有層次結構中的閉包表，我使用這個存儲過程：

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

閉包表用3列定義 - ANCESTOR_ID，DESCENDANT_ID，DEPTH。有可能（甚至建議）為ANCESTOR和DESCENDANT存儲具有相同值的記錄，深度值為零。這將簡化對層次結構進行檢索的查詢。他們確實很簡單：

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

此設計尚未提及：

多譜系列

雖然它有局限性，但如果你能承受它，它非常簡單而且非常高效。特徵：

列：每個血統級別的一個，指的是所有的父母直到根，當前項目的水平以下的級別被設置為NULL
限制層次結構的深度
廉價的祖先，後代，水平
廉價的插入，刪除，移動的葉子
昂貴的插入，刪除，移動內部節點

這裡有一個例子 - 鳥類的分類樹，所以層次結構是類別/順序/家族/屬/物種 - 物種是最低級別，1行= 1分類群（對應於葉節點的物種）：

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

和數據的例子：

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

這非常棒，因為只要內部類別不會在樹中改變它們的級別，您就可以非常簡單的方式完成所有需要的操作。

這真是一個方形釘，圓孔問題。

如果關係數據庫和SQL是您已經或願意使用的唯一錘子，那麼到目前為止發布的答案已經足夠。但是，為什麼不使用旨在處理分層數據的工具？圖形數據庫非常適合複雜的分層數據。

與圖形數據庫解決方案可以輕鬆解決相同問題相比，關係模型的低效率以及將圖形/分層模型映射到關係模型上的任何代碼/查詢解決方案的複雜性都不值得。

考慮將材料清單作為常見的分層數據結構。

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

兩個子程序集之間的最短路徑 ：簡單圖遍曆算法。可接受的路徑可以根據標准進行限定。

相似性 ：兩個程序集之間的相似程度是多少？對兩個子樹執行遍歷，計算兩個子樹的交集和並集。百分比類似的是十字路口除以工會。

傳遞閉包 ：步行子樹並總結感興趣的領域，例如“多少鋁在一個子組件中？”

是的，您可以使用SQL和關係數據庫解決問題。但是，如果您願意使用正確的工具進行工作，則有更好的方法。