플랫 테이블을 트리로 구문 분석하는 가장 효율적이고 우아한 방법은 무엇입니까?
순서가 지정된 트리 계층 구조를 저장하는 플랫 테이블이 있다고 가정하십시오.
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] Name. 루트 노드 0은 허구입니다.
[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은 "이것은 최상위 수준"을 나타내는 규칙입니다. Order 열은 동일한 부모를 가진 노드가 정렬되는 방법을 정의합니다.
내가 말한 "결과 세트"는 해시 맵의 배열로 묘사 될 수있다 (해당 용어를 유지하기 위해). 내 예는 이미 거기에 있었다. 어떤 대답은 여분의 마일을 가지고 그것을 먼저 구성하지만 괜찮습니다.
나무는 임의로 깊을 수 있습니다. 각 노드에는 N 개의 자식이있을 수 있습니다. 그래도 정확히 "수백만 개의 항목"트리가 없었습니다.
내가 선택해야 할 노드 이름 지정 ( '노드 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의 Recursive Query Throwdown 프레젠테이션에서 MySQL 8.0의 재귀 쿼리를 테스트했습니다 .
아래는 2008 년의 원래 답변입니다.
트리 구조 데이터를 관계형 데이터베이스에 저장하는 방법에는 여러 가지가 있습니다. 예제에서 보여주는 것은 두 가지 방법을 사용합니다.
- 인접 목록 ( "부모"열) 및
- 경로 열거 (이름 열의 점으로 구분 된 숫자)
다른 솔루션을 Nested Sets 라고 하며 같은 테이블에 저장할 수도 있습니다. 이러한 디자인에 대한 자세한 내용은 Joe Celko의 " SQL for Smarties의 트리 및 계층 구조 "를 읽으십시오 .
저는 일반적으로 트리 구조 데이터를 저장하기 위해 클로저 테이블 (일명 "인접 관계") 이라는 디자인을 선호합니다 . 다른 테이블이 필요하지만 트리 쿼리는 매우 쉽습니다.
필자 는 SQL 및 PHP를 사용한 계층 적 데이터 모델 프레젠테이션 및 저서 SQL 안티 패턴 : 데이터베이스 프로그래밍의 함정을 피하는 클로저 테이블을 다루고 있습니다.
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)
);
한 노드에서 다른 노드로 직접 조상이있는 클로저 테이블에 모든 경로를 저장하십시오. 각 노드가 자신을 참조하도록 행을 포함 시키십시오. 예를 들어 질문에 표시 한 데이터 세트를 사용하는 경우 :
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에서 내려 가지 않고 별도의 계층 구조의 일부이므로 제외됩니다.
다시 : 직계 자녀 (또는 직계 부모)에 대한 전자 위성의 의견. " 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의 자손입니다 .
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 |
+------------+-------------+
사용자가 오늘 수정을 제안했습니다. SO 중재자가 편집을 승인했지만 되돌리고 있습니다.
편집 ORDER BY b.path_length, f.name은 순서가 계층과 일치하는지 확인하기 위해 위의 마지막 쿼리에서 ORDER BY가되어야한다고 제안했습니다 . 그러나 "노드 1.2"다음에 "노드 1.1.1"을 주문하므로 작동하지 않습니다.
순서가 합리적인 방식으로 계층 구조와 일치하도록하려면 경로 길이를 기준으로 정렬하는 것이 아니라 가능합니다. 예를 들어 MySQL Closure Table 계층 데이터베이스에 대한 나의 답변 -올바른 순서로 정보를 가져 오는 방법을 참조하십시오 .
중첩 된 집합 (때로는 수정 된 사전 순서 트리 탐색이라고 함)을 사용하는 경우 단일 쿼리를 사용하여 전체 트리 구조 또는 트리 구조의 하위 트리를 단일 쿼리로 추출 할 수 있습니다. 트리 구조를 통한 순서 경로를 설명하는 열을 관리합니다.
들어 장고 - mptt ,이 같은 구조를 사용 :
id parent_id tree_id 레벨 lft rght ---------- ------- ----- --- ---- 1 null 1014 2 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
다음과 같은 트리를 설명합니다 ( id각 항목 을 나타냄).
1
+-2
| +-3
| +-4
|
+-5
+-6
+-7
또는 lft및 rght값의 작동 방식을보다 명확하게하는 중첩 된 집합 다이어그램으로 :
__________________________________________________________________________ | 루트 1 | | ________________________________ ________________________________ | | | 아동 1.1 | | 아동 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열은 무엇보다 편의를 위해 denormalisation의 비트를하고 tree_id열은 다시 시작 할 수 있습니다 lft와 rght는 AS, 삽입, 이동 및 삭제에 의해 영향을 열 수를 줄이고 각 최상위 노드에 대한 번호 lft와 rght열해야 간격을 만들거나 닫기 위해 이러한 작업이 수행 될 때 적절하게 조정됩니다. 좀 만들어 개발 노트 나 각 작업에 필요한 쿼리 주위에 내 머리를 정리하려고했던 때를.
실제로이 데이터를 사용하여 트리를 표시하는 관점에서 tree_item_iterator, 각 노드에 대해 원하는 종류의 표시를 생성하기에 충분한 정보를 제공 하는 유틸리티 기능을 작성했습니다 .
MPTT에 대한 추가 정보 :
그것은 매우 오래된 질문이지만 많은 견해를 가지고 있기 때문에 대안을 제시 할 가치가 있다고 생각합니다. 제 의견으로는 매우 우아합니다.
트리 구조를 읽으려면 재귀 공통 테이블 표현식 (CTE)을 사용할 수 있습니다 . 한 번에 전체 트리 구조를 페치하고 노드 레벨, 상위 노드 및 상위 노드의 하위 내 순서에 대한 정보를 가질 수 있습니다.
PostgreSQL 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는 PostgreSQL, IBM DB2, MS SQL Server 및 Oracle 에서 사용할 수 있습니다 .
재귀 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'
Bill의 대답은 꽤 훌륭합니다.이 답변에는 스레드 지원 답변이 필요합니다.
어쨌든 트리 구조와 Order 속성을 지원하고 싶었습니다. 나는 원래 질문 (왼쪽에서 오른쪽 순서로 유지) leftSibling과 동일한 기능을 수행하는 각 노드에 단일 속성을 포함 시켰습니다 Order.
mysql> desc 노드; + ------------- + -------------- + -------- + ----- + ------- -+ ---------------- + | 분야 | 타입 | 널 | 키 | 기본 | 추가 | + ------------- + -------------- + -------- + ----- + ------- -+ ---------------- + | 아이디 | int (11) | 아니요 | PRI | NULL | 자동 증가 | | 이름 | varchar (255) | 예 | | NULL | | | leftSibling | int (11) | 아니요 | | 0 | | + ------------- + -------------- + -------- + ----- + ------- -+ ---------------- + 3 행 세트 (0.00 초) mysql> 디스크 인접성; + ------------ + --------- + ------ + ----- + --------- + --- ------------- + | 분야 | 타입 | 널 | 키 | 기본 | 추가 | + ------------ + --------- + ------ + ----- + --------- + --- ------------- + | relationId | int (11) | 아니요 | PRI | NULL | 자동 증가 | | 부모 | int (11) | 아니요 | | NULL | | | 아이 | int (11) | 아니요 | | NULL | | | pathLen | int (11) | 아니요 | | NULL | | + ------------ + --------- + ------ + ----- + --------- + --- ------------- + 4 행 세트 (0.00 초)
내 블로그에 자세한 내용과 SQL 코드가 있습니다.
감사합니다 Bill 귀하의 답변이 시작하는 데 도움이되었습니다!
선택의 여지가 있다면 객체를 사용하고 있습니다. 각 객체에 children컬렉션 이있는 각 레코드에 대한 객체를 만들고 Id가 키 인 assoc 배열 (/ hashtable)에 모두 저장합니다. 컬렉션을 한 번 습격하면 관련 어린이 필드에 어린이가 추가됩니다. 단순한.
그러나 좋은 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성가시다!) 작동합니다.
내 자신의 객체를 생성하고 있기 때문에 규칙을 어길 수도 있지만 실제 작업과의 전환 으로이 작업을 수행하고 있습니다. :)
또한 Node를 만들기 전에 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;
}
}
SQL 인덱스의 내부 btree 표현을 이용하는 훌륭한 솔루션이 있습니다. 이것은 1998 년경에 이루어진 훌륭한 연구를 바탕으로합니다.
다음은 예제 테이블입니다 (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 : 부모 노드에 대한 참조 (tw 사용), 루트에 null이 있습니다.
- sz : 자신을 포함한 노드 브랜치의 크기.
- nc : 구문 설탕으로 사용됩니다. tw + nc이며 노드의 "다음 자식"의 tw를 나타냅니다.
다음은 tw 순서로 정렬 된 예제 24 노드 모집단입니다.
+-----+---------+----+------+------+------+
| 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 |
+-----+---------+----+------+------+------+
형제 자매와 자녀는 사소합니다. tw로 pa 필드 순서를 사용하십시오.
자손
예를 들어 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 index 및 sz (분기 크기) 값은 삽입 지점 이후 모든 노드와 모든 조상에 대해 각각 업데이트되어야하기 때문입니다.
분기 이동은 분기의 tw 값을 범위 밖으로 이동하는 것을 포함하므로 분기를 이동할 때 외래 키 제약 조건을 비활성화해야합니다. 지점을 이동하려면 기본적으로 네 가지 쿼리가 필요합니다.
- 분기를 범위 밖으로 이동하십시오.
- 남은 간격을 닫습니다. (나머지 트리는 이제 정규화되었습니다).
- 갈 곳을여십시오.
- 지점을 새 위치로 이동하십시오.
트리 쿼리 조정
트리에서 간격의 열기 / 닫기는 만들기 / 업데이트 / 삭제 방법에 사용되는 중요한 하위 기능이므로 여기에 포함시킵니다.
우리는 두 가지 매개 변수가 필요합니다-우리가 축소 또는 확대 중 여부를 나타내는 플래그와 노드의 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에 대해 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의 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;
루트 요소가 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 지옥의 위험을 희생하여 완전히 새로운 세계를 열었습니다.
예제와 같이 요소가 트리 순서에 있으면 다음 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 닫기). 그런 다음 해당 노드의 시작을 출력하여 스택으로 푸시합니다.
중첩 요소가 아닌 들여 쓰기를 사용하여 트리를 출력하려면 print 문을 건너 뛰어 div를 인쇄하고 각 항목 전에 스택 크기의 배수와 같은 여러 공간을 인쇄하면됩니다. 예를 들어, 파이썬에서 :
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를 버릴 수 있습니다.
Bill의 SQL 솔루션을 확장하기 위해 기본적으로 평면 배열을 사용하여 동일한 작업을 수행 할 수 있습니다. 또한 문자열의 길이가 모두 같고 최대 자식 수가 알려진 경우 (예 : 이진 트리) 단일 문자열 (문자 배열)을 사용하여 수행 할 수 있습니다. 만약 당신이 임의의 수의 아이들을 가지고 있다면 이것은 조금 복잡해집니다. 나는 할 수있는 것을보기 위해 오래된 노트를 확인해야 할 것입니다.
그런 다음 약간의 메모리를 희생하십시오. 특히 트리가 희박하거나 불완전한 경우 약간의 인덱스 수학을 사용하여 트리에 너비를 먼저 저장하여 모든 문자열에 무작위로 액세스 할 수 있습니다 (이진의 경우) 나무):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
당신의 문자열 길이를 알고 있습니다.
나는 지금 일하고 있으므로 많은 시간을 할애 할 수는 없지만 관심을 가지고 이것을하기 위해 약간의 코드를 가져올 수 있습니다.
우리는 DNA 코돈으로 만든 이진 트리에서 검색하는 데 사용합니다. 프로세스는 트리를 빌드 한 다음 텍스트 패턴을 검색하기 위해 평평하게 만들었습니다. 빠르고 효율적이며 터프한 트리에는 빈 노드가 거의 없었지만 기가 바이트의 데이터를 순식간에 깎을 수있었습니다.
계층 구조에 neo4j와 같은 nosql 도구를 사용하는 것을 고려하십시오. 예를 들어 linkedin과 같은 네트워크 응용 프로그램은 couchbase (다른 nosql 솔루션)를 사용합니다.
그러나 데이터 마트 수준 쿼리에만 nosql을 사용하고 트랜잭션을 저장 / 유지하지 마십시오.
'Programing' 카테고리의 다른 글
| 셀의 텍스트 양에 관계없이 테이블 열 너비를 일정하게 설정 하시겠습니까? (0) | 2020.02.13 |
|---|---|
| Mac OS X에 Maven 설치 (0) | 2020.02.12 |
| 한 스트림의 내용을 다른 스트림으로 어떻게 복사합니까? (0) | 2020.02.12 |
| 새로운 요소를 추가하기 위해 열거 형을 서브 클래스 화 할 수 있습니까? (0) | 2020.02.12 |
| 사용중인 Swift 버전을 어떻게 확인합니까? (0) | 2020.02.12 |