将平台解析成树的最有效/优雅的方法是什么？-Java 学习之路

478

假设您有一个存储有序树层次结构的平面表：

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

这是一张图，我们有 [id] Name . 根节点0是虚构的 .

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

您将使用什么简约方法将其输出为HTML（或文本，就此而言）作为正确排序，正确缩进的树？

进一步假设你只有基本的数据结构（数组和散列图），没有带有父/子引用的花哨对象，没有ORM，没有框架，只有你的双手 . 该表表示为结果集，可以随机访问 .

伪代码或普通英语是可以的，这纯粹是一个概念性的问题 .

额外的问题：在RDBMS中存储这样的树结构是否有根本更好的方法？

EDITS AND ADDITIONS

回答一个评论者（Mark Bessey）的问题：根节点不是必需的，因为它永远不会被显示 . ParentId = 0是表达"these are top level"的约定 . Order列定义了如何对具有相同父节点的节点进行排序 .

我所谈到的“结果集”可以被描绘成一组哈希图（保留在该术语中） . 因为我的例子意味着已经存在 . 有些答案会加倍努力并首先构建它，但那没关系 .

树可以任意深 . 每个节点可以有N个子节点 . 不过，我并没有考虑到“数百万条目” .

不要错误地选择节点命名（'Node 1.1.1'）来依赖 . 节点同样可以称为“Frank”或“Bob”，不暗示命名结构，这只是为了使其可读 .

我已经发布了自己的解决方案，所以你们可以把它拉成碎片 .

14 回答

9
现在，MySQL 8.0即将发布，标准语法为all popular SQL databases will support recursive queries .
```
WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
```
我在2017年的演示文稿Recursive Query Throwdown中测试了MySQL 8.0中的递归查询 .

以下是我2008年的原始答案：

有几种方法可以在关系数据库中存储树形结构数据 . 您在示例中显示的内容使用两种方法：
- Adjacency List （"parent"专栏）和
- Path Enumeration （名称列中的虚线数字） .
另一个解决方案叫做 Nested Sets ，它也可以存储在同一个表中 . 阅读Joe Celko的“Trees and Hierarchies in SQL for Smarties”，了解有关这些设计的更多信息 .

我通常更喜欢名为 Closure Table （又名"Adjacency Relation"）的设计来存储树形结构数据 . 它需要另一个表，但是查询树很容易 .

我在我的演讲Models for Hierarchical Data with SQL and PHP和我的书SQL Antipatterns: Avoiding the Pitfalls of Database Programming中介绍了Closure Table .
```
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)
);
```
将所有路径存储在Closure Table中，其中存在从一个节点到另一个节点的直接祖先 . 为每个节点包含一行以引用自身 . 例如，使用您在问题中显示的数据集：
```
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);
```
现在你可以从节点1开始得到一棵树，如下所示：
```
SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
```
输出（在MySQL客户端中）如下所示：
```
+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+
```
换句话说，节点3和5被排除，因为它们是单独层次结构的一部分，而不是从节点1下降 .

回复：电子满意的关于直接孩子（或直系亲属）的评论 . 您可以向 ClosureTable 添加“ path_length ”列，以便更容易专门查询直接子项或父项（或任何其他距离） .
```
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);
```
然后，您可以在搜索中添加一个术语，用于查询给定节点的直接子节点 . 这些是 path_length 为1的后代 .
```
SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+
```
来自@ashraf的评论：“如何按名称排序整棵树？”

这是一个示例查询，用于返回作为节点1后代的所有节点，将它们连接到包含其他节点属性（如 name ）的FlatTable，并按名称排序 .
```
SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
```
来自@Nate的评论：
```
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+
```
用户今天建议编辑 . SO主持人批准了编辑，但我正在撤消它 .

编辑建议上面最后一个查询中的ORDER BY应该是 ORDER BY b.path_length, f.name ，大概是为了确保排序与层次结构匹配 . 但是这不起作用，因为它会在"Node 1.2"之后命令"Node 1.1.1" .

