복붙노트

[SQL] 나무에 평평한 테이블을 구문 분석하는 가장 효율적인 / 우아한 방법은 무엇입니까?

SQL

나무에 평평한 테이블을 구문 분석하는 가장 효율적인 / 우아한 방법은 무엇입니까?

당신이 저장 순서 트리 계층 평평한 테이블이 있다고 가정 :

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] 이름을 가지고 다이어그램입니다. 루트 노드 0은 허구입니다.

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

당신이 출력에 최소한 어떤 방법을 사용할 것이라고 올바르게 정렬, 제대로 들여 쓰기 트리로 HTML (또는 그 문제에 대한 텍스트)에?

더 당신이 기본적인 데이터 구조 (배열과 HashMaps을)가 가정 더 멋진 부모 / 자녀 참조, 아니 ORM, 아니 프레임 워크, 당신의 두 손으로 오브젝트 없습니다. 테이블은 랜덤 액세스 할 수있는 결과 집합으로 표현된다.

의사 코드 또는 일반 영어 이것은 순전히 개념 질문, 괜찮습니다.

보너스 질문 : RDBMS에서이 같은 트리 구조를 저장하는 근본적으로 더 좋은 방법이 있나요?

편집 및 추가

한 주석의 (마크 Bessey의) 질문에 대답하려면 : 결코 어쨌든 표시 될 것 없기 때문에 루트 노드가 필요하지 않습니다. ParentId = 0 "이 최고 수준이다"표현하는 규칙이다. 같은 부모를 가진 노드가는 방법을 주문 열을 정의 정렬 할 수 있습니다.

내가 HashMaps을 배열로 묘사 될 수 말한 "결과 집합"(이 용어를 유지하기 위해). 내 예를 들어 이미 될 운명이되었다. 일부 답변은 여분의 마일을 가서 먼저 구성하지만, 그게 좋아.

나무는 임의의 깊이가 될 수 있습니다. 각 노드는 N의 아이를 가질 수 있습니다. 나는 정확히하지만, 마음에 트리 "는 수백만 개의 항목이"하지 않았다.

에 의존하는 뭔가를 노드 이름의 나의 선택 ( '노드 1.1.1')을 혼동하지 마십시오. 노드는 동일하게이 그것을 읽을 수 있도록 단지이고, 어떤 이름 구조하는 것은 아니다 '프랭크'또는 '밥'이라고 할 수있다.

너희들이 조각을 뽑을 수 있도록 내 자신의 솔루션을 게시했다.

해결법

  1. ==============================

    1.이제 MySQL을 8.0 지원하는 쿼리를 재귀 것을, 우리는 모든 인기있는 SQL 데이터베이스가 표준 문법에 재귀 쿼리를 지원 말할 수 있습니다.

    이제 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 년 내 프리젠 테이션 재귀 쿼리 Throwdown에 MySQL은 8.0 재귀 쿼리를 테스트했다.

    다음은 2008 년 내 원래 대답은 :

    관계형 데이터베이스에 저장하는 트리 구조 데이터에 대한 여러 가지가 있습니다. 당신이 당신의 예에 표시하는 두 가지 방법을 사용합니다 :

    또 다른 해결책은 중첩 된 세트라고하며 너무 같은 테이블에 저장할 수 있습니다. 이러한 디자인에 대한 더 많은 정보를 조 셀코에 의해 "에 smarties에 대한 SQL에서 나무와 계층"을 참조하십시오.

    나는 보통 트리 구조 데이터를 저장하기위한 폐쇄 표 (일명 "인접 관계")라는 디자인을 선호합니다. 그것은 다른 테이블이 필요하지만, 다음 나무를 조회하는 것은 매우 쉽습니다.

    데이터베이스 프로그래밍의 함정을 피하기 : 나는 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 | 
