질문자 :Community Wiki
좋은 개요
일반적으로 말하면 빠른 읽기 시간(예: 중첩 집합) 또는 빠른 쓰기 시간(인접 목록) 사이에서 결정을 내립니다. 일반적으로 요구 사항에 가장 적합한 아래 옵션의 조합으로 끝납니다. 다음은 몇 가지 심층적인 내용을 제공합니다.
옵션
내가 알고 있는 것들과 일반적인 특징들:
- 인접 목록 :
- 열: ID, ParentID
- 구현하기 쉽습니다.
- 저렴한 노드는 이동, 삽입 및 삭제합니다.
- 레벨, 조상 및 자손, 경로를 찾는 데 비용이 많이 듭니다.
- N+1을 지원하는 데이터베이스에서 공통 테이블 표현식 을 통해 N+1 방지
- 중첩 집합 (Modified Preorder Tree Traversal 이라고도 함)
- 열: 왼쪽, 오른쪽
- 값싼 조상, 후손
- 휘발성 인코딩으로 인해 매우 비싼
O(n/2) 이동, 삽입, 삭제
- 브리지 테이블(클로저 테이블 /w 트리거 라고도 함)
- 조상, 후손, 깊이(선택 사항)와 함께 별도의 조인 테이블을 사용합니다.
- 값싼 조상과 후손
- 삽입, 업데이트, 삭제에 대한
O(log n) (하위 트리 크기)를 씁니다. - 정규화된 인코딩: 조인에서 RDBMS 통계 및 쿼리 플래너에 적합
- 노드당 여러 행 필요
- 계보 열 (일명 구체화된 경로 , 경로 열거)
- 열: 계보(예: /parent/child/grandchild/etc...)
- 접두사 쿼리를 통한 저렴한 자손(예:
LEFT(lineage, #) = '/enumerated/path' ) - 삽입, 업데이트, 삭제에 대한
O(log n) (하위 트리 크기)를 씁니다. - 비관계형: 배열 데이터 유형 또는 직렬화된 문자열 형식에 의존
- 중첩 간격
- 중첩된 집합과 유사하지만 인코딩이 휘발성이 아니도록 실수/부동수/십진수를 사용합니다(저렴한 이동/삽입/삭제).
- 실수/부동수/십진수 표현/정밀도 문제가 있음
- 매트릭스 인코딩 변형 은 "무료"를 위해 상위 인코딩(구체화된 경로)을 추가하지만 선형 대수의 까다로움이 추가되었습니다.
- 플랫 테이블
- 각 레코드에 수준 및 순위(예: 순서 지정) 열을 추가하는 수정된 인접 목록입니다.
- 반복/페이지 매김에 저렴
- 값비싼 이동 및 삭제
- 좋은 사용: 스레드 토론 - 포럼/블로그 댓글
- 여러 계보 열
- 열: 각 계보 수준에 대해 하나씩, 루트까지의 모든 부모를 참조하고 항목 수준에서 하위 수준은 NULL로 설정됩니다.
- 저렴한 조상, 후손, 레벨
- 잎의 저렴한 삽입, 삭제, 이동
- 고가의 내부 노드 삽입, 삭제, 이동
- 계층 구조의 깊이에 대한 엄격한 제한
데이터베이스별 참고 사항
MySQL
신탁
PostgreSQL
SQL 서버
- 일반 요약
- 2008은 HierarchyId 데이터 유형을 제공하여 Lineage Column 접근 방식을 돕고 표현할 수 있는 깊이를 확장합니다.
내가 가장 좋아하는 대답은 이 스레드의 첫 번째 문장이 제안한 것과 같습니다. 인접 목록을 사용하여 계층을 유지 관리하고 중첩 집합을 사용하여 계층을 쿼리합니다.
지금까지의 문제는 대부분의 사람들이 "푸시 스택"으로 알려진 극단적인 RBAR 방법을 사용하여 변환을 수행하고 비용이 많이 드는 방법으로 간주되었기 때문에 Adjacecy List에서 Nested Sets로의 커버링 방법이 엄청나게 느리다는 것입니다. Adjacency List에 의한 유지 관리의 단순성과 Nested Sets의 놀라운 성능의 열반에 도달합니다. 결과적으로 대부분의 사람들은 특히 예를 들어 형편없는 노드가 100,000개 이상인 경우 둘 중 하나를 선택해야 합니다. 푸시 스택 방법을 사용하면 MLM 사용자가 작은 백만 노드 계층으로 간주하는 변환을 수행하는 데 하루 종일 걸릴 수 있습니다.
불가능해 보이는 속도로 인접 목록을 중첩 집합으로 변환하는 방법을 생각해 냄으로써 Celko가 약간의 경쟁을 할 수 있다고 생각했습니다. 다음은 내 i5 노트북에서 푸시 스택 방식의 성능입니다.
Duration for 1,000 Nodes = 00:00:00:870 Duration for 10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10) Duration for 100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) Duration for 1,000,000 Nodes = 'Didn't even try this'
다음은 새 메서드의 지속 시간입니다(괄호 안에 푸시 스택 메서드 포함).
Duration for 1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870) Duration for 10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783) Duration for 100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730) Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)
네, 맞습니다. 100만 노드는 1분 이내에 변환되고 100,000개 노드는 4초 이내에 변환됩니다.
다음 URL에서 새 방법에 대해 읽고 코드 사본을 얻을 수 있습니다. http://www.sqlservercentral.com/articles/Hierarchy/94040/
또한 유사한 방법을 사용하여 "미리 집계된" 계층 구조를 개발했습니다. MLM's 및 BOM을 만드는 사람들은 이 기사에 특히 관심이 있을 것입니다. http://www.sqlservercentral.com/articles/T-SQL/94570/
두 기사 중 하나를 보기 위해 들러서 "토론 참여" 링크로 이동하여 귀하의 생각을 알려주십시오.
이것은 귀하의 질문에 대한 부분적인 답변이지만 여전히 유용하기를 바랍니다.
Microsoft SQL Server 2008은 계층 데이터 관리에 매우 유용한 두 가지 기능을 구현합니다.
시작하려면 MSDN에서 Kent Tegels의 "Model Your Data Hierarchies With SQL Server 2008"을 살펴보십시오. 내 자신의 질문도 참조하십시오. SQL Server 2008의 재귀적 동일 테이블 쿼리
이 디자인은 아직 언급되지 않았습니다.
한계가 있지만 견딜 수만 있다면 매우 간단하고 매우 효율적입니다. 특징:
- 열: 각 계보 수준에 대해 하나씩, 루트까지의 모든 부모를 참조하고 현재 항목 수준 아래의 수준은 0(또는 NULL)으로 설정됩니다.
- 계층 구조의 깊이에는 고정된 제한이 있습니다.
- 저렴한 조상, 후손, 레벨
- 잎의 저렴한 삽입, 삭제, 이동
- 고가의 내부 노드 삽입, 삭제, 이동
다음은 새의 분류학적 트리이므로 계층 구조는 Class/Order/Family/Genus/Species입니다. 종은 가장 낮은 수준, 1 행 = 1 taxon(잎 노드의 경우 종에 해당)의 예입니다.
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 |
내부 범주가 트리에서 수준을 변경하지 않는 한 매우 쉬운 방법으로 필요한 모든 작업을 수행할 수 있기 때문에 매우 좋습니다.
인접 모델 + 중첩 집합 모델
트리에 새 항목을 쉽게 삽입할 수 있고(새 항목을 삽입하려면 분기의 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 사이 lft 와 rgt 부모를. - 당신이 트리의 루트 노드까지의 모든 학부모 필요한 경우, 당신은 필요 항목에 대한 쿼리
lft 노드의보다 낮은 lft 와 rgt 노드의보다 큰 rgt 정렬하여 및 parent .
삽입보다 빠르게 트리에 액세스하고 쿼리해야 했기 때문에 이것을 선택했습니다.
유일한 문제는 새 항목을 삽입할 때 left 및 right 열을 수정하는 것입니다. 글쎄, 나는 그것에 대한 저장 프로 시저를 만들고 내 경우에는 드물지만 정말 빠른 새 항목을 삽입 할 때마다 그것을 호출했습니다. Joe Celko의 책에서 아이디어를 얻었고 저장 프로시저와 이를 생각해낸 방법은 여기 DBA SE https://dba.stackexchange.com/q/89051/41481에 설명되어 있습니다.
데이터베이스가 배열을 지원하는 경우 계보 열 또는 구체화된 경로를 부모 ID의 배열로 구현할 수도 있습니다.
특히 Postgres에서는 집합 연산자를 사용하여 계층 구조를 쿼리하고 GIN 인덱스로 뛰어난 성능을 얻을 수 있습니다. 따라서 단일 쿼리에서 부모, 자식 및 깊이를 찾는 것이 매우 간단합니다. 업데이트도 꽤 관리하기 쉽습니다.
궁금한 경우 구체화된 경로에 배열을 사용하는 방법에 대한 전체 글이 있습니다.
이것은 실제로 사각형 못, 둥근 구멍 질문입니다.
관계형 데이터베이스와 SQL이 당신이 가지고 있거나 사용할 의향이 있는 유일한 망치라면 지금까지 게시된 답변으로 충분합니다. 그러나 계층적 데이터를 처리하도록 설계된 도구를 사용하지 않는 이유는 무엇입니까? 그래프 데이터베이스 는 복잡한 계층적 데이터에 이상적입니다.
그래프/계층적 모델을 관계형 모델에 매핑하기 위한 코드/쿼리 솔루션의 복잡성과 함께 관계형 모델의 비효율성은 그래프 데이터베이스 솔루션이 동일한 문제를 해결할 수 있는 용이성과 비교할 때 노력할 가치가 없습니다.
BOM을 공통 계층적 데이터 구조로 간주합니다.
class Component extends Vertex { long assetId; long partNumber; long material; long amount; }; class PartOf extends Edge { }; class AdjacentTo extends Edge { };
두 하위 어셈블리 사이의 최단 경로 : 단순 그래프 탐색 알고리즘. 허용되는 경로는 기준에 따라 한정될 수 있습니다.
유사성 : 두 어셈블리 간의 유사성 정도는 얼마입니까? 두 하위 트리의 교집합과 합집합을 계산하는 두 하위 트리에서 순회를 수행합니다. 유사 비율은 교집합을 합집합으로 나눈 값입니다.
전이적 폐쇄 : 하위 트리를 살펴보고 관심 분야를 요약합니다(예: "하위 어셈블리에 알루미늄이 얼마나 들어 있습니까?").
예, SQL과 관계형 데이터베이스로 문제를 해결할 수 있습니다. 그러나 작업에 적합한 도구를 사용하려는 경우 훨씬 더 나은 방법이 있습니다.
내 계층 구조에 대한 클로저 테이블과 함께 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; $$;
클로저 테이블은 ANCESTOR_ID, DESCENDANT_ID, DEPTH의 3개 열로 정의됩니다. ANCESTOR와 DESCENDANT의 값이 같고 DEPTH의 값이 0인 레코드를 저장하는 것이 가능합니다. 이렇게 하면 계층 검색을 위한 쿼리가 단순화됩니다. 그리고 그것들은 실제로 매우 간단합니다.
-- 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;
출처 : http:www.stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database