플랫 테이블을 트리로 해석하는 가장 효율적이고 우아한 방법은 무엇입니까?
순서 있는 트리 계층을 저장하는 플랫테이블이 있다고 가정합니다.
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
도표가 요.[id] Name0으로 하다
[0] 루트/ \[1] 노드 1 [3]노드 2/ \ \[2] 노드 1.1 [6]노드 1.2 [5]노드 2.1/[4] 노드 1.1.1
올바른 순서로 입력된 트리로 HTML(또는 텍스트)로 출력하려면 어떤 미니멀리즘 방식을 사용하시겠습니까?
또한 기본 데이터 구조(어레이와 해시맵)만 있고 부모/자녀 참조가 있는 화려한 개체는 없으며 ORM도 없고 프레임워크도 없으며 두 손만 있다고 가정합니다.테이블은 결과 세트로 나타나며 랜덤으로 액세스할 수 있습니다.
의사 코드나 평이한 영어라도 괜찮습니다.이것은 순전히 개념적인 질문입니다.
보너스 질문:이와 같은 트리 구조를 RDBMS에 저장하는 더 좋은 방법이 있습니까?
편집 및 추가
한 코멘트(Mark Bessey's)의 질문에 답하기 위해 루트 노드는 필요 없습니다.루트 노드는 어차피 표시되지 않기 때문입니다.ParentId = 0은 "these are top level"을 나타내는 규칙입니다.Order 열은 동일한 상위 노드를 정렬하는 방법을 정의합니다.
앞서 말한 '결과 세트'는 해시맵 배열로 볼 수 있습니다(이 용어 그대로 유지).내 예시는 이미 거기에 있을 운명이었으니까.어떤 답변들은 더 많은 것을 시도하고 그것을 먼저 구축하지만, 괜찮습니다.
트리는 임의로 깊을 수 있습니다.각 노드에는 N개의 자식을 둘 수 있습니다.하지만 저는 "수백만 개의 엔트리" 트리를 염두에 두고 있지는 않았습니다.
내가 선택한 노드 이름('Node 1.1.1')을 신뢰할 수 있는 것으로 착각하지 마십시오.이 노드들은 똑같이 '프랭크' 또는 '밥'이라고 불릴 수 있으며, 명명 구조는 암시되지 않았으며, 이는 단지 읽을 수 있도록 하기 위한 것이었다.
너희들이 분해할 수 있도록 내가 나만의 해결책을 올렸어.
이제 MySQL 8.0이 재귀 쿼리를 지원하므로 모든 인기 SQL 데이터베이스가 표준 구문에서 재귀 쿼리를 지원한다고 할 수 있습니다.
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
2017년 프레젠테이션 재귀 쿼리 드롭다운에서 MySQL 8.0에서 재귀 쿼리를 테스트했습니다.
다음은 2008년부터의 답변입니다.
트리로 구성된 데이터를 관계형 데이터베이스에 저장하는 방법은 여러 가지가 있습니다.이 예에서는 다음 두 가지 방법을 사용하고 있습니다.
- [ Adjacency List ]([parent]컬럼) 및
- Path Enumeration(이름 열의 점 숫자).
또 다른 솔루션은 중첩 집합이라고 하며 동일한 테이블에 저장할 수도 있습니다.이러한 설계에 대한 자세한 내용은 Joe Celko의 "SQL for Smarties"를 참조하십시오.
저는 보통 트리 구조화 데이터를 저장할 때 Closure Table(일명 "인접 관계")라는 설계를 선호합니다.다른 테이블이 필요하지만 트리를 조회하는 것은 매우 쉽습니다.
저는 SQL과 PHP를 사용한 계층형 데이터에 대한 프레젠테이션 모델 및 SQL 안티패턴 Volume 1: 데이터베이스 프로그래밍의 함정을 회피하기에서 Closure Table에 대해 다룹니다.
CREATE TABLE ClosureTable (
ancestor_id INT NOT NULL REFERENCES FlatTable(id),
descendant_id INT NOT NULL REFERENCES FlatTable(id),
PRIMARY KEY (ancestor_id, descendant_id)
);
노드 간에 직계 조상이 있는 Closure Table에 모든 경로를 저장합니다.자신을 참조할 각 노드의 행을 포함합니다.예를 들어, 질문에 표시된 데이터 세트를 사용하면 다음과 같습니다.
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
(1,1), (1,2), (1,4), (1,6),
(2,2), (2,4),
(3,3), (3,5),
(4,4),
(5,5),
(6,6);
이제 노드 1에서 다음과 같은 트리를 얻을 수 있습니다.
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
MySQL 클라이언트의 출력은 다음과 같습니다.
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
즉, 노드 3과 노드5는 노드1에서 내림차순이 아닌 별도의 계층의 일부이기 때문에 제외됩니다.
e-mailable's e-mailable's 。 해서 ''를 수 요.path_length에서 열로 ClosureTable직접 자녀 또는 부모(또는 기타 거리)에 대해 보다 쉽게 조회할 수 있습니다.
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
(1,1,0), (1,2,1), (1,4,2), (1,6,1),
(2,2,0), (2,4,1),
(3,3,0), (3,5,1),
(4,4,0),
(5,5,0),
(6,6,0);
그런 다음 특정 노드의 직계 하위 항목을 조회하기 위한 용어를 검색에 추가할 수 있습니다.은 그 이다.path_length1로 1면 .
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
AND path_length = 1;
+----+
| id |
+----+
| 2 |
| 6 |
+----+
@ashraf로부터의 리 코멘트: "[이름별로] 트리 전체를 정렬하는 것은 어떻습니까?"
를 다음에 나타냅니다 예에서는 노드 1의 하위 노드들을 FlatTable과 다른 시킵니다.name이치노
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
@Nate로부터의 재코멘트:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name
+------------+-------------+
| name | breadcrumbs |
+------------+-------------+
| Node 1 | 1 |
| Node 1.1 | 1,2 |
| Node 1.1.1 | 1,2,4 |
| Node 1.2 | 1,6 |
+------------+-------------+
오늘 사용자가 편집을 제안했습니다.그래서 모델레이터들이 편집을 승인했지만, 저는 번복하고 있습니다.
는 ORDER BY로 해야 했습니다.ORDER BY b.path_length, f.name이치노그러나 "Node 1.2" 뒤에 "Node 1.1.1"이 오더되기 때문에 이 방법은 작동하지 않습니다.
순서를 적절한 방법으로 계층과 일치시키는 경우는 가능합니다.단, 단순히 경로 길이로 정렬하는 것이 아닙니다.예를 들어 MySQL Closure Table 계층 데이터베이스에 대한 내 답변 - 올바른 순서로 정보를 꺼내는 방법을 참조하십시오.
중첩된 세트(수정된 사전 순서 트리 트래버설이라고도 함)를 사용하는 경우 트리 구조를 통과하는 순서대로 경로를 설명하는 열을 관리해야 하므로 삽입 비용이 더 많이 들지만 트리 구조 전체 또는 트리 내의 하위 트리를 단일 쿼리로 추출할 수 있습니다.
django-mptt에는 다음과 같은 구조를 사용했습니다.
id parent_id tree_id level lft right-- --------- ------- ----- --- ----1 특수한 순서1 0 1 142 1 1 1 2 73 2 1 2 3 44 2 1 2 5 65 1 1 1 8 136 5 1 2 9 107 5 1 2 11 12
입니다.id각 항목을 나타냅니다).
1+-- 2| +-- 3| +-- 4|+-- 5+-- 6+-- 7
더 잘 알 수 있는지 알 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수, 수.lft ★★★★★★★★★★★★★★★★★」rght[ ] :
__________________________________________________________________________| 루트 1 || ________________________________ ________________________________ || Child 1.1 || Child 1.2 ||| | ___________ ___________ | | ___________ ___________ | || | C 1.1.1 || C 1.1.2 || || C 1.2.1 || C 1.2.2 || || ||1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14| |________________________________| |________________________________| ||__________________________________________________________________________|
바와 같이를 트리 순서로 트리 "이러면 됩니다"가 있는 을 모두 .lft ★★★★★★★★★★★★★★★★★」rght 사이의 값lft ★★★★★★★★★★★★★★★★★」rght또한 특정 노드의 조상 트리를 검색하는 것도 간단합니다.
level을 위해 를 해제하고 column은 을 수행합니다.tree_id하면 컬럼을 할 수 .lft ★★★★★★★★★★★★★★★★★」rght삭제의 을 받는 의 수를 각: 입, 、 동 numbering 、 동 numbering 、 ,, ,,, 。lft ★★★★★★★★★★★★★★★★★」rght이러한 작업을 수행할 때 간격을 만들거나 좁히기 위해 열을 적절히 조정해야 합니다.각 작업에 필요한 질문에 대해 머리를 싸매려고 할 때 개발 노트를 작성했습니다.
실제로 이 데이터를 사용하여 트리를 표시하기 위해 각 노드에 대해 원하는 종류의 디스플레이를 생성하기에 충분한 정보를 제공하는 유틸리티 함수를 만들었습니다.
MPTT에 대한 자세한 내용:
꽤 오래된 질문이지만, 많은 견해를 가지고 있는 만큼, 매우 우아한 대안을 제시할 가치가 있다고 생각합니다.
트리 구조를 읽기 위해 CTE(Common Table Expression)를 재귀적으로 사용할 수 있습니다.이는 전체 트리 구조를 한 번에 가져올 수 있으며 노드 수준, 상위 노드 및 상위 노드의 하위 노드 내 순서에 대한 정보를 가질 수 있습니다.
Postgre에서 어떻게 작동하는지 보여드리죠.SQL 9.1.
구조물을 작성하다
CREATE TABLE tree ( id int NOT NULL, name varchar(32) NOT NULL, parent_id int NULL, node_order int NOT NULL, CONSTRAINT tree_pk PRIMARY KEY (id), CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) REFERENCES tree (id) NOT DEFERRABLE ); insert into tree values (0, 'ROOT', NULL, 0), (1, 'Node 1', 0, 10), (2, 'Node 1.1', 1, 10), (3, 'Node 2', 0, 20), (4, 'Node 1.1.1', 2, 10), (5, 'Node 2.1', 3, 10), (6, 'Node 1.2', 1, 20);쿼리를 작성하다
WITH RECURSIVE tree_search (id, name, level, parent_id, node_order) AS ( SELECT id, name, 0, parent_id, 1 FROM tree WHERE parent_id is NULL UNION ALL SELECT t.id, t.name, ts.level + 1, ts.id, t.node_order FROM tree t, tree_search ts WHERE t.parent_id = ts.id ) SELECT * FROM tree_search WHERE level > 0 ORDER BY level, parent_id, node_order;
결과는 다음과 같습니다.
id | name | level | parent_id | node_order
----+------------+-------+-----------+------------
1 | Node 1 | 1 | 0 | 10
3 | Node 2 | 1 | 0 | 20
2 | Node 1.1 | 2 | 1 | 10
6 | Node 1.2 | 2 | 1 | 20
5 | Node 2.1 | 2 | 3 | 10
4 | Node 1.1.1 | 3 | 2 | 10
(6 rows)
트리 노드는 깊이 수준에 따라 정렬됩니다.최종 출력에서는, 그것들을 다음의 행에 나타냅니다.
각 레벨에 대해 부모 내에서 parent_id 및 node_order 순으로 정렬됩니다.부모에 대한 출력 링크 노드에서 이 순서로 표시하는 방법을 설명합니다.
이러한 구조를 가지고 있기 때문에 HTML로 멋진 프레젠테이션을 하는 것은 어렵지 않을 것입니다.
재귀 CTE는 Postgre에서 사용할 수 있습니다.SQL, IBM DB2, MS SQL Server, Oracle 및 SQLite.
재귀 SQL 쿼리에 대한 자세한 내용을 보려면 즐겨찾기 DBMS 문서를 확인하거나 이 주제를 다루는 두 개의 기사를 읽어보십시오.
Oracle 9i부터는 CONNECT BY를 사용할 수 있습니다.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
SQL Server 2005부터는 CTE(재귀 공통 테이블 식)를 사용할 수 있습니다.
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
둘 다 다음 결과를 출력합니다.
이름.'노드 1''노드 1.1''노드 1.1.1''노드 1.2''노드 2''노드 2.1'
빌의 답변은 아주 훌륭하고, 이 답변에는 몇 가지 내용이 추가되어 있어, 나는 SO가 스레드화된 답변을 지원하기를 바란다.
어쨌든 저는 트리 구조와 Order 속성을 지원하고 싶었습니다.에 1개의 시켰습니다.leftSibling 일을 Order는, 원래의 질문(왼쪽에서 오른쪽으로의 순서)으로 행하도록 되어 있습니다.
mysql> 설명 노드;+-------------+--------------+------+-----+---------+----------------+| 필드 | 유형 | 특수한 순서 | 키 | 기본값 | 추가 |+-------------+--------------+------+-----+---------+----------------+| id | int(11) | NO | PRI | NULL | auto_increment || name | varchar (255) | YES | | NULL | || 좌회전 | int(11) | NO | | 0 | | |+-------------+--------------+------+-----+---------+----------------+3행 세트(0.00초) mysql> 인접 관계를 설명합니다.+------------+---------+------+-----+---------+----------------+| 필드 | 유형 | 특수한 순서 | 키 | 기본값 | 추가 |+------------+---------+------+-----+---------+----------------+| relationId | int(11) | NO | PRI | NULL | auto_increment || parent | int(11) | NO | | NULL | || child | int(11) | NO | | NULL | || pathLen | int(11) | NO | NULL | |+------------+---------+------+-----+---------+----------------+4줄 세트(0.00초)
자세한 내용과 SQL 코드는 블로그에서 확인할 수 있습니다.
빌에게 당신의 답변이 시작에 도움이 되었습니다!
SQL 인덱스의 내부 btree 표현을 이용하는 매우 좋은 솔루션이 있습니다.이것은 1998년 경에 행해진 훌륭한 연구에 근거하고 있다.
다음으로 테이블의 예를 나타냅니다(in mysql).
CREATE TABLE `node` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`tw` int(10) unsigned NOT NULL,
`pa` int(10) unsigned DEFAULT NULL,
`sz` int(10) unsigned DEFAULT NULL,
`nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
PRIMARY KEY (`id`),
KEY `node_tw_index` (`tw`),
KEY `node_pa_index` (`pa`),
KEY `node_nc_index` (`nc`),
CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)
트리 표현에 필요한 필드는 다음과 같습니다.
- tw: 왼쪽에서 오른쪽으로 DFS 사전 순서 색인입니다. 여기서 root = 1입니다.
- pa: 부모 노드(root)에 대한 참조(tw 사용)가 null이 있습니다.
- sz: 노드 분기의 크기(자체 포함).
- nc: 통사설탕으로 사용된다.이 값은 tw+default이며 노드의 "next child"의 tw를 나타냅니다.
다음으로 24노드의 구성 예를 나타냅니다.순서는 tw 입니다.
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 2 | A | 2 | 1 | 14 | 16 |
| 3 | AA | 3 | 2 | 1 | 4 |
| 4 | AB | 4 | 2 | 7 | 11 |
| 5 | ABA | 5 | 4 | 1 | 6 |
| 6 | ABB | 6 | 4 | 3 | 9 |
| 7 | ABBA | 7 | 6 | 1 | 8 |
| 8 | ABBB | 8 | 6 | 1 | 9 |
| 9 | ABC | 9 | 4 | 2 | 11 |
| 10 | ABCD | 10 | 9 | 1 | 11 |
| 11 | AC | 11 | 2 | 4 | 15 |
| 12 | ACA | 12 | 11 | 2 | 14 |
| 13 | ACAA | 13 | 12 | 1 | 14 |
| 14 | ACB | 14 | 11 | 1 | 15 |
| 15 | AD | 15 | 2 | 1 | 16 |
| 16 | B | 16 | 1 | 1 | 17 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
| 18 | D | 23 | 1 | 1 | 24 |
| 19 | E | 24 | 1 | 1 | 25 |
+-----+---------+----+------+------+------+
모든 트리 결과는 비재귀적으로 수행될 수 있습니다.예를 들어, tw='22'에 있는 노드의 조상 목록을 얻으려면
조상
select anc.* from node me,node anc
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw
order by anc.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
형제자매와 자녀는 사소합니다.단, pa 필드 순서를 tw로 지정해 주세요.
후예
예를 들어, tw = 17에 뿌리를 둔 노드의 집합(예: 노드)입니다.
select des.* from node me,node des
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw
order by des.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
기타 주의사항
이 방법은 삽입 또는 업데이트보다 읽기 횟수가 훨씬 많은 경우에 매우 유용합니다.
트리의 노드를 삽입, 이동 또는 업데이트하려면 트리를 조정해야 하므로 작업을 시작하기 전에 테이블을 잠가야 합니다.
삽입점 이후의 모든 노드에서 tw 인덱스와 sz(브런치 크기) 값을 각각 업데이트해야 하므로 삽입/삭제 비용이 높습니다.
브런치 이동에는 브런치의 tw 값을 범위 밖으로 이동해야 하므로 브런치를 이동할 때는 외부 키 제약도 비활성화해야 합니다.브랜치를 이동하려면 기본적으로 4개의 쿼리가 필요합니다.
- 브런치를 범위 밖으로 이동합니다.
- 남겨진 틈새를 메워라.(나머지 트리는 이제 정규화되었습니다).
- 어디로 갈지 틈을 벌려라.
- 브런치를 새 위치로 이동합니다.
트리 쿼리 조정
트리의 틈새 열기/닫기는 작성/갱신/삭제 메서드에서 사용되는 중요한 하위 기능이기 때문에 여기에 포함시킵니다.
2개의 파라미터가 필요합니다.다운사이징 또는 업사이징 여부를 나타내는 플래그와 노드의 tw 인덱스가 필요합니다.예를 들어 tw=18(가지 크기가 5)입니다.다운사이징(삭제 tw)을 하고 있다고 가정합니다.즉, 다음 예의 업데이트에서는 '+'가 아닌 '-'를 사용하고 있습니다.
먼저 (약간 변경된) 상위 함수를 사용하여 sz 값을 업데이트합니다.
update node me, node anc set anc.sz = anc.sz - me.sz from
node me, node anc where me.tw=18
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));
그러면 제거할 분기보다 tw가 높은 분기에 대해 tw를 조정해야 합니다.
update node me, node anc set anc.tw = anc.tw - me.sz from
node me, node anc where me.tw=18 and anc.tw >= me.tw;
그런 다음 pa's tw가 제거할 브랜치보다 높은 사람들을 위해 부모를 조정해야 합니다.
update node me, node anc set anc.pa = anc.pa - me.sz from
node me, node anc where me.tw=18 and anc.pa >= me.tw;
선택권이 주어진다면, 난 물건을 사용하고 있을 거야.각 레코드에 대한 개체를 만듭니다. 각 개체는children수집하여 모두 assoc 배열(/hashtable)에 저장합니다. Id가 키입니다.그리고 컬렉션을 한 번 훑어보고 아이들을 관련 아동분야에 추가하세요.심플.
하지만 좋은 OOP 사용을 제한하는 것은 재미없기 때문에 다음과 같이 반복합니다.
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
편집: 다른 엔트리와 비슷하지만 조금 더 깔끔한 것 같습니다.한 가지 덧붙이자면, 이것은 SQL을 매우 많이 사용합니다.심술궂다.선택할 수 있는 경우 OOP 루트로 이동합니다.
은 빨리 효율적이지도 잘 되지 않고, 도 잘 되지 않는다).int ★★★★★★★★★★★★★★★★★」Integer귀찮아!) 하지만 효과가 있어요.
나만의 오브젝트를 만들고 있기 때문에 규칙을 어길 수도 있지만, 실제 업무에서 벗어나기 위해 이 작업을 하고 있습니다.
또한 노드 구축을 시작하기 전에 resultSet/table이 어떤 구조에서 완전히 읽혀진다고 가정합니다.수십만 개의 행이 있는 경우에는 최적의 솔루션이 아닙니다.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
루트 요소가 0임을 알고 있다고 가정하면 텍스트로 출력하는 의사 코드를 다음에 나타냅니다.
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
해시맵을 사용하여 다른 데이터 구조를 에뮬레이트할 수 있으므로 큰 제약은 없습니다.위에서 아래로 스캔하면 데이터베이스의 각 행에 대해 각 열에 대한 엔트리가 포함된 해시 맵을 만듭니다.이러한 각 해시맵을 id로 키 입력된 "마스터" 해시맵에 추가합니다.노드에 아직 표시되지 않은 "상위"가 있는 경우 마스터 해시맵에서 해당 노드에 대한 자리 표시자 항목을 생성하고 실제 노드가 나타나면 해당 항목을 입력합니다.
인쇄하려면 데이터를 간단하게 깊이 우선 통과시키고 도중에 들여쓰기 수준을 추적합니다.각 행에 대해 "하위" 항목을 유지하고 데이터를 검색할 때 해당 항목을 채우면 이 작업을 더 쉽게 수행할 수 있습니다.
데이터베이스에 트리를 저장하는 "더 나은" 방법이 있는지 여부는 데이터를 어떻게 사용할지에 따라 달라집니다.계층 내 각 레벨에 대해 다른 테이블을 사용하는 알려진 최대 깊이를 가진 시스템을 본 적이 있습니다.결국 트리의 수준이 완전히 동일하지 않은 경우(최상위 범주는 잎과 다릅니다).
네스트된 해시 맵이나 배열을 만들 수 있는 경우 처음부터 테이블을 아래로 이동하여 각 항목을 네스트된 배열에 추가할 수 있습니다.네스트된 배열의 어느 레벨에 삽입할지를 알기 위해 루트 노드까지 각 행을 추적해야 합니다.같은 부모를 반복해서 찾을 필요가 없도록 메모 기능을 사용할 수 있습니다.
편집: 먼저 전체 테이블을 배열로 읽어 DB를 반복 쿼리하지 않습니다.테이블이 너무 크면 당연히 실용적이진 않겠죠.
구조물이 만들어지면 먼저 깊이 탐색을 하고 HTML을 출력해야 합니다.
이 정보를 하나의 표를 사용하여 저장하는 가장 기본적인 방법은 없습니다(단, 틀릴 수도 있습니다). 더 나은 해결책을 찾고 싶습니다.그러나 동적으로 생성된 DB 테이블을 사용하는 스킴을 작성하면 단순성과 SQL Hell의 위험을 감수하고 완전히 새로운 세상을 열게 됩니다.
빌의 SQL 솔루션을 확장하려면 기본적으로 플랫 어레이를 사용하여 동일한 작업을 수행할 수 있습니다.또한 문자열의 밝기가 모두 같고 최대 자식 수를 알고 있는 경우(예를 들어 이진 트리에서) 단일 문자열(문자 배열)을 사용하여 수행할 수 있습니다.자의적으로 아이를 낳으면 일이 좀 복잡해져요어떻게 하면 좋을지 예전 노트를 확인해 봐야겠어요.
그런 다음, 특히 트리가 희박하거나 분산되지 않은 경우 다음과 같이 트리를 먼저 배열에 저장함으로써 모든 문자열에 랜덤하게 액세스할 수 있습니다(바이너리 트리의 경우).
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
당신은 당신의 끈 길이를 알고, 당신은 그것을 알고 있다.
나는 지금 일하고 있기 때문에 그것에 많은 시간을 할애할 수 없지만 흥미를 가지고 이것을 하기 위한 약간의 코드를 가져올 수 있다.
우리는 DNA 코돈으로 만들어진 이진 트리를 검색하기 위해 이것을 사용하곤 했습니다. 그리고 나서 우리는 그것을 텍스트 패턴을 검색하기 위해 평평하게 만들었습니다. 그리고 발견되었을 때, 인덱스 수학(위로부터의 역)을 통해 노드를 다시 얻습니다.매우 빠르고 효율적이며 튼튼한 트리에 빈 노드가 거의 없지만 기가바이트의 데이터를 순식간에 처리할 수 있습니다.
인접 표현에 대한 온 더 플라이 경로 열거를 사용한 사전 순서 횡단
중첩된 집합 위치:
- Konchog https://stackoverflow.com/a/42781302/895245
- 조니 뷰캐넌 https://stackoverflow.com/a/194031/895245
업데이트 속도가 느리지만 효율적인 방법은 이 방법밖에 없습니다.그것은 대부분의 사람들이 사전 주문으로 원하는 것입니다.
https://stackoverflow.com/a/192462/895245의 클로징 테이블은 흥미롭지만 어떻게 사전 주문을 해야 할지 모르겠습니다.MySQL Closure Table 계층 데이터베이스 - 올바른 순서로 정보를 꺼내는 방법
주로 재미를 위해, 여기에서는 부모 ID/자녀 인덱스 표현만을 기준으로 1.3.2.5. 접두사를 즉시 재귀적으로 계산하고 마지막에 정렬하는 방법이 있습니다.
업사이드:
- 업데이트는 각 형제의 인덱스만 업데이트하면 됩니다.
단점:
- n^2 메모리 사용률 최악의 경우 슈퍼 딥 트리로 간주됩니다.이것은 꽤 심각할 수 있기 때문에, 이 방법은 대부분 재미로 하는 것이라고 생각합니다.하지만 누군가 사용하고 싶어 하는 초고도의 업데이트 사례가 있는 것은 아닐까요?누가 알겠어
- 재귀 쿼리는 네스트된 세트보다 읽기 효율이 떨어집니다.
테이블 작성 및 채우기:
CREATE TABLE "ParentIndexTree" (
"id" INTEGER PRIMARY KEY,
"parentId" INTEGER,
"childIndex" INTEGER NOT NULL,
"value" INTEGER NOT NULL,
"name" TEXT NOT NULL,
FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
;
INSERT INTO "ParentIndexTree" VALUES
(0, NULL, 0, 1, 'one' ),
(1, 0, 0, 2, 'two' ),
(2, 0, 1, 3, 'three'),
(3, 1, 0, 4, 'four' ),
(4, 1, 1, 5, 'five' )
;
표시되는 트리:
1
/ \
2 3
/ \
4 5
PostgreSQL](https://www.postgresql.org/docs/14/arrays.html)과 같은 어레이를 갖춘 DBMS의 경우:
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
array[0]
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
array_append("parent"."prefix", "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
그러면 형식의 프리픽스에 다음과 같이 작성됩니다.
1 -> 0
2 -> 0, 0
3 -> 0, 1
4 -> 0, 0, 0
5 -> 0, 0, 1
그 후 Postgre다음으로 SQL은 어레이별로 다음과 같이 알파벳 순으로 정렬됩니다.
1 -> 0
2 -> 0, 0
4 -> 0, 0, 0
5 -> 0, 0, 1
3 -> 0, 1
우리가 원하는 사전 주문 결과입니다.
SQLite와 같은 배열이 없는 DBMS의 경우 고정 너비 정수 문자열로 프레픽스를 인코딩하여 해킹할 수 있습니다.바이너리가 이상적이긴 한데, 16진법이 어떻게 작동하는지 알 수가 없었어요.이는 물론 선택한 바이트 수에 맞는 최대 깊이를 선택해야 함을 의미합니다. 예를 들어 노드당 최대 16^6의 자녀를 허용하는 6을 선택합니다.
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
'000000'
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
"parent"."prefix" || printf('%06x', "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
일부 중첩된 세트 노트
여기 다른 중첩된 답변들을 보고 조금 혼란스러웠던 몇 가지 요점이 있습니다.
Jonny Buchanan은 자신의 중첩된 세트 설정을 다음과 같이 표시합니다.
__________________________________________________________________________
| Root 1 |
| ________________________________ ________________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
| |________________________________| |________________________________| |
|__________________________________________________________________________|
왜 단순한 외관을 사용하지 않는지 궁금했어요.
__________________________________________________________________________
| Root 1 |
| ________________________________ _______________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________| 4___________| | 5 6___________| 7___________| | |
| |________________________________| |_______________________________| |
|_________________________________________________________________________|
각 엔드포인트에는 추가 번호가 없습니다.
그러나 실제로 구현하려고 했을 때 Konchog에서 사용하는 부모 정보가 없는 한 업데이트 쿼리를 구현하기가 어렵거나 불가능하다는 것을 알게 되었습니다.문제는 트리가 옮겨지는 동안 형제자매와 부모를 한 번에 구별하기가 어려웠기 때문에 틈새를 좁히면서 오른쪽을 줄일지 결정할 필요가 있었습니다.
왼쪽/크기 vs 왼쪽/오른쪽: 데이터베이스에 저장할 수 있지만, 왼쪽/오른쪽이 더 효율적이라고 생각합니다. DB를 멀티컬럼 인덱스(왼쪽, 오른쪽)로 인덱싱하면 상위 쿼리의 속도를 높일 수 있습니다.
left < curLeft AND right > curLeft
Ubuntu 22.04로 테스트 완료(Postgre).SQL 14.5, SQLite 3.34.0.
예시와 같이 요소가 트리 순서로 나열되어 있는 경우 다음과 같은 Python 예를 사용할 수 있습니다.
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
이렇게 하면 트리의 현재 위치를 나타내는 스택이 유지됩니다.테이블의 각 요소에 대해 현재 항목의 부모를 찾을 때까지 스택 요소(일치하는 div 닫기)를 팝합니다.그런 다음 해당 노드의 시작을 출력하여 스택에 푸시합니다.
네스트된 요소가 아닌 들여쓰기를 사용하여 트리를 출력하려면 인쇄문을 건너뛰고 div를 인쇄하고 각 항목 앞에 스택 크기의 몇 배와 동일한 공간을 인쇄하면 됩니다.예를 들어 Python의 경우:
print " " * len(stack)
또한 이 방법을 사용하여 중첩된 목록 또는 사전 세트를 쉽게 구성할 수 있습니다.
편집: 설명에서 이름이 노드 경로로 의도된 것이 아님을 알 수 있습니다.이는 다른 접근방식을 제안합니다.
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
그러면 튜플(!) 배열 트리가 구성됩니다.idx[0]는 트리의 루트를 나타냅니다.배열의 각 요소는 노드 자체와 모든 자식 목록으로 구성된 2-태플입니다.일단 구성되면 ID로 노드에 액세스하지 않는 한 idx[0]를 유지하여 idx를 폐기할 수 있습니다.
계층 구조에 neo4j와 같은 nosql 도구를 사용하는 것을 고려해 보십시오.예를 들어 Linkedin과 같은 네트워크 애플리케이션은 카우치 베이스를 사용합니다(다른 nosql 솔루션).
그러나 nosql은 데이터마트 수준의 쿼리에만 사용하고 트랜잭션 저장/유지에는 사용하지 마십시오.
언급URL : https://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree
'source' 카테고리의 다른 글
| WPF 애플리케이션의 엔트리 포인트는 무엇입니까? (0) | 2023.04.14 |
|---|---|
| Git을 사용하여 최신 커밋을 새 브랜치로 이동 (0) | 2023.04.14 |
| 패키지가 설치되어 있는지 확인하고 설치되어 있지 않으면 어떻게 해야 합니까? (0) | 2023.04.14 |
| PowerShell에서 문자열을 정수로 변환하는 방법 (0) | 2023.04.14 |
| Swift Array에서 최소/최대값 검색 (0) | 2023.04.14 |