Jaki jest najbardziej efektywny / elegancki sposób parsowania płaskiego stołu do drzewa?

Załóżmy, że masz płaską tabelę, która przechowuje uporządkowaną hierarchię drzew:

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

Oto schemat, na którym mamy [id] Name. Węzeł główny 0 jest fikcyjny.

                       [0] ROOT
                          / \ 
              [1] Węzeł 1 [3] Węzeł 2
              / \ \
    [2] Węzeł 1.1 [6] Węzeł 1.2 [5] Węzeł 2.1
          /          
 [4] Węzeł 1.1.1

Jakiego minimalistycznego podejścia zastosowałbyś do wyprowadzenia go do HTML (lub tekstu, jeśli o to chodzi) jako poprawnie uporządkowane, poprawnie wcięte drzewo?

Załóżmy, że masz tylko podstawowe struktury danych (tablice i mapy skrótów), żadnych wymyślnych obiektów z odniesieniami do rodziców / dzieci, bez ORM, bez frameworka, tylko dwie ręce. Tabela jest reprezentowana jako zestaw wyników, do którego można uzyskać dostęp losowo.

Pseudokod lub zwykły angielski jest w porządku, jest to pytanie czysto koncepcyjne.

Pytanie dodatkowe: Czy istnieje zasadniczo lepszy sposób przechowywania takiej struktury drzewa w RDBMS?

EDYCJE I DODATKI

Aby odpowiedzieć na pytanie jednego komentatora ( Marka Besseya ): Węzeł główny nie jest konieczny, ponieważ i tak nigdy nie zostanie wyświetlony. ParentId = 0 to konwencja wyrażająca „to najwyższy poziom”. Kolumna Kolejność określa sposób sortowania węzłów z tym samym rodzicem.

„Zestaw wyników”, o którym mówiłem, można przedstawić jako tablicę skrótów (aby pozostać w tej terminologii). Bo mój przykład miał już tam być. Niektóre odpowiedzi idą o krok dalej i najpierw je konstruują, ale nie ma sprawy.

Drzewo może być dowolnie głębokie. Każdy węzeł może mieć N dzieci. Nie miałem jednak dokładnie na myśli drzewa „milionów wpisów”.

Nie pomyl mojego wyboru nazewnictwa węzłów („Węzeł 1.1.1”) z czymś, na czym można polegać. Węzły można równie dobrze nazwać „Frank” lub „Bob”, nie sugeruje się żadnej struktury nazewnictwa, tylko po to, aby była czytelna.

Opublikowałem własne rozwiązanie, abyście mogli je rozłożyć na kawałki.

Teraz, gdy MySQL 8.0 obsługuje zapytania rekurencyjne , możemy powiedzieć, że wszystkie popularne bazy danych SQL obsługują zapytania rekurencyjne w standardowej składni.

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;

Testowałem zapytania rekurencyjne w MySQL 8.0 w mojej prezentacji Recursive Query Throwdown w 2017 roku.

Poniżej moja oryginalna odpowiedź z 2008 roku:

Istnieje kilka sposobów przechowywania danych o strukturze drzewa w relacyjnej bazie danych. To, co pokazano w przykładzie, wykorzystuje dwie metody:

• Lista Adjacency (kolumna „macierzysta”) i
• Wyliczenie ścieżki (kropkowane liczby w kolumnie z Twoim imieniem).

Inne rozwiązanie nazywa się zestawami zagnieżdżonymi i można je również przechowywać w tej samej tabeli. Przeczytaj „ Drzewa i hierarchie w SQL for Smarties ” Joe Celko, aby uzyskać więcej informacji na temat tych projektów.

Zwykle wolę projekt o nazwie Tabela zamknięcia (aka „Adjacency Relation”) do przechowywania danych o strukturze drzewa. Wymaga kolejnej tabeli, ale wyszukiwanie drzew jest dość łatwe.

Omawiam tabelę zamknięcia w mojej prezentacji Modele danych hierarchicznych z SQL i PHP oraz w mojej książce Antypatterny SQL: unikanie pułapek programowania baz danych .

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)
);

Przechowuj wszystkie ścieżki w tabeli zamknięcia, gdzie istnieje bezpośrednie pochodzenie od jednego węzła do drugiego. Dołącz wiersz dla każdego węzła, aby sam się do niego odwoływał. Na przykład używając zestawu danych pokazanego w pytaniu:

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);

Teraz możesz uzyskać drzewo zaczynające się od węzła 1 w następujący sposób:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

Dane wyjściowe (w kliencie MySQL) wyglądają następująco:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