如果您希望排序以合理的方式匹配层次结构，那么这是可能的，但不是简单地按路径长度排序 . 例如，请参阅我对MySQL Closure Table hierarchical database - How to pull information out in the correct order的回答 .
回复于 2024-04-29T12:39:29+08:00
1
如果使用嵌套集（有时称为修改的预订树遍历），您可以使用单个查询以树顺序提取整个树结构或其中的任何子树，但代价是插入更昂贵，因为您需要管理通过树结构描述有序路径的列 .

对于django-mptt，我使用了这样的结构：
```
id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12
```
其中描述了一个看起来像这样的树（ id 表示每个项目）：
```
1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7
```
或者，作为嵌套集合图，使 lft 和 rght 值如何工作更加明显：
```
__________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|
```
如您所见，要以树的顺序获取给定节点的整个子树，您只需选择所有具有 lft 和 rght 的行 lft 和 rght 值之间的值 . 检索给定节点的祖先树也很简单 .

为方便起见， level 列有点非常规化，而 tree_id 列允许您为每个顶级节点重新启动 lft 和 rght 编号，这样可以减少受插入，移动和删除影响的列数，如 lft 当进行这些操作以创建或缩小间隙时，必须相应地调整和 rght 列 . 当我试图围绕每个操作所需的查询时，我做了一些development notes .

在实际处理这些数据以显示树的方面，我创建了一个tree_item_iterator实用程序函数，对于每个节点，它应该为您提供足够的信息来生成您想要的任何类型的显示 .

有关更多信息MPTT：
回复于 2024-04-29T12:39:29+08:00

从Oracle 9i开始，您可以使用CONNECT BY .

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

从SQL Server 2005开始，您可以使用递归公用表表达式（CTE） .

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

两者都将输出以下结果 .

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

回复于 2024-04-29T12:39:29+08:00

这是一个相当古老的问题，但由于它有很多观点，我认为值得提出一个替代方案，并且在我看来非常优雅的解决方案 .

要读取树结构，可以使用 recursive Common Table Expressions （CTE） . 它提供了一次获取整个树结构的可能性，具有关于节点级别，其父节点和父节点的子节点内的顺序的信息 .

让我告诉你这在PostgreSQL 9.1中是如何工作的 .

创建一个结构

CREATE TABLE tree (
    id int  NOT NULL,
    name varchar(32)  NOT NULL,
    parent_id int  NULL,
    node_order int  NOT NULL,
    CONSTRAINT tree_pk PRIMARY KEY (id),
    CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
      REFERENCES tree (id) NOT DEFERRABLE
);


insert into tree values
  (0, 'ROOT', NULL, 0),
  (1, 'Node 1', 0, 10),
  (2, 'Node 1.1', 1, 10),
  (3, 'Node 2', 0, 20),
  (4, 'Node 1.1.1', 2, 10),
  (5, 'Node 2.1', 3, 10),
  (6, 'Node 1.2', 1, 20);

写一个查询

WITH RECURSIVE 
tree_search (id, name, level, parent_id, node_order) AS (
  SELECT 
    id, 
    name,
    0,
    parent_id, 
    1 
  FROM tree
  WHERE parent_id is NULL

  UNION ALL 
  SELECT 
    t.id, 
    t.name,
    ts.level + 1, 
    ts.id, 
    t.node_order 
  FROM tree t, tree_search ts 
  WHERE t.parent_id = ts.id 
) 
SELECT * FROM tree_search 
WHERE level > 0 
ORDER BY level, parent_id, node_order;

结果如下：

id |    name    | level | parent_id | node_order 
----+------------+-------+-----------+------------
  1 | Node 1     |     1 |         0 |         10
  3 | Node 2     |     1 |         0 |         20
  2 | Node 1.1   |     2 |         1 |         10
  6 | Node 1.2   |     2 |         1 |         20
  5 | Node 2.1   |     2 |         3 |         10
  4 | Node 1.1.1 |     3 |         2 |         10
(6 rows)

树节点按深度级排序 . 在最终输出中，我们将在后续行中显示它们 .

对于每个级别，它们按父级中的parent_id和node_order排序 . 这告诉我们如何在输出中呈现它们 - 按此顺序将链接节点呈现给父节点 .

拥有这样的结构，在HTML中制作一个非常好的演示文稿并不困难 .

