什么是最有效率的/优雅的方式来parsing一个平坦的表格成一棵树?

假设您有一个存储有序树形层次的平坦表格:

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是虚构的。

                        [ROOT]
                           / \ 
               [1]节点1 [3]节点2
               / \ \
     [2]节点1.1 [6]节点1.2 [5]节点2.1
           /          
  [4]节点1.1.1

你将使用什么简约的方法将其输出为HTML(或文本)作为正确sorting,正确缩进的树?

进一步假设你只有基本的数据结构(数组和hashmaps),没有父母/孩子引用的奇特对象,没有ORM,没有框架,只有你的两只手。 该表格表示为一个结果集,可以随机访问。

伪代码或简单的英文是好的,这纯粹是一个概念性的问题。

奖金问题:在RDBMS中存储这样一个树结构是否有一个更好的方法?


编辑和附加

回答一个评论者的问题( 马克·贝西的问题):根节点不是必须的,因为它永远不会被显示出来。 ParentId = 0是expression“这些是顶级”的惯例。 “订单”列定义了如何对具有相同父级的节点进行sorting。

我所说的“结果集”可以被描绘成一连串hashmaps(留在这个术语中)。 我的例子本来就是在那里。 有些答案会加倍努力,并首先构build它,但那没关系。

树可以任意深。 每个节点可以有N个孩子。 尽pipe如此,我并没有真正拥有“数以百万计的条目”树。

不要把我select的节点命名('节点1.1.1')弄糊涂了。 节点也可以称为“弗兰克”或“鲍勃”,没有命名结构的暗示,这只是为了使其可读性。