Innymi słowy, węzły 3 i 5 są wykluczone, ponieważ są częścią oddzielnej hierarchii, nie schodząc z węzła 1.

Re: komentarz e-satis na temat bezpośrednich dzieci (lub bezpośredniego rodzica). Możesz dodać path_lengthkolumnę „ ” ClosureTabledo, aby ułatwić zapytanie dotyczące bezpośredniego dziecka lub rodzica (lub dowolnej innej odległości).

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);

Następnie możesz dodać termin do wyszukiwania w celu zapytania o bezpośrednie elementy potomne danego węzła. Są to potomkowie, których path_lengthjest 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 | 
+----+

Ponownie skomentuj @ashraf: „A co z sortowaniem całego drzewa [według nazwy]?”

Oto przykładowe zapytanie, aby zwrócić wszystkie węzły potomków węzła 1, dołączyć je do FlatTable, który zawiera inne atrybuty węzła, takie jak name, i posortować według nazwy.

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

Ponownie skomentuj @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         |
+------------+-------------+

Użytkownik zaproponował dziś edycję. Moderatorzy SO zaakceptowali zmianę, ale ja ją cofam.

Edycja sugerowała, że ​​ORDER BY w ostatnim zapytaniu powyżej powinien być ORDER BY b.path_length, f.name, prawdopodobnie, aby upewnić się, że kolejność jest zgodna z hierarchią. Ale to nie działa, ponieważ porządkuje „Node 1.1.1” po „Node 1.2”.

Jeśli chcesz, aby porządkowanie pasowało do hierarchii w rozsądny sposób, jest to możliwe, ale nie tylko poprzez uporządkowanie według długości ścieżki. Na przykład zobacz moją odpowiedź na hierarchiczną bazę danych MySQL Closure Table - Jak wyciągać informacje we właściwej kolejności .

Jeśli używasz zestawów zagnieżdżonych (czasami nazywanych zmodyfikowanym przejściem drzewa w przedsprzedaży), możesz wyodrębnić całą strukturę drzewa lub dowolne poddrzewo w jej kolejności w drzewie za pomocą jednego zapytania, kosztem wstawek jest droższy, ponieważ musisz zarządzaj kolumnami opisującymi uporządkowaną ścieżkę przez strukturę drzewa.

W przypadku django-mptt użyłem takiej struktury:

id parent_id tree_id poziom 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

Który opisuje drzewo, które wygląda tak (z idreprezentowaniem każdego elementu):

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

Lub jako diagram zestawu zagnieżdżonego, co czyni bardziej oczywistym sposób działania wartości lfti rght:

 __________________________________________________________________________
| Korzeń 1 |
| ________________________________ ________________________________ |
| | Dziecko 1.1 | | Dziecko 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
| | ________________________________ | | ________________________________ | |
| __________________________________________________________________________ |

Jak widać, aby uzyskać całe poddrzewo dla danego węzła, w kolejności drzewa, wystarczy wybrać wszystkie wiersze, które mają lfti rghtwartości między nim lfta rghtwartościami. Łatwo jest również pobrać drzewo przodków dla danego węzła.

levelKolumna jest trochę denormalizacja dla wygody bardziej niż cokolwiek innego, a tree_idkolumna pozwala na ponowne uruchomienie lfti rghtnumeracji dla każdego węzła najwyższego poziomu, co zmniejsza liczbę kolumn dotkniętych wkładki, ruchów i delecji, jak lfti rghtkolumny mają być odpowiednio korygowane, gdy operacje te mają miejsce w celu utworzenia lub zamknięcia luk. Zrobiłem kilka notatek programistycznych w czasie, gdy próbowałem owinąć głowę zapytaniami wymaganymi dla każdej operacji.

Jeśli chodzi o faktyczną pracę z tymi danymi w celu wyświetlenia drzewa, stworzyłem funkcję tree_item_iteratornarzędzia, która dla każdego węzła powinna dostarczyć informacji wystarczających do wygenerowania dowolnego rodzaju wyświetlania.

Więcej informacji o MPTT:

• Drzewa w SQL
• Przechowywanie danych hierarchicznych w bazie danych
• Zarządzanie danymi hierarchicznymi w MySQL

To dość stare pytanie, ale ponieważ ma wiele poglądów, myślę, że warto przedstawić alternatywne i moim zdaniem bardzo eleganckie rozwiązanie.

Aby odczytać strukturę drzewa, możesz użyć rekurencyjnych wspólnych wyrażeń tabelowych (CTE). Daje to możliwość pobrania całej struktury drzewa na raz, uzyskania informacji o poziomie węzła, jego węźle nadrzędnym i kolejności w elementach potomnych węzła nadrzędnego.

