query - mysql select recursive parent




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

鄰接模型+嵌套集模型

我為此付出了努力,因為我可以輕鬆地將新項目插入樹中(您只需要一個分支的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列。
  • 如果您需要任何父母的所有後代,則查詢其父母之間的lftrgt之間的lft項目。
  • 如果需要任何節點的所有父節點直到樹的根節點,則查詢比節點的lftrgtlft並且大於節點的rgt並按parent節點進行排序的項目。

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

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

良好的概述

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

選項

我知道的和一般特徵:

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

數據庫特定註釋

MySQL的

神諭

PostgreSQL的

SQL Server

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

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

特別是使用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和關係數據庫解決問題。 但是,如果您願意使用正確的工具進行工作,則有更好的方法。







hierarchical-data