递归CTE可在 PostgreSQL, IBM DB2, MS SQL Server and Oracle 中找到 .

如果您想阅读有关递归SQL查询的更多信息，可以查看您喜欢的DBMS的文档，或阅读我的两篇文章，内容涉及此主题：

回复于 2024-04-29T12:39:29+08:00

比尔的答案非常好，这个答案增加了一些东西，这使我希望SO支持线程答案 .

无论如何，我想支持树结构和Order属性 . 我在每个节点中包含一个名为 leftSibling 的属性，它在原始问题中执行相同的操作 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 .

谢谢比尔，你的回答有助于入门！

回复于 2024-04-29T12:39:29+08:00

1
在给出选择的情况下，我为每个记录创建一个对象，其中每个对象都有一个 children 集合，并将它们全部存储在一个关联数组（/ hashtable）中，其中Id是关键字 . 并通过该系列闪电战，将孩子们加入相关的儿童田地 . Simple.

但是因为你通过限制使用一些好的OOP而没有乐趣，我可能会根据以下内容进行迭代：
```
function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)
```
编辑：这类似于其他几个条目，但我认为它是's slightly cleaner. One thing I' ll add：这是非常SQL密集型的 . 这很讨厌 . If you have the choice, go the OOP route.
回复于 2024-04-29T12:39:29+08:00

414

这是写得很快，既不漂亮也不高效（再加上autoboxes很多，在 int 和_692590之间进行转换很烦人！），但它确实有效 .

它可能违反了规则，因为我正在创建自己的对象，但是嘿，我这样做是为了转移实际工作:)

这也假设在开始构建节点之前，resultSet / table被完全读入某种结构，如果你有数十万行，这将不是最好的解决方案 .

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

回复于 2024-04-29T12:39:29+08:00

假设您知道根元素为零，这是输出到文本的伪代码：

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)

回复于 2024-04-29T12:39:29+08:00

0

您可以使用散列映射模拟任何其他数据结构，因此这不是一个可怕的限制 . 从顶部扫描到底部，您可以为数据库的每一行创建一个哈希映射，每个列都有一个条目 . 将每个哈希映射添加到“主”哈希映射，键入id . 如果任何节点具有您尚未看到的“父”，请在主哈希映射中为其创建占位符条目，并在看到实际节点时将其填入 .

要将其打印出来，请执行简单的深度优先传递数据，并沿途跟踪缩进级别 . 您可以通过为每行保留“子”条目并在扫描数据时填充它来使这更容易 .

至于是否有一种“更好”的方式将树存储在数据库中，这取决于您将如何使用数据 . 我已经看到了具有已知最大深度的系统，它为层次结构中的每个级别使用了不同的表 . 如果树中的级别毕竟不是完全相同的（顶级类别不同于），那么这很有意义树叶） .

回复于 2024-04-29T12:39:29+08:00

有很好的解决方案可以利用sql索引的内部btree表示 . 这是基于1998年左右的一些重大研究 .

这是一个示例表（在mysql中） .

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

树表示所需的唯一字段是：

tw：从左到右DFS预订单索引，其中root = 1 .
pa：对父节点的引用（使用tw），root为null .
sz：节点分支的大小包括自身 .
nc：用作语法糖 . 它是tw nc并代表节点的_t的两个"next child" .

这是一个示例24节点填充，按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 |
+-----+---------+----+------+------+------+

每个树结果都可以非递归地完成 . 例如，要在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 |
+-----+---------+----+------+------+------+

兄弟姐妹和孩子是微不足道的 - 只需使用tw字段排序 .

Descendants

例如，以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

当存在比插入或更新更多的读取时，此方法非常有用 .

因为树中节点的插入，移动或更新需要调整树，所以必须在开始操作之前锁定表 .

插入/删除成本很高，因为需要在插入点之后的所有节点上更新tw索引和sz（分支大小）值，并且分别针对所有祖先更新 .

分支移动涉及将分支的tw值移出范围，因此在移动分支时还必须禁用外键约束 . 移动分支需要四个查询：

将分支移出范围 .
缩小它留下的空隙 . （剩下的树现在已标准化） .
打开它会去的差距 .
将分支移动到新位置 .