Pokażę ci, jak to będzie działać w PostgreSQL 9.1.

1. Utwórz strukturę

   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);

2. Napisz zapytanie

   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;

   Oto wyniki:

    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)

   Węzły drzew są uporządkowane według poziomu głębokości. W końcowym wyniku przedstawilibyśmy je w kolejnych wierszach.

   Dla każdego poziomu są one uporządkowane według parent_id i node_order w obrębie rodzica. Dzięki temu dowiemy się, jak zaprezentować je w węźle wyjściowym - link do elementu nadrzędnego w tej kolejności.

   Mając taką strukturę, nie byłoby trudno stworzyć naprawdę ładną prezentację w HTML.

   Rekurencyjne CTE są dostępne w PostgreSQL, IBM DB2, MS SQL Server i Oracle .

   Jeśli chcesz przeczytać więcej na temat rekurencyjnych zapytań SQL, możesz sprawdzić dokumentację swojego ulubionego DBMS lub przeczytać dwa moje artykuły dotyczące tego tematu:

   • Do It In SQL: Recursive Tree Traversal
   • Poznaj moc zapytań rekurencyjnych SQL

Począwszy od Oracle 9i, możesz używać 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)

Począwszy od SQL Server 2005, można używać rekurencyjnego wspólnego wyrażenia tabelowego (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]

Oba wygenerują następujące wyniki.

Imię
„Węzeł 1”
„Węzeł 1.1”
„Węzeł 1.1.1”
„Węzeł 1.2”
„Węzeł 2”
„Węzeł 2.1”

Odpowiedź Billa jest cholernie dobra, ta odpowiedź dodaje do niej pewne rzeczy, co sprawia, że ​​życzę SO obsługiwanych wątków.

W każdym razie chciałem wesprzeć strukturę drzewa i właściwość Order. W każdym wywołanym węźle zawarłem jedną właściwość, leftSiblingktóra robi to samo, co Orderw pierwotnym pytaniu (zachowaj porządek od lewej do prawej).

mysql> desc nodes;
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| Pole | Wpisz | Zero | Klucz | Domyślnie | Extra |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| id | int (11) | NIE PRI | NULL | auto_increment |
| nazwa | varchar (255) | TAK | | NULL | |
| leftSibling | int (11) | NIE | 0 | |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
3 rzędy w zestawie (0,00 s)

mysql> desc przylegania;
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| Pole | Wpisz | Zero | Klucz | Domyślnie | Extra |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| relationsId | int (11) | NIE PRI | NULL | auto_increment |
| rodzic | int (11) | NIE | NULL | |
| dziecko | int (11) | NIE | NULL | |
| pathLen | int (11) | NIE | NULL | |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
4 rzędy w zestawie (0,00 s)

Więcej szczegółów i kod SQL na moim blogu .

Dzięki Bill Twoja odpowiedź była pomocna w rozpoczęciu!

Biorąc pod uwagę wybór, używałbym przedmiotów. Tworzę obiekt dla każdego rekordu, w którym każdy obiekt ma childrenkolekcję, i przechowuję je wszystkie w tablicy assoc (/ hashtable), w której kluczem jest identyfikator. I raz przejrzyj kolekcję, dodając dzieci do odpowiednich pól dla dzieci. Prosty.

Ale ponieważ nie sprawia ci to przyjemności, ograniczając korzystanie z dobrego OOP, prawdopodobnie wykonałbym iterację w oparciu o:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Edycja: jest podobny do kilku innych pozycji, ale myślę, że jest nieco czystszy. Dodam jeszcze jedną rzecz: jest to bardzo wymagające SQL. To przykre . Jeśli masz wybór, wybierz trasę OOP.

Zostało to napisane szybko i nie jest ani ładne, ani wydajne (a ponadto bardzo się autoboxuje, konwersja między inti Integerjest denerwujące!), Ale działa.

Prawdopodobnie łamie to zasady, ponieważ tworzę własne obiekty, ale hej robię to jako odwrócenie uwagi od prawdziwej pracy :)

Zakłada się również, że wynik / tabela wyników jest całkowicie wczytywana w jakąś strukturę przed rozpoczęciem budowania Węzłów, co nie byłoby najlepszym rozwiązaniem, jeśli masz setki tysięcy wierszy.

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;
    }
}

Istnieją naprawdę dobre rozwiązania, które wykorzystują wewnętrzną reprezentację btree indeksów sql. Jest to oparte na świetnych badaniach z 1998 roku.

