Apa cara paling efisien / elegan untuk mengurai meja datar menjadi pohon?

Asumsikan Anda memiliki tabel datar yang menyimpan hierarki pohon yang dipesan:

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

Berikut diagram, di mana kita miliki [id] Name. Root node 0 bersifat fiksi.

                       [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

Pendekatan minimalis apa yang akan Anda gunakan untuk menampilkan itu ke HTML (atau teks, dalam hal ini) sebagai pohon dengan indentasi yang disusun dengan benar?

Asumsikan lebih lanjut Anda hanya memiliki struktur data dasar (array dan hashmaps), tidak ada objek mewah dengan referensi orang tua / anak, tidak ada ORM, tidak ada kerangka kerja, hanya dua tangan Anda. Tabel diwakili sebagai set hasil, yang dapat diakses secara acak.

Kode semu atau bahasa Inggris biasa tidak apa-apa, ini murni pertanyaan konseptual.

Pertanyaan bonus: Apakah ada cara yang secara fundamental lebih baik untuk menyimpan struktur pohon seperti ini di RDBMS?

EDIT DAN TAMBAHAN

Untuk menjawab pertanyaan salah satu komentator ( Mark Bessey ): Simpul root tidak diperlukan, karena tidak akan pernah ditampilkan. ParentId = 0 adalah konvensi untuk menyatakan "ini adalah level teratas". Kolom Pesanan menentukan bagaimana simpul dengan induk yang sama akan diurutkan.

"Set hasil" yang saya bicarakan dapat digambarkan sebagai array hashmaps (untuk tetap dalam terminologi itu). Untuk contoh saya seharusnya sudah ada di sana. Beberapa jawaban bekerja lebih keras dan membangunnya terlebih dahulu, tapi tidak apa-apa.

Pohonnya bisa sedalam mungkin. Setiap simpul dapat memiliki N anak. Namun, saya sebenarnya tidak memiliki pohon "jutaan entri".

Jangan salah pilih penamaan simpul ('Node 1.1.1') untuk sesuatu yang bisa diandalkan. Node dapat juga disebut 'Frank' atau 'Bob', tidak ada struktur penamaan yang tersirat, ini hanya untuk membuatnya dapat dibaca.

Saya telah memposting solusi saya sendiri sehingga kalian bisa menariknya berkeping-keping.

Sekarang MySQL 8.0 mendukung kueri rekursif , kita dapat mengatakan bahwa semua database SQL populer mendukung kueri rekursif dalam sintaksis standar.

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;

Saya menguji permintaan rekursif di MySQL 8.0 di presentasi saya Recursive Query Throwdown pada 2017.

Di bawah ini adalah jawaban asli saya dari 2008:

Ada beberapa cara untuk menyimpan data terstruktur pohon dalam database relasional. Apa yang Anda perlihatkan dalam contoh Anda menggunakan dua metode:

• Daftar Adjacency (kolom "induk") dan
• Enumerasi Jalur (angka-titik bertitik di kolom nama Anda).

Solusi lain disebut Nested Sets , dan dapat disimpan dalam tabel yang sama juga. Baca " Pohon dan Hirarki dalam SQL untuk Smarties " oleh Joe Celko untuk informasi lebih lanjut tentang desain ini.

Saya biasanya lebih suka desain yang disebut Tabel Penutupan (alias "Hubungan Adjacency") untuk menyimpan data terstruktur pohon. Membutuhkan tabel lain, tetapi kemudian permintaan pohon cukup mudah.

Saya membahas Tabel Penutupan dalam Model presentasi saya untuk Data Hirarki dengan SQL dan PHP dan dalam buku saya SQL Antipatterns: Menghindari Jebakan Pemrograman Basis Data .

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

Simpan semua jalur di Tabel Penutupan, di mana ada keturunan langsung dari satu simpul ke simpul lainnya. Sertakan baris untuk setiap node untuk referensi itu sendiri. Misalnya, menggunakan kumpulan data yang Anda tunjukkan dalam pertanyaan Anda:

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

Sekarang Anda bisa mendapatkan pohon mulai dari simpul 1 seperti ini:

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

Output (dalam klien MySQL) terlihat seperti berikut:

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

Dengan kata lain, simpul 3 dan 5 dikecualikan, karena mereka merupakan bagian dari hierarki yang terpisah, bukan turun dari simpul 1.

Re: komentar dari e-satis tentang anak langsung (atau orang tua langsung). Anda dapat menambahkan path_lengthkolom " " ke ClosureTableuntuk membuatnya lebih mudah untuk meminta secara khusus untuk anak atau orang tua langsung (atau jarak lainnya).

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

Kemudian Anda dapat menambahkan istilah dalam pencarian Anda untuk menanyakan langsung anak-anak dari simpul yang diberikan. Ini adalah keturunan yang 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 | 
+----+

Komentar ulang dari @ashraf: "Bagaimana kalau menyortir seluruh pohon [dengan nama]?"

Berikut ini contoh kueri untuk mengembalikan semua node yang merupakan turunan dari simpul 1, bergabung dengan mereka ke FlatTable yang berisi atribut simpul lainnya seperti name, dan urutkan berdasarkan namanya.

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

Komentar ulang dari @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         |
+------------+-------------+

Seorang pengguna menyarankan suntingan hari ini. SO moderator menyetujui hasil edit, tetapi saya membalikkannya.

Hasil edit menyarankan agar ORDER BY dalam kueri terakhir di atas seharusnya ORDER BY b.path_length, f.name, mungkin untuk memastikan pemesanan sesuai dengan hierarki. Tetapi ini tidak berhasil, karena akan memesan "Node 1.1.1" setelah "Node 1.2".

Jika Anda ingin pemesanan mencocokkan hierarki dengan cara yang masuk akal, itu mungkin, tetapi tidak hanya dengan memesan berdasarkan panjang jalur. Sebagai contoh, lihat jawaban saya ke database hierarkis Tabel Penutupan MySQL - Cara mengeluarkan informasi dalam urutan yang benar .

Jika Anda menggunakan kumpulan bersarang (kadang-kadang disebut sebagai Modifikasi Traversal Pohon Pra-pemesanan yang Dimodifikasi), Anda dapat mengekstraksi seluruh struktur pohon atau setiap subtree di dalamnya dalam urutan pohon dengan satu permintaan, dengan biaya memasukkan lebih mahal, karena Anda perlu mengelola kolom yang menggambarkan jalur berurutan melalui struktur pohon Anda.

Untuk django-mptt , saya menggunakan struktur seperti ini:

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

Yang menggambarkan pohon yang terlihat seperti ini (dengan idmewakili setiap item):

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

Atau, sebagai set diagram bersarang yang membuatnya lebih jelas bagaimana lftdan rghtnilai - nilai bekerja:

 __________________________________________________________________________
| Root 1 |
| ________________________________ ________________________________ |
| | Anak 1.1 | | Anak 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
| | ________________________________ | | ________________________________ | |
| __________________________________________________________________________ |

Seperti yang Anda lihat, untuk mendapatkan seluruh subtree untuk node yang diberikan, dalam urutan pohon, Anda cukup memilih semua baris yang memiliki lftdan rghtnilai - nilai antara lftdan rghtnilai - nilai. Ini juga mudah untuk mengambil pohon leluhur untuk simpul yang diberikan.

The levelkolom sedikit denormalisation untuk kenyamanan lebih dari apa pun dan tree_idkolom memungkinkan Anda untuk me-restart lftdan rghtpenomoran untuk setiap node tingkat atas, yang mengurangi jumlah kolom dipengaruhi oleh sisipan, bergerak dan penghapusan, sebagai lftdan rghtkolom harus disesuaikan sesuai ketika operasi ini dilakukan untuk membuat atau menutup celah. Saya membuat beberapa catatan pengembangan pada saat saya mencoba membungkus kepala saya di sekitar pertanyaan yang diperlukan untuk setiap operasi.

Dalam hal benar-benar bekerja dengan data ini untuk menampilkan pohon, saya membuat tree_item_iteratorfungsi utilitas yang, untuk setiap node, harus memberi Anda informasi yang cukup untuk menghasilkan tampilan apa pun yang Anda inginkan.

Info lebih lanjut tentang MPTT:

• Pohon dalam SQL
• Menyimpan Data Hirarki dalam Database
• Mengelola Data Hirarki di MySQL

Ini pertanyaan yang cukup lama, tetapi karena punya banyak pandangan saya pikir itu layak untuk menyajikan alternatif, dan menurut saya solusi yang sangat elegan.

Untuk membaca struktur pohon, Anda dapat menggunakan Common Table Expressions (CTE) rekursif . Ini memberikan kemungkinan untuk mengambil seluruh struktur pohon sekaligus, memiliki informasi tentang tingkat simpul, simpul induknya dan urutan dalam anak-anak dari simpul induk.

Biarkan saya menunjukkan kepada Anda bagaimana ini akan bekerja di PostgreSQL 9.1.

1. Buat 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. Tulis kueri

   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;

   Inilah hasilnya:

    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)

   Simpul pohon disusun berdasarkan tingkat kedalaman. Pada hasil akhir, kami akan mempresentasikannya di baris berikutnya.

   Untuk setiap level, mereka diurutkan oleh parent_id dan node_order di dalam parent. Ini memberitahu kita bagaimana menyajikannya dalam simpul tautan keluaran ke induk dalam urutan ini.

   Memiliki struktur seperti itu tidak akan sulit untuk membuat presentasi yang sangat bagus dalam HTML.

   CTE rekursif tersedia dalam PostgreSQL, IBM DB2, MS SQL Server dan Oracle .

   Jika Anda ingin membaca lebih lanjut tentang query SQL rekursif, Anda dapat memeriksa dokumentasi DBMS favorit Anda atau membaca dua artikel saya yang membahas topik ini:

   • Do It In SQL: Tree Traversal Rekursif
   • Mengenal kekuatan query SQL rekursif