Adjust Tree Queries

树中间隙的打开/关闭是创建/更新/删除方法使用的重要子功能，因此我将其包含在此处 .

我们需要两个参数 - 一个表示我们是否正在缩小规模或升级的标志，以及节点的tw索引 . 因此，例如tw = 18（其分支大小为5） . 让我们假设我们正在缩小规模（删除tw） - 这意味着我们在以下示例的更新中使用' - '而不是'' .

我们首先使用（略微改变的）祖先函数来更新sz值 .

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

然后我们需要为tw高于要移除的分支的那些调整tw .

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

然后我们需要为pa的tw高于要删除的分支的那些调整父级 .

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

回复于 2024-04-29T12:39:29+08:00

5

如果可以创建嵌套的哈希映射或数组，那么我可以从头开始向下移动表并将每个项添加到嵌套数组中 . 我必须跟踪每个行到根节点，以便知道要插入的嵌套数组中的哪个级别 . 我可以使用memoization，这样我就不需要一遍又一遍地查找同一个父母 .

编辑：我会先将整个表读入一个数组，因此不会重复查询数据库 . 当然，如果您的 table 非常大，这将不切实际 .

在构建结构之后，我必须首先遍历它并打印出HTML .

没有更好的基本方法来使用一个表来存储这些信息（虽然我可能是错的;），并且希望看到更好的解决方案） . 但是，如果您创建一个使用动态创建的数据库表的方案，那么您在牺牲简单性和SQL地狱风险的情况下开辟了一个全新的世界;） .

回复于 2024-04-29T12:39:29+08:00
1
如果元素按树顺序排列，如示例所示，则可以使用类似以下Python示例的内容：
```
delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)
```
这样做是维护一个表示树中当前位置的堆栈 . 对于表中的每个元素，它会弹出堆栈元素（关闭匹配的div），直到找到当前项的父元素 . 然后它输出该节点的开始并将其推送到堆栈 .

如果要使用缩进而不是嵌套元素输出树，可以简单地跳过print语句来打印div，并在每个项之前打印一些空格，这些空格等于堆栈大小的某个倍数 . 例如，在Python中：
```
print "  " * len(stack)
```
您还可以轻松地使用此方法构造一组嵌套列表或词典 .

编辑：我从您的澄清中看到，这些名称并非旨在成为节点路径 . 这表明了另一种方法：
```
idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))
```
这构造了一个元组数组树（！） . idx [0]表示树的根 . 数组中的每个元素都是一个2元组，由节点本身和所有子节点组成 . 一旦构造，您可以保持idx [0]并丢弃idx，除非您想通过其ID访问节点 .
回复于 2024-04-29T12:39:29+08:00
3
要扩展Bill的SQL解决方案，您基本上可以使用平面阵列执行相同的操作 . 更进一步，如果您的字符串都具有相同的长度并且您的最大子项数已知（例如在二叉树中），您可以使用单个字符串（字符）来完成数组） . 如果你有任意数量的孩子，这会使事情变得复杂......我将不得不检查我的旧笔记，看看能做些什么 .

然后，牺牲一点内存，特别是如果你的树稀疏和/或不平静，你可以通过一些索引数学，通过存储你的树，宽度优先在数组中随机访问所有字符串（对于二进制文件）树）：
```
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
```
你知道你的字符串长度吗？

我现在在工作，所以不能花太多时间在它上面，但有兴趣的话，我可以获取一些代码来做到这一点 .

我们用它来搜索由DNA密码子构成的二叉树，一个构建树的过程，然后我们将它展平以搜索文本模式，当找到时，虽然索引数学（从上面反转）我们得到节点...非常快速高效，坚韧我们的树很少有空节点，但我们可以快速搜索数十亿字节的数据 .
回复于 2024-04-29T12:39:29+08:00
53

考虑使用像neo4j这样的nosql工具来实现层次结构 . 例如，像Linkedin这样的网络应用程序使用couchbase（另一个nosql解决方案）

但是，仅将nosql用于数据集市级别查询，而不是存储/维护事务

回复于 2024-04-29T12:39:29+08:00

将平台解析成树的最有效/优雅的方法是什么？

14 回答

相关问题