SQL树结构

Question

我是SQL中的新主题（即树结构）。我经历了不同的来源，但仍不清楚。

这里在我的情况下，我有一张附表。

现在这里首先，我要找回一个完整的树的“办公室”。

此外，我必须找到附加的分层数据中的所有叶节点（没有儿童）。

请提供详细解释的答案。 在此先感谢。

Answer 1

你没有指定你的DBMS但随着标准的SQL（所有modern DBMS支持），您可以轻松地做一个递归查询，以获得完整的树：

with recursive full_tree as (
    select id, name, parent, 1 as level 
    from departments 
    where parent is null 
    union all 
    select c.id, c.name, c.parent, p.level + 1 
    from departments c 
    join full_tree p on c.parent = p.id 
) 
select * 
from full_tree; 

如果你需要一个子树，只是改变了在公用表格表达式中的起始条件。为了得到例如所有的 “类别”：

with recursive all_categories as (
    select id, name, parent, 1 as level 
    from departments 
    where id = 2 --- << start with a different node 
    union all 
    select c.id, c.name, c.parent, p.level + 1 
    from departments c 
    join all_categories p on c.parent = p.id 
) 
select * 
from all_categories; 

让所有叶子很简单：这是在那里他们的ID不会显示为一个parent所有节点：

select * 
from departments 
where id not in (select parent 
       from departments 
       where parent is not null); 

SQLFiddle例如：http://sqlfiddle.com/#!15/414c9/1

---

编辑在DBMS被指定之后。

Oracle确实支持递归CTE（尽管您需要11.2.x），您只需要忽略关键字recursive。但你也可以使用CONNECT BY操作：

select id, name, parent, level 
from departments 
start with parent is null 
connect by prior id = parent; 

select id, name, parent, level 
from departments 
start with id = 2 
connect by prior id = parent; 

SQLFiddle对于Oracle：http://sqlfiddle.com/#!4/6774ee/3

详情请参见手册：https://docs.oracle.com/database/121/SQLRF/queries003.htm#i2053935

Answer 2

现在，首先，我必须检索“OFFICE”的完整树。

你想如何表示你的树？你发布的内容已经可以算作一棵树了。

此外，我必须找到附加的分层数据中的所有叶节点（没有儿童）。

TSQL：

select * 
from table outer 
where id not in (select id 
       from table inner 
       where inner.parent = outer.id) 

内选择会给你指向一个特定的父母所有的ID。外部选择将为您提供内部选择不会产生任何结果的所有节点。

Answer 3

有一种称为“硬编码树”的模式设计，可以用于此目的。

然后你可以使用这个查询寻找父母为每个孩子

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID 

或者这一个寻找孩子们为每个父：

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID 

Answer 4

如果你能买得起一点点预处理时间的一小部分，那么这个问题的典型解决方案是使用nested sets。

CREATE TABLE node (
    id INTEGER NOT NULL PRIMARY KEY, 
    name VARCHAR(255) NOT NULL, 
    parent_id INTEGER DEFAULT NULL, 
    seq_min INTEGER NOT NULL, 
    seq_max INTEGER NOT NULL 
); 

假设，您使用的内存中的数据结构的某种像

class Node: 
    def __init__(self, id, name, children=()): 
     self.id = id 
     self.name = name 
     self.children = list(children) 

代表在内存中的树节点，我们就可以定义

def assign_sequence_numbers(root_node): 
    def recurse(counter, node): 
     node.seq_min = counter 
     node.seq_max = reduce(recurse, node.children, 1 + counter) 
     return node.seq_max 
    return recurse(1, root_node) 

它做了在树上预先遍历，这为每个节点分配两个附加数字：

seq_min值将成为每个节点的备用唯一整数键。此外，节点的所有直接子节点（和间接子节点）的值都将为seq_min，该值大于分配给节点本身的值。

seq_max值仅仅是所有后代节点的seq_min值的上限。

例：考虑下面的树

Root 
| 
+--- Category1 
|  | 
|  +--- Category1.1 
|  | 
|  `--- Category1.2 
| 
`--- Category2 

使用上面定义的函数，我们得到

Root [min=1, max=6] 
| 
+--- Category1 [min=2, max=5] 
|  | 
|  +--- Category1.1 [min=3, max=4] 
|  | 
|  `--- Category1.2 [min=4, max=5] 
| 
`--- Category2 [min=5, max=6] 

注意，对于每一个节点上，min值始终< =的min值所有后代和max的值始终是>所有后代的最大值。所以，找到Root后裔和节点本身（即得到整个树），我们会做：

SELECT * FROM node 
WHERE seq_min >= 1 /* i.e., seq_min(Root) */ 
AND seq_min < 6 /* i.e., seq_max(Root) */ 

要获得组别的后裔（并在该节点本身）

SELECT * FROM node 
WHERE seq_min >= 2 /* i.e., seq_min(Category1) */ 
AND seq_min < 5 /* i.e., seq_max(Category2) */ 

该方法的缺点是，原则上，如果对树进行更改（即插入新节点或删除旧节点），则必须重新为所有节点分配seq_xxx数字。这通常不是问题，至少如果对树结构的更改不频繁且树足够小。

由于ITGenius已经链接到that answer：如果您的数据库支持它，使用公用表表达式是另一种可能性，它避免了预处理步骤，并且在面对树结构更改时也更具弹性。

（我没有测试任何在这个答案中给出的代码，你可能需要在这里和那里申请几个补丁;特别是，如果你选择的项目的语言是不蟒蛇 ...）