Pada Oracle 9i, Anda dapat menggunakan 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)

Pada SQL Server 2005, Anda dapat menggunakan ekspresi tabel rekursif umum (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]

Keduanya akan menampilkan hasil berikut.

Nama
'Node 1'
'Node 1.1'
'Node 1.1.1'
'Node 1.2'
'Node 2'
'Node 2.1'

Jawaban Bill sangat baik sekali, jawaban ini menambahkan beberapa hal yang membuat saya berharap SO didukung jawaban berulir.

Pokoknya saya ingin mendukung struktur pohon dan properti Order. Saya menyertakan satu properti di setiap Node yang dipanggil leftSiblingyang melakukan hal yang sama Orderdimaksudkan untuk dilakukan dalam pertanyaan asli (mempertahankan urutan kiri-ke-kanan).

mysql> desc node;
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| Bidang | Ketik | Null | Kunci | Default | Ekstra |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| id | int (11) | TIDAK | PRI | NULL | auto_increment |
| nama | varchar (255) | YA | | NULL | |
| leftSibling | int (11) | TIDAK | | 0 | |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
3 baris dalam set (0,00 dtk)

mysql> desc adjacencies;
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| Bidang | Ketik | Null | Kunci | Default | Ekstra |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| relationId | int (11) | TIDAK | PRI | NULL | auto_increment |
| induk | int (11) | TIDAK | | NULL | |
| anak | int (11) | TIDAK | | NULL | |
| pathLen | int (11) | TIDAK | | NULL | |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
4 baris dalam set (0,00 dtk)