我已经发布了我自己的解决scheme,所以你们可以把它拉成碎片。

    在关系数据库中存储树结构化数据有多种方法。 您在示例中显示的内容使用两种方法:

    • 邻接列表 (“父”列)和
    • path枚举 (您的名字列中的虚线数字)。

    另一个解决scheme称为嵌套集 ,它也可以存储在同一个表中。 阅读Joe Celko的“ SQL中的树和层次结构 ”,了解关于这些devise的更多信息。

    我通常更喜欢一个称为Closure Table (又名“Adjacency Relation”)的devise来存储树形结构的数据。 它需要另一个表格,但是查询树木非常容易。

    我在我的演示文稿中介绍了Closure Table SQL和PHP的分层数据模型以及我的书SQL反模式:避免数据库编程的陷阱 。

     CREATE TABLE ClosureTable ( ancestor_id INT NOT NULL REFERENCES FlatTable(id), descendant_id INT NOT NULL REFERENCES FlatTable(id), PRIMARY KEY (ancestor_id, descendant_id) ); 

    将所有path存储在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下降。


    Re:关于直系孩子(或直系父母)的电子交stream评论。 您可以在path_length添加一个“ path_length ”列,以便更ClosureTable地查询直接的子项或父项(或任何其他距离)。

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

    然后,可以在search中添加一个术语来查询给定节点的直接子节点。 这些是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重新评论:“如何sorting整个树(按名称)?”

    下面是一个示例查询,返回所有属于节点1后代的节点,将它们连接到包含其他节点属性(如name的FlatTable,并按namesorting。

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

    用户今天build议编辑。 所以主持人批准了这个编辑,但是我正在倒转。

    编辑build议上面最后一个查询中的ORDER BY b.path_length, f.name应该是ORDER BY b.path_length, f.name ,大概是为了确保sorting与层次匹配。 但是这不起作用,因为它会在“节点1.2”之后命令“节点1.1.1”。

    如果您希望命令以合理的方式匹配层次结构,这是可能的,但不能简单地按path长度sorting。 例如,请参阅我对MySQL Closure Table分层数据库的回答- 如何以正确的顺序提取信息 。

    如果使用嵌套集(有时称为修改的预定义树遍历),则可以使用单个查询提取整个树结构或其中的任何子树,但代价是插入代价更高,因为您需要pipe理通过树结构描述有序path的列。

    对于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
    

    或者,作为一个嵌套的设置图,这使得它更加明显地显示了左右值的工作原理:

      __________________________________________________________________________
     | 根1 |
     |  ________________________________ ________________________________ |
     |  | 孩子1.1 |  | 孩子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
     |  | ________________________________ |  | ________________________________ |  |
     | __________________________________________________________________________ |
    

    正如你所看到的,为了得到给定节点的整个子树,按照树的顺序,你只需要selectlftrght值之间有lftrght值的所有行。 检索给定节点的祖先树也很简单。

    为了方便起见, tree_idtree_id的一点, tree_id列允许您为每个顶级节点重新开始lftrght编号,这减less了插入,移动和删除所影响的列数,就像lft当这些行动发生时,必须相应地调整列以创造或缩小差距。 当时我正试图围绕每个操作所需的查询来解决问题,我做了一些开发笔记 。

    就实际使用这些数据来显示一棵树而言,我创build了一个tree_item_iterator实用程序函数,它为每个节点提供足够的信息来生成所需的任何types的显示。

    有关MPTT的更多信息:

    • SQL中的树
    • 将分层数据存储在数据库中
    • 在MySQL中pipe理分层数据

    从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开始,可以使用recursion公用表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] 

    两者都会输出以下结果。

    名称
     '节点1'
     '节点1.1'
     '节点1.1.1'
     '节点1.2'
     '节点2'
     '节点2.1'
    

    这是一个相当古老的问题,但是因为它有很多观点,所以我认为值得提出一个替代scheme,在我看来,这是非常优雅的解决scheme。

    为了读取树结构,可以使用recursion公用表expression式 (CTE)。 它提供了一次获取整个树结构的可能性,获得关于父节点的子节点中的节点,其父节点和顺序的信息。

    让我告诉你如何在PostgreSQL 9.1中工作。

    1. 创build一个结构

       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. 写一个查询

       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) 

      树节点按深度sorting。 在最后的输出中,我们将在后面的行中提供它们。

      对于每个级别,它们都由父级中的parent_id和node_order进行sorting。 这告诉我们如何在输出链接节点中以父顺序显示它们。

      有了这样的结构,在HTML中做一个非常好的演示并不困难。

      recursionCTE在PostgreSQL,IBM DB2,MS SQL Server和Oracle中都可用。

      如果您想了解更多关于recursionSQL查询的知识,您可以查看您最喜欢的DBMS的文档,或者阅读我关于此主题的两篇文章:

      • 在SQL中执行:recursion树遍历
      • 了解SQLrecursion查询的function

    比尔的回答是非常好的,这个答案增加了一些东西,这让我希望SO支持线程答案。

    无论如何,我想支持树结构和Order属性。 我在每个Node中包含了一个名为leftSibling的单个属性, Order与原始问题(保持从左到右的顺序)相同。

     mysql> desc节点;
     + ------------- + -------------- + ------ + ----- + ------- -  + ---------------- +
     | 字段| types| 空| 密钥| 默认| 额外|
     + ------------- + -------------- + ------ + ----- + ------- -  + ---------------- +
     |  id |  int(11)|  NO |  PRI |  NULL |  auto_increment |
     | 名字|  varchar(255)| 是|  |  NULL |  |
     |  leftSibling |  int(11)|  NO |  |  0 |  |
     + ------------- + -------------- + ------ + ----- + ------- -  + ---------------- +
     3行(0.00秒)
    
     mysql> desc adjacencies;
     + ------------ + --------- + ------ + ------ + --------- + --- ------------- +
     | 字段| types| 空| 密钥| 默认| 额外|
     + ------------ + --------- + ------ + ------ + --------- + --- ------------- +
     |  relationId |  int(11)|  NO |  PRI |  NULL |  auto_increment |
     | 父母|  int(11)|  NO |  |  NULL |  |
     | 孩子|  int(11)|  NO |  |  NULL |  |
     |  pathLen |  int(11)|  NO |  |  NULL |  |
     + ------------ + --------- + ------ + ------ + --------- + --- ------------- +
    设置4行(0.00秒)
    

    更多的细节和我的博客上的SQL代码 。

    谢谢比尔你的答案有助于开始!

    那么给出的select,我会使用的对象。 我会为每个logging创build一个对象,其中每个对象都有一个子集合,并将它们全部存储在Id是关键字的关联数组(/ hashtable)中。 并通过收集突击一次,添加到有关儿童领域的儿童。 简单。

    但是因为限制使用一些很好的OOP你没有什么乐趣,所以我可能会基于:

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

    编辑:这是类似于其他一些条目,但我认为它稍微清洁。 我会补充一件事:这是非常密集的SQL。 这是讨厌的如果你有select,去面向对象的路线。

    这是写得很快,既不漂亮也不高效(加上自动包装很多, intInteger之间转换很烦人!),但它的工作原理。

    它可能违反了规则,因为我创build自己的对象,但嘿,我这样做是为了从真正的工作转移:)

    这还假设在开始构build节点之前,结果集/表已经被完全读入某种结构,如果有成千上万的行,这不是最好的解决scheme。

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

    假设你知道根元素是零,这里是伪代码输出到文本:

     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) 

    你可以使用hashmap模拟任何其他的数据结构,所以这不是一个可怕的限制。 从顶部到底部扫描,为数据库的每一行创build一个散列映射,并为每个列创build一个条目。 将这些hashmaps中的每一个添加到一个“主”哈希映射,键入的ID。 如果任何节点具有尚未见过的“父”,请在主散列映射中为其创build占位符条目,并在看到实际节点时填写它。

    要将其打印出来,请执行简单的深度优先传递数据,并跟踪缩进级别。 您可以通过为每行保留一个“children”条目,并在扫描数据时填充它来简化操作。

    至于在数据库中是否有“更好”的方式来存储树,这取决于你将如何使用数据。 我已经看到具有已知最大深度的系统为层次结构中的每个级别使用了不同的表。 如果树中的级别不是完全相同(顶级类别不同于树叶),那么这就很有意义。

    有很好的解决scheme,利用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,表示节点的“下一个孩子”的tw。

    这里是一个例子24节点人口,由twsorting:

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

    每棵树的结果都可以非recursion地完成。 例如,要获得tw = '22'节点的祖先列表,

    祖先

     select anc.* from node me,node anc where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw order by anc.tw; +-----+---------+----+------+------+------+ | id | name | tw | pa | sz | nc | +-----+---------+----+------+------+------+ | 1 | Root | 1 | NULL | 24 | 25 | | 17 | C | 17 | 1 | 6 | 23 | | 359 | C0 | 18 | 17 | 5 | 23 | | 360 | C1 | 19 | 18 | 4 | 23 | | 361 | C2(res) | 20 | 19 | 3 | 23 | | 362 | C3 | 21 | 20 | 2 | 23 | | 363 | C4 | 22 | 21 | 1 | 23 | +-----+---------+----+------+------+------+ 

    兄弟姐妹和孩子是微不足道的 – 只是使用pa字段顺序tw。

    后人

    例如,植根于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 | +-----+---------+----+------+------+------+ 

    补充笔记

    这种方法对于读取次数远远多于插入或更新次数非常有用。

    由于树中节点的插入,移动或更新需要调整树,所以在开始动作之前,需要locking表。

    插入/删除成本很高,因为tw索引和sz(分支大小)值将需要在插入点之后的所有节点以及所有祖先上分别更新。

    分支移动涉及将分支的tw值移出范围,因此在移动分支时还需要禁用外键约束。 基本上有四个查询需要移动分支:

    • 将分支移出范围。
    • 缩小它留下的差距。 (剩下的树现在正常化了)。
    • 打开它将要去的地方。
    • 将分支移动到新的位置。

    调整树查询

    树中间隙的打开/closures是创build/更新/删除方法所使用的一个重要的子function,所以我将它包含在这里。

    我们需要两个参数 – 一个标志,表示我们是否正在缩小规模或者规模扩大,以及节点的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; 

    如果可以创build嵌套的哈希映射或数组,那么我可以简单地从头开始,并将每个项目添加到嵌套数组。 我必须将每一行跟踪到根节点,以便知道嵌套数组中要插入哪个级别。 我可以使用memoization,所以我不需要一遍又一遍地查找同一个父母。

    编辑:我会读整个表到数组中,所以它不会重复查询数据库。 如果你的桌子很大,这当然不会实用。

    在构build好这个结构之后,我必须先深入一遍才能打印出HTML。

    使用一个表格存储这些信息没有更好的基本方法(虽然我可能是错的),并希望看到更好的解决scheme)。 但是,如果你创build一个scheme来dynamic创build数据库表,那么你就以牺牲简单性和SQL风险为代价打开了一个全新的世界;)。

    如果元素按照树的顺序(如你的例子所示),你可以使用类似下面的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) 

    这样做是维护一个代表树中当前位置的堆栈。 对于表中的每个元素,它popup堆栈元素(closures匹配的div),直到find当前项目的父项。 然后输出该节点的开始并将其推送到堆栈。

    如果要使用缩进而不是嵌套元素输出树,则可以简单地跳过打印语句以打印div,并在每个项目之前打印等于堆栈大小的几倍的空格。 例如,在Python中:

     print " " * len(stack) 

    您也可以轻松使用此方法来构build一组嵌套列表或字典。

    编辑:我从你的澄清看到,名称不打算成为节点path。 这表明了另一种方法:

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

    这构造了元组(!)的数组树。 idx [0]表示树的根。 数组中的每个元素都是由节点本身和所有子节点组成的2元组。 一旦构build完成,您可以保留idx [0]并放弃idx,除非您想通过ID访问节点。

    要扩展比尔的SQL解决scheme,你可以使用平面arrays基本上做同样的事情。 更进一步,如果你的string都具有相同的长度,并且你已经知道了最大数量的子元素(比如在一个二叉树中),你可以使用一个string(字符数组)来完成。 如果你有任意数量的孩子,这会使事情变得复杂一些…我将不得不检查我的旧笔记,看看能做些什么。

    那么,牺牲一点内存,特别是如果你的树稀疏和/或不匹配,你可以用一些索引math,通过存储你的树随机访问所有的string,宽度在数组中像这样(二进制树):

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

    你知道你的string的长度,你知道的

    我现在在工作,所以不能花太多的时间,但有兴趣,我可以取一些代码来做到这一点。

    我们使用它来search由DNA密码子组成的二叉树,一个过程构build了树,然后我们将其平坦化以search文本模式,并且当发现时,尽pipe指数math(从上面的倒数),我们得到节点…非常快速和高效,我们的树很难有空的节点,但我们可以在jiffy中search千兆字节的数据。

    考虑使用像neo4j这样的nosql工具来build立分层结构。 例如像linkedin这样的联网应用程序使用couchbase(另一个nosql解决scheme)

    但是,只能将nosql用于数据集市级查询,而不能存储/维护事务