SQL 树结构

Question

我在 SQL 对这个主题（即树结构）不熟悉。我已经浏览了不同的来源，但仍然不清楚。

在我的案例中，我有一个 table 附在此处。

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

我还必须在附加的分层数据中找到所有叶节点（没有子节点的节点）。

请提供详细解释的答案。提前致谢。

Answer 1

Now here first, I have to retrieve a Full Tree for “OFFICE”.

您想如何表示您的树？你发的已经可以算作一棵树了

Also I have to find all the leaf nodes (those with no Children) in the attached hierarchical data.

TSQL:

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

内部的 select 会给你所有指向某个父级的 ID。外部 select 将为您提供内部 select 没有结果的所有节点。

Answer 2

有一个名为 "hardcoded trees" 的模式设计可用于此目的。

然后您可以使用此查询为每个 child

查找 parent

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID

或者这个用于为每个 parent 找到 children:

SELECT level1ID FROM Level2entity as L2 WHERE level2ID = :aLevel2ID

Answer 3

如果你能负担得起一点预处理时间，那么这个问题的经典解决方案是使用 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) */

获取 Category1 的后代（以及该节点本身）

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：如果您的数据库支持它，使用常见的 table 表达式是另一种可能性，它避免了预处理步骤，并且在面对更改树结构。

（我没有测试此答案中给出的任何代码。您可能需要在这里和那里应用一些修复；特别是，如果您选择的项目语言是 而不是 python...)

Answer 4

您没有指定您的 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;

如果需要子树，只需要改变普通table表达式中的起始条件即可。得到例如全部 "categories":

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

SQL小提琴示例：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;

SQLOracle 小提琴：http://sqlfiddle.com/#!4/6774ee/3

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

SQL 树结构

SQL Tree Structure

sql

oracle

hierarchical-data

recursive-query