Cách hiệu quả / thanh lịch nhất để phân tích một bàn phẳng thành một cái cây là gì?

531
Tomalak 2008-10-11 06:47.

Giả sử bạn có một bảng phẳng lưu trữ hệ thống phân cấp cây được sắp xếp:

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

Đây là một sơ đồ, nơi chúng tôi có [id] Name. Nút gốc 0 là hư cấu.

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

Bạn sẽ sử dụng cách tiếp cận tối giản nào để xuất dữ liệu đó sang HTML (hoặc văn bản, đối với vấn đề đó) dưới dạng một cây có thứ tự chính xác, được thụt lề chính xác?

Giả sử xa hơn, bạn chỉ có cấu trúc dữ liệu cơ bản (mảng và bản đồ băm), không có đối tượng ưa thích với tham chiếu cha / con, không có ORM, không có khuôn khổ, chỉ cần hai tay của bạn. Bảng được biểu diễn dưới dạng tập kết quả, có thể được truy cập ngẫu nhiên.

Mã giả hoặc tiếng Anh đơn giản là được, đây hoàn toàn là một câu hỏi đặc biệt.

Câu hỏi bổ sung: Có cách nào tốt hơn về cơ bản để lưu trữ cấu trúc cây như thế này trong RDBMS không?


CHỈNH SỬA VÀ BỔ SUNG

Để trả lời câu hỏi của một người bình luận ( Mark Bessey ): Một nút gốc là không cần thiết, bởi vì nó sẽ không bao giờ được hiển thị. ParentId = 0 là quy ước để thể hiện "đây là cấp cao nhất". Cột Thứ tự xác định cách sắp xếp các nút có cùng nguồn gốc.

"Tập hợp kết quả" mà tôi nói đến có thể được hình dung như một mảng các bản đồ băm (để ở trong thuật ngữ đó). Ví dụ của tôi có nghĩa là đã có ở đó. Một số câu trả lời đi xa hơn và xây dựng nó trước, nhưng điều đó không sao.

Cây có thể sâu tùy ý. Mỗi nút có thể có N nút con. Mặc dù vậy, tôi không thực sự có "hàng triệu mục nhập" trong đầu.

Đừng nhầm tưởng lựa chọn đặt tên nút của tôi ('Node 1.1.1') cho thứ gì đó để dựa vào. Các nút cũng có thể được gọi là 'Frank' hoặc 'Bob', không có cấu trúc đặt tên nào được ngụ ý, điều này chỉ là để làm cho nó có thể đọc được.

Tôi đã đăng giải pháp của riêng tôi để các bạn có thể kéo nó ra từng mảnh.

14 answers

464
Bill Karwin 2008-10-11 07:58.

Bây giờ MySQL 8.0 hỗ trợ truy vấn đệ quy , chúng ta có thể nói rằng tất cả các cơ sở dữ liệu SQL phổ biến đều hỗ trợ truy vấn đệ quy theo cú pháp chuẩn.

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;

Tôi đã thử nghiệm các truy vấn đệ quy trong MySQL 8.0 trong bản trình bày của tôi Truy vấn đệ quy Throwdown vào năm 2017.

Dưới đây là câu trả lời ban đầu của tôi từ năm 2008:


Có một số cách để lưu trữ dữ liệu có cấu trúc cây trong cơ sở dữ liệu quan hệ. Những gì bạn hiển thị trong ví dụ của mình sử dụng hai phương pháp:

  • Danh sách gần kề (cột "gốc") và
  • Liệt kê Đường dẫn (các số có dấu chấm trong cột tên của bạn).

Một giải pháp khác được gọi là Bộ lồng nhau và nó cũng có thể được lưu trữ trong cùng một bảng. Đọc " Trees and Hierarchies in SQL for Smarties " của Joe Celko để biết thêm thông tin về những thiết kế này.

Tôi thường thích thiết kế có tên là Bảng đóng (hay còn gọi là "Quan hệ gần kề") để lưu trữ dữ liệu có cấu trúc dạng cây. Nó yêu cầu một bảng khác, nhưng sau đó việc truy vấn cây khá dễ dàng.

Tôi đề cập đến Bảng đóng trong bản trình bày của tôi Mô hình cho dữ liệu phân cấp với SQL và PHP và trong cuốn sách Phản vật chất SQL: Tránh cạm bẫy của lập trình cơ sở dữ liệu .

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

Lưu trữ tất cả các đường dẫn trong Bảng đóng cửa, nơi có tổ tiên trực tiếp từ nút này sang nút khác. Bao gồm một hàng để mỗi nút tự tham chiếu. Ví dụ: sử dụng tập dữ liệu bạn đã hiển thị trong câu hỏi của mình:

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