Oto przykładowa tabela (w 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
)

Jedynymi polami niezbędnymi do przedstawienia drzewa są:

• tw: Indeks zamówień w przedsprzedaży DFS od lewej do prawej, gdzie root = 1.
• pa: Odwołanie (przy użyciu tw) do węzła nadrzędnego, root ma wartość NULL.
• sz: Rozmiar gałęzi węzła łącznie z samym sobą.
• nc: jest stosowany jako cukier składniowy. jest to tw + nc i reprezentuje tw „następnego potomka” węzła.

Oto przykładowa populacja 24 węzłów, uporządkowana według 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 |
+-----+---------+----+------+------+------+

Każdy wynik drzewa można wykonać nierekurencyjnie. Na przykład, aby uzyskać listę przodków węzła o tw = '22 '

Przodkowie

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 |
+-----+---------+----+------+------+------+

Rodzeństwo i dzieci są trywialne - wystarczy użyć pa pa uporządkowania przez tw.

Potomków

Na przykład zbiór (gałąź) węzłów zrootowanych na 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 |
+-----+---------+----+------+------+------+

Dodatkowe uwagi

Metodologia ta jest niezwykle przydatna, gdy liczba odczytów jest znacznie większa niż w przypadku wstawek lub aktualizacji.

Ponieważ wstawienie, przesunięcie lub aktualizacja węzła w drzewie wymaga dostosowania drzewa, konieczne jest zablokowanie tabeli przed rozpoczęciem akcji.

Koszt wstawienia / usunięcia jest wysoki, ponieważ wartości indeksu tw i sz (rozmiar gałęzi) będą musiały zostać zaktualizowane we wszystkich węzłach po punkcie wstawienia i odpowiednio dla wszystkich przodków.

Przenoszenie gałęzi polega na przesunięciu wartości tw gałęzi poza zakres, dlatego konieczne jest również wyłączenie ograniczeń klucza obcego podczas przenoszenia gałęzi. Aby przenieść gałąź, wymagane są zasadniczo cztery zapytania:

• Przenieś gałąź poza zasięg.
• Zamknij pozostawioną szczelinę. (pozostałe drzewo jest teraz znormalizowane).
• Otwórz lukę, do której to dojdzie.
• Przenieś gałąź do nowej pozycji.

Dostosuj zapytania o drzewa

Otwieranie / zamykanie luk w drzewie jest ważną podfunkcją używaną przez metody create / update / delete, dlatego dołączam ją tutaj.

Potrzebujemy dwóch parametrów - flagi reprezentującej to, czy zmniejszamy czy powiększamy, oraz indeksu tw węzła. Na przykład tw = 18 (która ma rozmiar gałęzi 5). Załóżmy, że zmniejszamy rozmiar (usuwamy tw) - oznacza to, że używamy „-” zamiast „+” w aktualizacjach poniższego przykładu.

Najpierw używamy (nieco zmienionej) funkcji przodka, aby zaktualizować wartość 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));

Następnie musimy dostosować tw dla tych, których tw jest wyższy niż gałąź do usunięcia.

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;

Następnie musimy dostosować rodzica dla tych, których pa tw jest wyższe niż gałąź do usunięcia.

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;

Zakładając, że wiesz, że elementy główne są równe zero, oto pseudokod do wyprowadzenia na tekst:

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)

Możesz emulować dowolną inną strukturę danych za pomocą mapy skrótów, więc nie jest to straszne ograniczenie. Skanując od góry do dołu, tworzysz mapę dla każdego wiersza bazy danych z wpisem dla każdej kolumny. Dodaj każdy z tych skrótów do „głównego” skrótu, wpisanego w id. Jeśli jakikolwiek węzeł ma „element nadrzędny”, którego jeszcze nie widziałeś, utwórz dla niego pozycję zastępczą w głównej mapie skrótów i wypełnij go, gdy zobaczysz rzeczywisty węzeł.

Aby go wydrukować, wykonaj proste przejście przez głębokość, najpierw przechodząc przez dane, śledząc poziom wcięcia po drodze. Możesz to ułatwić, przechowując pozycję „potomną” dla każdego wiersza i wypełniając ją podczas skanowania danych.

To, czy istnieje „lepszy” sposób przechowywania drzewa w bazie danych, zależy od tego, jak zamierzasz korzystać z danych. Widziałem systemy o znanej maksymalnej głębokości, które używały innej tabeli dla każdego poziomu w hierarchii. Ma to sens, jeśli poziomy w drzewie nie są przecież równoważne (kategorie najwyższego poziomu różnią się od liści).

