在关系数据库中存储分层数据有哪些选项？

Question

在关系数据库中存储分层数据有哪些选项？

好的概述

一般来说，您要在快速读取时间（例如，嵌套集）或快速写入时间（邻接列表）之间做出决定。通常，您最终会得到最适合您需求的以下选项组合。以下提供了一些深入阅读：

• 还有一个嵌套间隔与邻接列表比较：我发现的邻接列表，物化路径，嵌套集和嵌套间隔的最佳比较。

• 分层数据的模型：幻灯片，有很好的权衡解释和示例用法

• 在MySQL中表示层次结构：特别是对嵌套集的非常好的概述

• RDBMS中的分层数据：我见过的最全面，组织良好的链接集，但解释方式不多

选项

我知道和一般的功能：

1. 邻接清单：

• 列：ID，ParentID

• 易于实施。

• 便宜节点移动，插入和删除。

• 昂贵的找到水平，血统和后代，路径

• 在支持它们的数据库中通过公用表表达式避免使用N + 1

2. 嵌套集（又名修改的预订树遍历）

• 列：左，右

• 便宜的血统，后代

• 非常昂贵的O(n/2)移动，插入，由于易失性编码而删除

3. 桥表（又名闭包表/ w触发器）

• 使用单独的连接表：祖先，后代，深度（可选）

• 廉价的血统和后代

• 写入O(log n)插入，更新，删除的成本（子树的大小）

• 规范化编码：适用于连接中的RDBMS统计信息和查询规划器

• 每个节点需要多行

4. 谱系列（又名物化路径，路径枚举）

• 专栏：血统（例如/父母/孩子/孙子/等......）

• 廉价后代通过前缀查询（例如LEFT(lineage, #) = '/enumerated/path'）

• 写入O(log n)插入，更新，删除的成本（子树的大小）

• 非关系型：依赖于Array数据类型或序列化字符串格式

5. 嵌套间隔

• 像嵌套集一样，但是使用实数/浮点数/小数，这样编码就不易变（廉价的移动/插入/删除）

• 有实/浮/十进制表示/精度问题

• 矩阵编码变体为“自由”添加了祖先编码（物化路径），但增加了线性代数的诡计。

6. 平表

• 修改的Adjacency List，为每条记录添加Level和Rank（例如排序）列。

• 便宜迭代/分页

• 昂贵的移动和删除

• 好用：线程讨论 - 论坛/博客评论

7. 多个谱系列

• 列：每个谱系级别一个，指向根目录的所有父级，从项目级别向下的级别设置为NULL

• 便宜的祖先，后代，水平

• 便宜的插入，删除，移动的叶子

• 昂贵的插入，删除，移动内部节点

• 对层次结构有多深的硬性限制

数据库特定说明

MySQL的

• 将会话变量用于Adjacency List

神谕

• 使用CONNECT BY遍历邻接列表

PostgreSQL的

• 物化路径的ltree数据类型

SQL Server

• 总结

• 2008年提供的HierarchyId数据类型似乎有助于Lineage Column方法并扩展可以表示的深度。

Answer 1

这是对你的问题的非常局部的答案，但我希望仍然有用。Microsoft SQL Server 2008实现了两个对管理分层数据非常有用的功能：所述HierarchyId的数据类型。公用表表达式，使用with关键字。看一看“的模式您的数据层次结构有了SQL Server 2008”由Kent Tegels MSDN上的开始。另请参阅我自己的问题：SQL Server 2008中的递归同表查询