Lebih detail dan kode SQL di blog saya .

Terima kasih Bill, jawaban Anda sangat membantu dalam memulai!

Kalau diberi pilihan, saya akan menggunakan benda. Saya akan membuat objek untuk setiap catatan di mana setiap objek memiliki childrenkoleksi dan menyimpannya semua dalam array assoc (/ hashtable) di mana ID adalah kuncinya. Dan kilat melalui koleksi sekali, menambahkan anak-anak ke bidang anak yang relevan. Sederhana.

Tetapi karena Anda tidak bersenang-senang dengan membatasi penggunaan beberapa OOP yang baik, saya mungkin akan beralih berdasarkan:

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

PrintLine(0, 0)

Sunting: ini mirip dengan beberapa entri lain, tapi saya pikir ini sedikit lebih bersih. Satu hal yang akan saya tambahkan: ini sangat intensif SQL. Ini jahat . Jika Anda punya pilihan, buka rute OOP.

Ini ditulis dengan cepat, dan tidak cantik juga tidak efisien (ditambah lagi autobox banyak, mengubah antara intdan Integermenjengkelkan!), Tetapi bekerja.

Mungkin melanggar aturan karena saya membuat objek sendiri tapi hei saya melakukan ini sebagai pengalihan dari kerja nyata :)

Ini juga mengasumsikan bahwa resultSet / tabel sepenuhnya dibaca ke dalam semacam struktur sebelum Anda mulai membangun Nodes, yang tidak akan menjadi solusi terbaik jika Anda memiliki ratusan ribu baris.

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

Ada solusi yang sangat baik yang mengeksploitasi representasi btree internal indeks sql. Ini didasarkan pada beberapa penelitian hebat yang dilakukan sekitar tahun 1998.

Berikut ini adalah contoh tabel (dalam 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
)