+----+

    그들은 별도의 계층 구조의있는 거 부분은 노드 1에서 하강 때문이 아니라 즉, 노드 3, 5는 제외됩니다.

    재 : 직접적인 아이 (또는 바로 위 부모)에 대한 전자 satis에서 코멘트. 당신은 쉽게 즉시 자녀 또는 부모 (또는 다른 거리)을 위해 특별히 쿼리 만들기 위해 ClosureTable에 "PATH_LENGTH '항목을 추가 할 수 있습니다.

    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_LENGTH 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에서 코멘트 제목 : Re : "어떻게 전체 트리를 정렬에 대한 [이름]?"

    여기서, 노드 1의 후손 모든 노드를 돌려 그들을 다른 노드 이름과 같은 속성 및 종류의 이름이 들어있는 FlatTable에 가입 ​​예를 들어 쿼리입니다.

    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 사회자는 편집 승인,하지만 난 그것을 반대하고있다.

    편집 위의 마지막 쿼리가 b.path_length에 의해 ORDER해야한다에 BY 순서는, f.name, 아마도 확인 순서가 계층 구조를 일치하는지 확인하는 것이 좋습니다. 그것은 "노드 1.2"후 "노드 1.1.1"을 주문 때문에 그러나 이것은,하지 작업을 수행합니다.

    당신은 순서가 합리적인 방법으로 계층 구조를 일치시킬 경우에, 그것은 가능하지만, 단순히 경로 길이에 의해 순서입니다. 예를 들어, MySQL의 폐쇄 표 계층 데이터베이스에 대한 내 대답을 참조 - 어떻게 풀 정보를 올바른 순서로.

  2. ==============================

    2.중첩 된 세트를 사용하는 경우에 필요에 따라 더 비싼 삽입의 비용으로, 단일 쿼리 트리 위해 그 안에 전체 트리 구조 또는 하위 트리를 추출 할 수 있습니다 (때로는 수정 된 예약 주문 트리 순회로 함) 너를 트리 구조를 통해 순서대로의 경로를 설명하는 열을 관리한다.

    중첩 된 세트를 사용하는 경우에 필요에 따라 더 비싼 삽입의 비용으로, 단일 쿼리 트리 위해 그 안에 전체 트리 구조 또는 하위 트리를 추출 할 수 있습니다 (때로는 수정 된 예약 주문 트리 순회로 함) 너를 트리 구조를 통해 순서대로의 경로를 설명하는 열을 관리한다.

    장고 - mptt를 들어,이 같은 구조를 사용 :

    id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

    어느 (ID 각 항목을 나타내는와) 같이 보이는 트리를 설명합니다 :

     1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

    또는, 더 분명하게 중첩 된 세트도 같은 방법 왼쪽과 오른쪽 값 작업 :

     __________________________________________________________________________