Bây giờ bạn có thể lấy một cây bắt đầu từ nút 1 như sau:

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

Đầu ra (trong MySQL client) trông giống như sau:

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

Nói cách khác, các nút 3 và 5 bị loại trừ, vì chúng là một phần của hệ thống phân cấp riêng biệt, không giảm dần từ nút 1.


Re: nhận xét từ e-thoả mãn về trẻ em trực tiếp (hoặc cha mẹ trực tiếp). Bạn có thể thêm path_lengthcột "" vào ClosureTableđể dễ dàng hơn trong việc truy vấn cụ thể cho con hoặc cha mẹ ngay lập tức (hoặc bất kỳ khoảng cách nào khác).

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

Sau đó, bạn có thể thêm một cụm từ trong tìm kiếm của mình để truy vấn các nút con trực tiếp của một nút nhất định. Đây là những hậu duệ của họ path_lengthlà 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 | 
+----+

Nhận xét lại từ @ashraf: "Làm thế nào về việc phân loại toàn bộ cây [theo tên]?"

Đây là một truy vấn ví dụ để trả về tất cả các nút là con của nút 1, nối chúng vào FlatTable có chứa các thuộc tính nút khác, chẳng hạn như namevà sắp xếp theo tên.

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

Nhận xét lại từ @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         |
+------------+-------------+

Một người dùng đã đề xuất một chỉnh sửa ngày hôm nay. SO người kiểm duyệt đã chấp thuận bản chỉnh sửa, nhưng tôi đang đảo ngược nó.

Chỉnh sửa đề xuất rằng ORDER BY trong truy vấn cuối cùng ở trên ORDER BY b.path_length, f.name, có lẽ là để đảm bảo rằng thứ tự phù hợp với hệ thống phân cấp. Nhưng điều này không hoạt động, vì nó sẽ đặt "Node 1.1.1" sau "Node 1.2".

Nếu bạn muốn thứ tự khớp với hệ thống phân cấp theo cách hợp lý, điều đó là có thể, nhưng không chỉ đơn giản là sắp xếp theo độ dài đường dẫn. Ví dụ: hãy xem câu trả lời của tôi cho cơ sở dữ liệu phân cấp MySQL Closure Table - Cách lấy thông tin ra theo đúng thứ tự .

58
Jonny Buchanan 2008-10-12 02:31.

Nếu bạn sử dụng các tập hợp lồng nhau (đôi khi được gọi là Truyền tải cây đặt trước đã sửa đổi), bạn có thể trích xuất toàn bộ cấu trúc cây hoặc bất kỳ cây con nào trong nó theo thứ tự cây bằng một truy vấn duy nhất, với chi phí chèn đắt hơn, vì bạn cần quản lý các cột mô tả một đường dẫn theo thứ tự thông qua cấu trúc cây của bạn.

Đối với django-mptt , tôi đã sử dụng cấu trúc như sau:

id parent_id tree_id level lft rght
- --------- ------- ----- --- ----
 1 rỗng 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

Mô tả một cái cây trông như thế này (với idđại diện cho từng mục):

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

Hoặc, dưới dạng một sơ đồ tập hợp lồng nhau giúp rõ ràng hơn về cách hoạt động của các giá trị lftrght:

 __________________________________________________________________________
| Gốc 1 |
| ________________________________ ________________________________ |
| | Con 1.1 | | Con 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
| | ________________________________ | | ________________________________ | |
| __________________________________________________________________________ |

Như bạn có thể thấy, để lấy toàn bộ cây con cho một nút nhất định, theo thứ tự cây, bạn chỉ cần chọn tất cả các hàng có lftrghtgiá trị giữa nó lftrghtgiá trị. Cũng đơn giản để lấy cây tổ tiên cho một nút nhất định.

Các levelcột là một chút của denormalisation để thuận tiện hơn bất cứ điều gì và tree_idcột cho phép bạn khởi động lại lftrghtđánh số cho mỗi nút cấp cao nhất, làm giảm số lượng các cột bị ảnh hưởng bởi chèn, di chuyển và xóa bỏ, như lftrghtcột phải được điều chỉnh cho phù hợp khi các hoạt động này diễn ra nhằm tạo ra hoặc thu hẹp khoảng cách. Tôi đã thực hiện một số ghi chú phát triển vào thời điểm tôi đang cố gắng xoay quanh các truy vấn cần thiết cho mỗi hoạt động.

Về việc thực sự làm việc với dữ liệu này để hiển thị một cây, tôi đã tạo một tree_item_iteratorhàm tiện ích, cho mỗi nút, sẽ cung cấp cho bạn đầy đủ thông tin để tạo bất kỳ loại hiển thị nào bạn muốn.

