树的数据库设计：按父级、按层或两者选择

Question

我想在关系数据库中存储同类项目的树（即每个项目只有一个父节点，或 none 作为根节点）。偶尔会写入树，最常见的是在某处添加一个叶节点，不太频繁地添加一个中间节点。

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

Select 具有特定父项 的所有项目。
Select 位于树中特定层 / 特定深度的所有项目。

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

我对该数据库的结构有哪些选择？数据库可能有几千个条目。我的目标是使这两种类型的查询都更快。

Answer 1

此解决方案适用于支持递归通用 Table 表达式（除了 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 = ?;

这会计算 table 中每一行的级别，因此可以对其进行优化，但我不确定如何优化。物化视图是一种选择。

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

树的数据库设计：按父级、按层或两者选择

Database design for a tree: selection by parent, by layer or both

tree

database-design

relational-database