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