More info about MPTT:

  • Trees in SQL
  • Storing Hierarchical Data in a Database
  • Managing Hierarchical Data in MySQL
22
Michał Kołodziejski 2014-03-14 01:19.

It's a quite old question, but as it's got many views I think it's worth to present an alternative, and in my opinion very elegant, solution.

In order to read a tree structure you can use recursive Common Table Expressions (CTEs). It gives a possibility to fetch whole tree structure at once, have the information about the level of the node, its parent node and order within children of the parent node.

Let me show you how this would work in PostgreSQL 9.1.

  1. Create a structure

    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. Write a query

    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;
    

    Here are the results:

     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)
    

    The tree nodes are ordered by a level of depth. In the final output we would present them in the subsequent lines.

    For each level, they are ordered by parent_id and node_order within the parent. This tells us how to present them in the output - link node to the parent in this order.

    Having such a structure it wouldn't be difficult to make a really nice presentation in HTML.

    Recursive CTEs are available in PostgreSQL, IBM DB2, MS SQL Server and Oracle.

    If you'd like to read more on recursive SQL queries, you can either check the documentation of your favourite DBMS or read my two articles covering this topic:

    • Do It In SQL: Recursive Tree Traversal
    • Get to know the power of SQL recursive queries
18
Eric Weilnau 2008-10-11 10:06.

As of Oracle 9i, you can use 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)

As of SQL Server 2005, you can use a recursive common table expression (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]

Both will output the following results.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'
9
bobobobo 2010-12-22 18:31.

Bill's answer is pretty gosh-darned good, this answer adds some things to it which makes me wish SO supported threaded answers.

Anyway I wanted to support the tree structure and the Order property. I included a single property in each Node called leftSibling that does the same thing Order is meant to do in the original question (maintain left-to-right order).

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)

More detail and SQL code on my blog.

Thanks Bill your answer was helpful in getting started!

7
Oli 2008-10-11 07:36.

Well given the choice, I'd be using objects. I'd create an object for each record where each object has a children collection and store them all in an assoc array (/hashtable) where the Id is the key. And blitz through the collection once, adding the children to the relevant children fields. Simple.

But because you're being no fun by restricting use of some good OOP, I'd probably iterate based on:

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

PrintLine(0, 0)

Edit: this is similar to a couple of other entries, but I think it's slightly cleaner. One thing I'll add: this is extremely SQL-intensive. It's nasty. If you have the choice, go the OOP route.

5
matt b 2008-10-11 08:25.

This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.

It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)

This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.

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;
    }
}
5
Konchog 2017-03-14 22:43.

There are really good solutions which exploit the internal btree representation of sql indices. This is based on some great research done back around 1998.

Here is an example table (in mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

The only fields necessary for the tree representation are:

  • tw: The Left to Right DFS Pre-order index, where root = 1.
  • pa: The reference (using tw) to the parent node, root has null.
  • sz: The size of the node's branch including itself.
  • nc: is used as syntactic sugar. it is tw+nc and represents the tw of the node's "next child".

Here is an example 24 node population, ordered by 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 |
+-----+---------+----+------+------+------+

Every tree result can be done non-recursively. For instance, to get a list of ancestors of node at tw='22'

Ancestors

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

Siblings and children are trivial - just use pa field ordering by tw.

Descendants

For example the set (branch) of nodes that are rooted at 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 |
+-----+---------+----+------+------+------+

Additional Notes

This methodology is extremely useful for when there are a far greater number of reads than there are inserts or updates.

Because the insertion, movement, or updating of a node in the tree requires the tree to be adjusted, it is necessary to lock the table before commencing with the action.

The insertion/deletion cost is high because the tw index and sz (branch size) values will need to be updated on all the nodes after the insertion point, and for all ancestors respectively.

Branch moving involves moving the tw value of the branch out of range, so it is also necessary to disable foreign key constraints when moving a branch. There are, essentially four queries required to move a branch:

  • Move the branch out of range.
  • Close the gap that it left. (the remaining tree is now normalised).
  • Open the gap where it will go to.
  • Move the branch into it's new position.

Adjust Tree Queries

The opening/closing of gaps in the tree is an important sub-function used by create/update/delete methods, so I include it here.

We need two parameters - a flag representing whether or not we are downsizing or upsizing, and the node's tw index. So, for example tw=18 (which has a branch size of 5). Let's assume that we are downsizing (removing tw) - this means that we are using '-' instead of '+' in the updates of the following example.

We first use a (slightly altered) ancestor function to update the sz value.

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

Then we need to adjust the tw for those whose tw is higher than the branch to be removed.

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;

Then we need to adjust the parent for those whose pa's tw is higher than the branch to be removed.

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;
3
wcm 2008-10-11 06:59.

Assuming that you know that the root elements are zero, here's the pseudocode to output to text:

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)
3
Mark Bessey 2008-10-11 07:24.