Jeśli można utworzyć zagnieżdżone mapy skrótów lub tablice, mogę po prostu zejść od początku tabeli i dodać każdy element do zagnieżdżonej tablicy. Muszę prześledzić każdą linię do węzła głównego, aby dowiedzieć się, do którego poziomu w zagnieżdżonej tablicy należy wstawić. Mogę zastosować zapamiętywanie, aby nie musiałem od nowa szukać tego samego rodzica.

Edycja: Najpierw wczytałbym całą tabelę do tablicy, aby nie pytała DB wielokrotnie. Oczywiście nie będzie to praktyczne, jeśli twój stół jest bardzo duży.

Po zbudowaniu struktury muszę najpierw przejść przez nią głębokość i wydrukować HTML.

Nie ma lepszego fundamentalnego sposobu na przechowywanie tych informacji przy użyciu jednej tabeli (choć mogę się mylić;) i chciałbym znaleźć lepsze rozwiązanie). Jeśli jednak stworzysz schemat, w którym zostaną zastosowane dynamicznie tworzone tabele db, otworzysz zupełnie nowy świat, poświęcając się prostocie i ryzyku piekła SQL;).

Jeśli elementy są uporządkowane w drzewie, jak pokazano w przykładzie, możesz użyć czegoś takiego jak następujący przykład w języku 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)

Pozwala to zachować stos reprezentujący bieżącą pozycję w drzewie. Dla każdego elementu w tabeli wyskakuje elementy stosu (zamykając pasujące elementy div), dopóki nie znajdzie elementu nadrzędnego bieżącego elementu. Następnie wysyła początek tego węzła i wypycha go na stos.

Jeśli chcesz wyprowadzić drzewo za pomocą wcięcia zamiast elementów zagnieżdżonych, możesz po prostu pominąć instrukcje print, aby wydrukować div, i wydrukować liczbę spacji równą wielokrotności wielkości stosu przed każdym elementem. Na przykład w Pythonie:

print "  " * len(stack)

Można również łatwo użyć tej metody do zbudowania zestawu zagnieżdżonych list lub słowników.

Edycja: z twojego wyjaśnienia wynika, że ​​nazwy nie miały być ścieżkami do węzłów. To sugeruje alternatywne podejście:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

To buduje drzewo tablic krotek (!). idx [0] reprezentuje katalog główny drzewa. Każdy element w tablicy to 2-krotka składająca się z samego węzła i listy wszystkich jego elementów podrzędnych. Po zbudowaniu możesz zatrzymać idx [0] i odrzucić idx, chyba że chcesz uzyskać dostęp do węzłów według ich ID.

Aby rozszerzyć rozwiązanie SQL Billa, możesz zrobić to samo za pomocą płaskiej tablicy. Co więcej, jeśli wszystkie łańcuchy mają tę samą długość, a maksymalna liczba dzieci jest znana (powiedzmy w drzewie binarnym), możesz to zrobić za pomocą jednego łańcucha (tablica znaków). Jeśli masz dowolną liczbę dzieci, to trochę to komplikuje ... Musiałbym sprawdzić moje stare notatki, aby zobaczyć, co można zrobić.

Następnie, poświęcając trochę pamięci, szczególnie jeśli twoje drzewo jest rzadkie i / lub niezrównoważone, możesz, przy odrobinie indeksu, uzyskać dostęp do wszystkich ciągów losowo, przechowując swoje drzewo, szerokość najpierw w tablicy w ten sposób (dla pliku binarnego drzewo):

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

znasz swoją długość struny, znasz ją

Jestem teraz w pracy, więc nie mogę spędzać dużo czasu, ale z zainteresowaniem mogę pobrać trochę kodu, aby to zrobić.

Robimy to, aby przeszukiwać drzewa binarne zbudowane z kodonów DNA, proces zbudował drzewo, a następnie spłaszcziliśmy je, aby wyszukać wzorce tekstowe, a gdy je znajdziemy, choć matematyka indeksu (odwraca się od góry) odzyskujemy węzeł z powrotem ... bardzo szybkie i wydajne, twarde nasze drzewo rzadko miało puste węzły, ale mogliśmy przeszukać gigabajty danych w mgnieniu oka.

Pomyśl o użyciu narzędzi nosql, takich jak neo4j, do struktur hierarchicznych. np. aplikacja sieciowa, taka jak linkedin, korzysta z couchbase (inne rozwiązanie nosql)

Ale używaj nosql tylko do zapytań na poziomie danych, a nie do przechowywania / utrzymywania transakcji