树的数据库设计:按父、层或两者进行选择

Question

我希望在关系数据库中存储同构项的树(即每个项都有一个父项，或者根节点没有一个父项)。偶尔会有对树的写操作，最常见的情况是要在某个地方添加叶节点，而不太频繁地添加中间节点。

两种最常见的查询类型是：

1. 选择具有特定父的所有项。
2. 选择在特定层/在树中特定深度的所有项。

只存储每个项的父项(根节点为null)，第一种情况很容易。对于第二种情况，我必须迭代并计数每个项目的父级，直到到达根节点，或者显式地存储该层，从而引入冗余。

我对这个数据库的结构有什么选择？数据库可能有几千个条目。我的目标是快速实现这两种类型的查询。

Answer 1

此解决方案适用于支持递归公共表表达式(除了MySQL以外的任何东西)的数据库。

您应该使用邻接列表：

create table foo (
  id int primary key,
  name text not null,
  parent_id int null references foo(id)
);

您的查询应该如下所示：

with recursive expression1 as (

  --select the root node:
  select
    id,
    name,
    1 as level
  from foo
  where
    parent_id is null

  union all

  select
    current.id,
    current.name,
    previous.level + 1 as level
  from foo current
  join expression1 as previous on current.parent_id = previous.id
)

select * from expression1
where
  level = ?;

这将计算表中每一行的级别，因此可能有可能对其进行优化，但我不完全确定如何进行优化。物化视图是一个选项。

工作示例：http://sqlfiddle.com/#!15/ad19f/10