You can emulate any other data structure with a hashmap, so that's not a terrible limitation. Scanning from the top to the bottom, you create a hashmap for each row of the database, with an entry for each column. Add each of these hashmaps to a "master" hashmap, keyed on the id. If any node has a "parent" that you haven't seen yet, create an placeholder entry for it in the master hashmap, and fill it in when you see the actual node.

To print it out, do a simple depth-first pass through the data, keeping track of indent level along the way. You can make this easier by keeping a "children" entry for each row, and populating it as you scan the data.

As for whether there's a "better" way to store a tree in a database, that depends on how you're going to use the data. I've seen systems that had a known maximum depth that used a different table for each level in the hierarchy. That makes a lot of sense if the levels in the tree aren't quite equivalent after all (top level categories being different than the leaves).

1
tchen 2008-10-11 07:02.

If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.

Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.

After the structure is built, I must do a depth first traverse through it and print out the HTML.

There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).

1
Nick Johnson 2008-10-11 11:45.

If elements are in tree order, as shown in your example, you can use something like the following Python example:

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)

What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.

If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:

print "  " * len(stack)

You could also easily use this method to construct a set of nested lists or dictionaries.

Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:

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

This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.

1
Newtopian 2008-10-11 08:42.

To Extend Bill's SQL solution you can basically do the same using a flat array. Further more if your strings all have the same lenght and your maximum number of children are known (say in a binary tree) you can do it using a single string (character array). If you have arbitrary number of children this complicates things a bit... I would have to check my old notes to see what can be done.

Then, sacrificing a bit of memory, especially if your tree is sparse and/or unballanced, you can, with a bit of index math, access all the strings randomly by storing your tree, width first in the array like so (for a binary tree):

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

yo know your string length, you know it

I'm at work now so cannot spend much time on it but with interest I can fetch a bit of code to do this.

We use to do it to search in binary trees made of DNA codons, a process built the tree, then we flattened it to search text patterns and when found, though index math (revers from above) we get the node back... very fast and efficient, tough our tree rarely had empty nodes, but we could searh gigabytes of data in a jiffy.

0
sreenivasulu kandakuru 2012-11-27 05:49.

Think about using nosql tools like neo4j for hierarchial structures. e.g a networked application like linkedin uses couchbase (another nosql solution)

But use nosql only for data-mart level queries and not to store / maintain transactions

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Trong Saturday Night Live, The Bachelor is Bland và Tina Fey trở lại với vai 'Crazy' Sarah Palin

Trong Saturday Night Live, The Bachelor is Bland và Tina Fey trở lại với vai 'Crazy' Sarah Palin

Sau khi Sarah Palin tán thành Donald Trump vào đầu tuần này, gần như không thể tránh khỏi việc Tina Fey sẽ trở lại Saturday Night Live để thăm lại ấn tượng Palin cổ điển của cô. Và Fey chắc chắn đã không làm thất vọng, cô ấy đã đưa ra một lời khen ngợi không hề nhẹ về bài phát biểu chứng thực Iowa quanh co và khó hiểu của Palin trong khi Trump của Darrell Hammond đưa ra bình luận xuyên suốt.

Đây có phải là sự khởi đầu cho sự kết thúc của việc giam giữ Brittney Griner?

Đây có phải là sự khởi đầu cho sự kết thúc của việc giam giữ Brittney Griner?

Brittney Griner (r.) Ngay từ đầu, thân phận của Brittney Griner đã là tình huống con tin Mỹ độc nhất trong lịch sử hiện đại.

Tom Brady là bộ tứ vệ đầu tiên cuối cùng có thể giúp Julio Jones có hơn 10 lần chạm bóng trong một mùa giải

Tom Brady là bộ tứ vệ đầu tiên cuối cùng có thể giúp Julio Jones có hơn 10 lần chạm bóng trong một mùa giải

Chúng ta có thể thấy nhiều hơn nữa về một Julio Jones khỏe mạnh trong khu vực cuối năm nay. John Parker Wilson, Greg McElroy, A.

Đó phải là Đức

Đó phải là Đức

Đối với đội tuyển Anh, không có kẻ thủ ác nào lớn hơn Hầu hết các cổ động viên Anh, nếu không muốn nói là tất cả, hẳn sẽ phải gật gù khi tiếng còi mãn cuộc của trận bán kết lượt về W Euro 2022 vang lên. Bởi vì nó báo hiệu rằng Đức sẽ chờ đợi ở Wembley trong trận chung kết với Anh và là điều duy nhất giữa Anh và chiếc cúp lớn đầu tiên của đội tuyển nữ.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language