Satu-satunya bidang yang diperlukan untuk representasi pohon adalah:

• tw: Indeks Pre-order DFS Kiri ke Kanan, di mana root = 1.
• pa: Referensi (menggunakan tw) ke node induk, root memiliki null.
• sz: Ukuran cabang simpul termasuk dirinya sendiri.
• nc: digunakan sebagai gula sintaksis. itu adalah tw + nc dan mewakili tw dari "anak berikutnya" dari node.

Berikut adalah contoh populasi 24 simpul, yang dipesan oleh 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 |
+-----+---------+----+------+------+------+

Setiap hasil pohon dapat dilakukan secara non-rekursif. Misalnya, untuk mendapatkan daftar leluhur simpul di tw = '22 '

Leluhur

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

Saudara kandung dan anak-anak adalah sepele - cukup gunakan bidang pemesanan pa oleh tw.

Keturunan

Misalnya set (cabang) dari node yang di-root pada 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 |
+-----+---------+----+------+------+------+

catatan tambahan

Metodologi ini sangat berguna ketika ada jumlah pembacaan yang jauh lebih besar daripada sisipan atau pembaruan.

Karena penyisipan, gerakan, atau pemutakhiran suatu simpul dalam pohon mengharuskan pohon untuk disesuaikan, maka perlu untuk mengunci tabel sebelum memulai dengan tindakan.

Biaya penyisipan / penghapusan tinggi karena nilai indeks tw dan sz (ukuran cabang) perlu diperbarui pada semua node setelah titik penyisipan, dan untuk semua leluhur masing-masing.

Pemindahan cabang melibatkan pemindahan nilai tw dari cabang di luar jangkauan, jadi penting juga untuk menonaktifkan batasan kunci asing saat memindahkan cabang. Ada, pada dasarnya empat permintaan yang diperlukan untuk memindahkan cabang:

• Pindahkan cabang keluar dari jangkauan.
• Tutup celah yang tersisa. (pohon yang tersisa sekarang dinormalisasi).
• Buka celah ke mana ia akan pergi.
• Pindahkan cabang ke posisi baru itu.

Sesuaikan Kueri Pohon

Pembukaan / penutupan celah dalam struktur pohon adalah sub-fungsi penting yang digunakan dengan membuat / memperbarui / menghapus metode, jadi saya memasukkannya di sini.

Kita membutuhkan dua parameter - sebuah flag yang menunjukkan apakah kita melakukan perampingan atau upsizing, dan indeks tw node. Jadi, misalnya tw = 18 (yang memiliki ukuran cabang 5). Mari kita asumsikan bahwa kita melakukan perampingan (menghapus tw) - ini berarti bahwa kita menggunakan '-' alih-alih '+' dalam pembaruan contoh berikut.

Kami pertama-tama menggunakan fungsi leluhur (sedikit diubah) untuk memperbarui nilai 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));

Maka kita perlu menyesuaikan tw untuk mereka yang tw lebih tinggi dari cabang yang akan dihapus.

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;

Maka kita perlu menyesuaikan induk untuk mereka yang tw pa lebih tinggi dari cabang yang akan dihapus.

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;

Dengan asumsi Anda tahu bahwa elemen root adalah nol, inilah pseudocode untuk menghasilkan teks:

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)

Anda dapat meniru struktur data lainnya dengan hashmap, jadi itu bukan batasan yang mengerikan. Memindai dari atas ke bawah, Anda membuat peta hash untuk setiap baris database, dengan entri untuk setiap kolom. Tambahkan masing-masing hashmaps ini ke hashmap "master", dengan kunci id. Jika ada simpul yang memiliki "induk" yang belum Anda lihat, buat entri placeholder untuknya di master hashmap, dan isi ketika Anda melihat simpul yang sebenarnya.

Untuk mencetaknya, lakukan pass-first sederhana pertama melalui data, melacak tingkat indent sepanjang jalan. Anda dapat membuatnya lebih mudah dengan menyimpan entri "anak-anak" untuk setiap baris, dan mengisinya saat Anda memindai data.

Adapun apakah ada cara "lebih baik" untuk menyimpan pohon dalam database, itu tergantung pada bagaimana Anda akan menggunakan data. Saya telah melihat sistem yang memiliki kedalaman maksimum yang diketahui yang menggunakan tabel berbeda untuk setiap level dalam hierarki. Itu masuk akal jika level di pohon tidak cukup setara setelah semua (kategori tingkat atas berbeda dari daun).