|  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
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

    당신이 볼 수 있듯이, 트리 순서로 주어진 노드의 전체 하위 트리를 얻을, 당신은 단순히 LFT와 LFT와 rght 값 사이 rght 값이 모든 행을 선택해야합니다. 그것은 주어진 노드에 대한 조상의 트리를 검색하는 것이 간단합니다.

    레벨 열은 더 무엇보다 편리하고 tree_id 열에 대한 denormalisation의 비트가 LFT, 당신은 삽입, 이동 및 삭제에 의해 영향을 열 수를 줄이고 각 최상위 노드에 대한 LFT와 rght 번호를 다시 시작할 수있다 및 rght 열은 이러한 작업을 만들기 위해 또는 가까운 간격에서 일어날 때 따라 조정되어야한다. 나는 각 작업에 필요한 쿼리 주위에 내 머리를 정리하려고 당시 일부 개발 메모를했다.

    실제로 트리를 표시하려면이 데이터로 작업의 측면에서, 나는 각 노드에 대해, 당신이 원하는 디스플레이의 어떤 종류를 생성 할 수있는 충분한 정보를 제공해야하는 tree_item_iterator 유틸리티 기능을 만들었습니다.

    MPTT에 대한 자세한 정보 :

  3. ==============================

    3.그것은 아주 오래된 질문이다, 그러나 많은 뷰를 가지고 나는이 솔루션을 매우 우아 그것의 가치는 대안을 제시하기 위해 생각하고, 내 의견이다.

    그것은 아주 오래된 질문이다, 그러나 많은 뷰를 가지고 나는이 솔루션을 매우 우아 그것의 가치는 대안을 제시하기 위해 생각하고, 내 의견이다.

    당신은 재귀 공통 테이블 식 (CTE를)를 사용할 수있는 트리 구조를 읽기 위해. 그것은 노드, 부모 노드의 자식에서 부모 노드와 질서의 수준에 대한 정보를 한 번에 전체 트리 구조를 가져올 수있는 가능성을 제공합니다.

    이 PostgreSQL의 9.1에서 어떻게 작동하는지 내가 당신을 보여 드리죠.

  4. ==============================

    4.오라클 9i의의, 당신은 CONNECT BY를 사용할 수 있습니다.

    오라클 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 서버 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]

    모두가 출력됩니다 다음과 같은 결과.

    Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'
  5. ==============================

    5.빌의 대답은 꽤 세상에-꿰매 좋은,이 대답은 나를 SO 지원 스레드 답변을 할 수있는 여기에 몇 가지를 추가합니다.

    빌의 대답은 꽤 세상에-꿰매 좋은,이 대답은 나를 SO 지원 스레드 답변을 할 수있는 여기에 몇 가지를 추가합니다.

    어쨌든 나는 트리 구조 및 주문 속성을 지원하고 싶었다. 나는 각 노드에 하나의 속성이 주문은 원래의 질문에 어떻게 의미 같은 일을 (유지 왼쪽에서 오른쪽 순서)하지 leftSibling라는 포함되어 있습니다.

    mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

    내 블로그에 대한 자세한 세부 사항 및 SQL 코드입니다.

    감사 빌은 당신의 대답은 시작에 도움이되었다!

  6. ==============================

    6.글쎄, 난 개체를 사용하려는 선택을 제공. 나는 각각의 객체가 자식 컬렉션을 가지고 각 레코드에 대해 객체를 생성하고 ASSOC 배열 (/ 해시 테이블) ID가 열쇠에 그들 모두를 저장하는 것입니다. 그리고 컬렉션을 습격 한 번, 관련 아이들 필드에 아이를 추가. 단순한.

    글쎄, 난 개체를 사용하려는 선택을 제공. 나는 각각의 객체가 자식 컬렉션을 가지고 각 레코드에 대해 객체를 생성하고 ASSOC 배열 (/ 해시 테이블) 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 경로를 이동합니다.

  7. ==============================

    7.이 신속하게 작성하고도 꽤도 효율적이다 (플러스는 INT 사이의 변환, 많이 autoboxes 및 정수 성가신입니다!)하지만, 그것은 작동했다.

    이 신속하게 작성하고도 꽤도 효율적이다 (플러스는 INT 사이의 변환, 많이 autoboxes 및 정수 성가신입니다!)하지만, 그것은 작동했다.

    난 내 자신의 객체를 만드는거야하지만 헤이 나는 실제 작업에서 기분 전환으로이 일을하고있어 이후로 아마 규칙을 나누기 :)

    이것은 또한 당신이 행 수십만이있는 경우 가장 좋은 솔루션이 아닐 것이다 노드를 구축 시작하기 전에 결과 집합 / 테이블이 완전히 구조의 일종으로 읽기를 실행하는 것을 가정한다.

    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;
    }
}
  8. ==============================

    8.SQL 인덱스의 내부 BTREE 표현을 악용 좋은 솔루션은 정말 있습니다. 이 1998 년의 주위에 훌륭한 연구를 수행 백을 기반으로합니다.

    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에 의해 주문 예를 들어 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 지수와 SZ (지점 크기) 값이 삽입 지점 이후 모든 노드에 업데이트 할 필요가 있고, 각각의 모든 조상 때문에 삽입 / 삭제 비용이 높다.

    분기 이동은 지점을 이동할 때 그것은 또한 비활성화 외래 키 제약 할 필요가 있으므로, 범위를 벗어난 지점의 TW 값을 이동 포함한다. 지점을 이동하는 데 필요한 네 개의 쿼리는 본질적으로있다 :

    트리 쿼리를 조정

    내가 여기 포함 있도록 개방 / 트리 격차의 개폐, 생성 / 업데이트 / 삭제 방법으로 사용되는 중요한 하위 기능입니다.

    우리는 두 개의 매개 변수를 필요 - 플래그는 우리가 축소 또는 대형화 및 노드의 TW 지수할지 여부를 나타내는. 따라서, 예를 들어 TW (5 지점의 크기를 갖는) = 18. '-'우리가 사용하고 있는지,이 수단 -의 우리가 (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;

    그리고 우리는 그 파의 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;
  9. ==============================

    9.여기에 텍스트를 출력 할 의사가있어, 루트 요소가 제로 것을 알고 있다고 가정 :

    여기에 텍스트를 출력 할 의사가있어, 루트 요소가 제로 것을 알고 있다고 가정 :

    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)
  10. ==============================

    10.그 끔찍한 제한하지 그래서 당신은 해시 맵과 다른 데이터 구조를 에뮬레이션 할 수 있습니다. 위에서 아래로 스캔, 각 컬럼에 대한 항목과 데이터베이스의 각 행에 대해 해시 맵을 만들 수 있습니다. 아이디에 맞는 "마스터"해시 맵, 이러한 HashMaps을 각각 추가합니다. 모든 노드는 아직 보지 못했다하는 "부모"가있는 경우, 마스터 해시 맵에 대한 자리 표시 자 항목을 작성, 당신은 실제 노드를 볼 때 그것을 채우십시오.

    그 끔찍한 제한하지 그래서 당신은 해시 맵과 다른 데이터 구조를 에뮬레이션 할 수 있습니다. 위에서 아래로 스캔, 각 컬럼에 대한 항목과 데이터베이스의 각 행에 대해 해시 맵을 만들 수 있습니다. 아이디에 맞는 "마스터"해시 맵, 이러한 HashMaps을 각각 추가합니다. 모든 노드는 아직 보지 못했다하는 "부모"가있는 경우, 마스터 해시 맵에 대한 자리 표시 자 항목을 작성, 당신은 실제 노드를 볼 때 그것을 채우십시오.

    그것을 밖으로 인쇄하려면, 그 길을 따라 들여 쓰기 수준을 추적, 데이터를 통해 간단한 깊이 우선 통과 할. 각 행에 대해 "어린이"항목을 유지하고 스캔 데이터로 채우기에 의해이 쉽게 할 수 있습니다.

    당신이 데이터를 사용하는거야 방법에 따라 달라집니다 데이터베이스에 나무를 저장하는 "더 나은"방법이 있는지에 관해서는. 나는 계층 구조의 각 수준에 대해 서로 다른 테이블을 사용 알려진 최대 깊이를 가지고 시스템을 보았다. 모든 (최상위 범주 잎과 다른 것을) 후 트리의 수준이 꽤 해당하는 경우 그 많은 이해된다.

  11. ==============================

    11.중첩 된 해시 맵 또는 배열을 생성 할 수 있다면, 나는 단순히 처음부터 테이블을 내려 가서 중첩 된 배열에 각 항목을 추가 할 수 있습니다. 나는에 삽입 할 중첩 된 배열하는 수준 알기 위해 루트 노드의 각 줄에 추적해야합니다. 나는 또 다시 같은 부모를보고 할 필요가 없습니다 그래서 나는 메모이 제이션을 사용할 수 있습니다.

    중첩 된 해시 맵 또는 배열을 생성 할 수 있다면, 나는 단순히 처음부터 테이블을 내려 가서 중첩 된 배열에 각 항목을 추가 할 수 있습니다. 나는에 삽입 할 중첩 된 배열하는 수준 알기 위해 루트 노드의 각 줄에 추적해야합니다. 나는 또 다시 같은 부모를보고 할 필요가 없습니다 그래서 나는 메모이 제이션을 사용할 수 있습니다.

    편집 :이 반복적으로 DB를 조회하지 않도록 내가 먼저 배열로 전체 테이블을 읽을 것이다. 테이블이 매우 큰 경우 물론이 실용적이지 않을 것입니다.

    구조가 구축 후, 나는 그것을 통해 깊이 첫 번째 횡단을하고 HTML을 출력해야합니다.

    ), 그리고 더 나은 솔루션을보고 싶지만, 하나 개의 테이블을 사용하여이 정보를 저장하는 기본적인 방법은 더 좋은있다 (비록 잘못 될 수 없었다). 당신이 고용 동적으로 생성 DB 테이블에 대한 스키마를 만들 경우, 당신은 단순함의 희생, 그리고 SQL 지옥의 위험에서 완전히 새로운 세계를 열어).

  12. ==============================

    12.귀하의 예와 같이 요소, 트리 순서에있는 경우, 다음과 같은 파이썬 예제 같은 것을 사용할 수 있습니다 :

    귀하의 예와 같이 요소, 트리 순서에있는 경우, 다음과 같은 파이썬 예제 같은 것을 사용할 수 있습니다 :

    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를 인쇄하려면 인쇄 문을 건너 뛰고 각 항목 전에 스택의 크기의 몇 배수로 동일 공간의 수를 인쇄 할 수 있습니다. 예를 들어, 파이썬에서 :

    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에 저장할 수 있습니다.

  13. ==============================

    13.빌의 SQL 솔루션을 확장하려면 기본적으로 평면 배열을 사용하여 동일한 작업을 수행 할 수 있습니다. 또한 많은 경우 문자열은 모두 같은 아이폰에와 알려진 어린이의 최대 수를 (이진 트리에서 말하는) 당신은 하나의 문자열 (문자 배열)를 사용하여 그것을 할 수 있습니다. 당신이 아이들의 임의의 번호가있는 경우이 조금 ... 내가 무엇을 할 수 있는지 보는 나의 오래된 노트를 확인해야 일을 복잡하게한다.

    빌의 SQL 솔루션을 확장하려면 기본적으로 평면 배열을 사용하여 동일한 작업을 수행 할 수 있습니다. 또한 많은 경우 문자열은 모두 같은 아이폰에와 알려진 어린이의 최대 수를 (이진 트리에서 말하는) 당신은 하나의 문자열 (문자 배열)를 사용하여 그것을 할 수 있습니다. 당신이 아이들의 임의의 번호가있는 경우이 조금 ... 내가 무엇을 할 수 있는지 보는 나의 오래된 노트를 확인해야 일을 복잡하게한다.

    그런 다음, 무작위로 바이너리를 위해 (때문에 같은 배열의 폭 첫째, 당신의 나무를 저장하여 트리 인덱스 수학, 액세스 모든 문자열의 비트와 함께, 당신이 할 수있는, 드문 드문 및 / 또는 unballanced 특히 경우, 메모리의 비트를 희생 나무):

    String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

    요 당신의 문자열 길이를 알고, 당신은 그것을 알고 나는 거기에 많은 시간을 할애 할 수는 없지만 관심을 가지고 내가이 작업을 수행하는 코드의 비트를 가져올 수 있습니다 그래서 지금 직장에서입니다. 우리는 DNA 코돈으로 만든 이진 트리에서 검색을 수행하는 데 사용, 프로세스 트리를 구축, 우리는 텍스트 패턴을 검색하도록 평평하고, 인덱스 수학하지만 (위에서 REVERS)를 발견했을 때 우리는 ... 노드 다시 매우 얻을 신속하고 효율적인, 우리의 나무는 거의 빈 노드 없었다 터프하지만 우리는 순식간에 기가 바이트의 데이터를 searh 수 있습니다.

  14. ==============================

    14.계층 구조에 대한 neo4j 같은 NoSQL의 도구를 사용하는 방법에 대한 생각. 용도 링크드 등 예컨대 네트워크 애플리케이션 카우치베이스 주식회사 (다른 NoSQL의 용액)

    계층 구조에 대한 neo4j 같은 NoSQL의 도구를 사용하는 방법에 대한 생각. 용도 링크드 등 예컨대 네트워크 애플리케이션 카우치베이스 주식회사 (다른 NoSQL의 용액)

    하지만 데이터 마트 수준의 쿼리 및 저장하지에 NoSQL의 사용 / 트랜잭션을 유지

    15. from https://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree by cc-by-sa and MIT license

'SQL' 카테고리의 다른 글

[SQL] 어떻게 SQL의 다른 열을 기준으로 DISTINCT MAX (열 값)와 행을 선택할 수 있습니까?  (0) 2020.03.05
[SQL] 나는 하나 개의 필드에 여러 개의 MySQL의 행을 연결할 수 있습니까?  (0) 2020.03.05
[SQL] INNER가, 왼쪽, 오른쪽 조인 및 FULL은 조인의 차이점은 무엇입니까? [복제]  (0) 2020.03.05
[SQL] 분류 결과 각 그룹에 대해 상위 N 레코드를 가져 오기  (0) 2020.03.05
[SQL] 명시 대 암시 SQL 조인  (0) 2020.03.05
,

티스토리툴바