Jika peta hash bersarang atau array dapat dibuat, maka saya bisa langsung turun tabel dari awal dan menambahkan setiap item ke array bersarang. Saya harus melacak setiap baris ke simpul akar untuk mengetahui level mana dalam array bersarang untuk dimasukkan. Saya dapat menggunakan memoisasi sehingga saya tidak perlu mencari orang tua yang sama berulang kali.

Sunting: Saya akan membaca seluruh tabel menjadi array terlebih dahulu, sehingga tidak akan menanyakan DB berulang kali. Tentu saja ini tidak akan praktis jika meja Anda sangat besar.

Setelah struktur dibangun, saya harus melakukan penelusuran mendalam terlebih dahulu dan mencetak HTML.

Tidak ada cara mendasar yang lebih baik untuk menyimpan informasi ini menggunakan satu tabel (saya bisa saja salah;), dan akan senang melihat solusi yang lebih baik). Namun, jika Anda membuat skema untuk menggunakan tabel db yang dibuat secara dinamis, maka Anda membuka dunia baru dengan mengorbankan kesederhanaan, dan risiko SQL neraka;).

Jika elemen berada dalam susunan pohon, seperti yang ditunjukkan pada contoh Anda, Anda bisa menggunakan sesuatu seperti contoh Python berikut:

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)

Apa yang dilakukan adalah mempertahankan tumpukan yang mewakili posisi saat ini di pohon. Untuk setiap elemen dalam tabel, ini akan memunculkan elemen stack (menutup div yang cocok) sampai menemukan induk dari item saat ini. Kemudian output awal simpul itu dan mendorongnya ke stack.

Jika Anda ingin menampilkan pohon menggunakan elemen indentasi daripada elemen bersarang, Anda bisa melewatkan pernyataan cetak untuk mencetak div, dan mencetak sejumlah ruang yang sama dengan beberapa kelipatan ukuran tumpukan sebelum setiap item. Misalnya, dalam Python:

print "  " * len(stack)

Anda juga dapat dengan mudah menggunakan metode ini untuk membangun satu set daftar atau kamus bersarang.

Sunting: Saya melihat dari klarifikasi Anda bahwa nama-nama itu tidak dimaksudkan sebagai jalur simpul. Itu menunjukkan pendekatan alternatif:

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

Ini membangun pohon susunan tupel (!). idx [0] mewakili akar pohon. Setiap elemen dalam array adalah 2-tuple yang terdiri dari node itu sendiri dan daftar semua anak-anaknya. Setelah dibuat, Anda dapat mempertahankan idx [0] dan membuang idx, kecuali jika Anda ingin mengakses node dengan ID mereka.

Untuk Memperpanjang solusi SQL Bill Anda pada dasarnya dapat melakukan hal yang sama menggunakan array datar. Lebih jauh lagi jika semua string Anda memiliki panjang yang sama dan jumlah maksimum anak Anda diketahui (katakanlah dalam pohon biner), Anda dapat melakukannya menggunakan string tunggal (array karakter). Jika Anda memiliki jumlah anak yang sewenang-wenang, ini akan sedikit mempersulit ... Saya harus memeriksa catatan lama saya untuk melihat apa yang dapat dilakukan.

Kemudian, dengan mengorbankan sedikit memori, terutama jika pohon Anda jarang dan / atau tidak dikunci, Anda dapat, dengan sedikit indeks matematika, mengakses semua string secara acak dengan menyimpan pohon Anda, lebar pertama dalam array seperti itu (untuk biner pohon):

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

Anda tahu panjang tali Anda, Anda tahu itu

Saya sedang bekerja sekarang jadi tidak bisa menghabiskan banyak waktu untuk itu, tetapi dengan minat saya dapat mengambil sedikit kode untuk melakukan ini.

Kami menggunakannya untuk mencari di pohon biner yang terbuat dari kodon DNA, sebuah proses membangun pohon, kemudian kami meratakannya untuk mencari pola teks dan ketika ditemukan, meskipun indeks matematika (berbalik dari atas) kami mendapatkan simpul kembali ... sangat cepat dan efisien, tangguh pohon kami jarang memiliki node kosong, tetapi kami dapat melihat gigabytes data dalam sekejap.

Pikirkan tentang penggunaan alat nosql seperti neo4j untuk struktur hierarki. mis. aplikasi jaringan seperti linkedin menggunakan couchbase (solusi nosql lain)

Tetapi gunakan nosql hanya untuk kueri level data-mart dan bukan untuk menyimpan / memelihara transaksi