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

好的概述

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

还有一个嵌套间隔与邻接列表比较：我发现的邻接列表，物化路径，嵌套集和嵌套间隔的最佳比较 。
分层数据的模型：幻灯片，有很好的权衡解释和示例用法
代表 MySQL 中的层次结构：特别是对嵌套集的非常好的概述
RDBMS 中的分层数据：我见过的最全面，组织良好的链接集，但解释方式不多

选项

我知道和一般的功能：

邻接清单：
- 列：ID，ParentID
- 易于实施。
- 便宜节点移动，插入和删除。
- 昂贵的找到水平，血统和后代，路径
- 在支持它们的数据库中通过公用表表达式避免使用 N + 1
嵌套集（又名修改的预订树遍历）
- 列：左，右
- 便宜的血统，后代
- 非常昂贵的O(n/2)移动，插入，由于易失性编码而删除
桥表（又名闭包表 / w 触发器）
- 使用单独的连接表：祖先，后代，深度（可选）
- 廉价的血统和后代
- 为插入，更新，删除写入成本O(log n) （子树的大小）
- 规范化编码：适用于连接中的 RDBMS 统计信息和查询规划器
- 每个节点需要多行
谱系列（又名物化路径，路径枚举）
- 专栏：血统（例如 / 父母 / 孩子 / 孙子 / 等......）
- 通过前缀查询的廉价后代（例如LEFT(lineage, #) = '/enumerated/path' ）
- 为插入，更新，删除写入成本O(log n) （子树的大小）
- 非关系型：依赖于 Array 数据类型或序列化字符串格式
嵌套间隔
- 像嵌套集一样，但是使用实数 / 浮点数 / 小数，这样编码就不易变（廉价的移动 / 插入 / 删除）
- 有实 / 浮 / 十进制表示 / 精度问题
- 矩阵编码变体为 “自由” 添加了祖先编码（物化路径），但增加了线性代数的诡计。
平表
- 修改的 Adjacency List，为每条记录添加 Level 和 Rank（例如排序）列。
- 便宜迭代 / 分页
- 昂贵的移动和删除
- 好用：线程讨论 - 论坛 / 博客评论
多个谱系列
- 列：每个谱系级别一个，指向根目录的所有父级，从项目级别向下的级别设置为 NULL
- 便宜的祖先，后代，水平
- 便宜的插入，删除，移动的叶子
- 昂贵的插入，删除，移动内部节点
- 对层次结构有多深的硬性限制

数据库特定说明

MySQL 的

将会话变量用于 Adjacency List

神谕

使用CONNECT BY遍历邻接列表

PostgreSQL 的

物化路径的ltree 数据类型

SQL Server

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

答案

我最喜欢的答案就是这个帖子中第一句话的建议。使用邻接列表维护层次结构并使用嵌套集查询层次结构。

直到现在的问题一直是从邻接列表到嵌套集的转换方法非常缓慢，因为大多数人使用称为 “推送栈” 的极端 RBAR 方法来进行转换，并且被认为是昂贵的方式通过邻接列表和嵌套集的强大性能来达到 Nirvana 的简单维护。结果，大多数人最终不得不满足于一个或另一个，特别是如果有超过 10 万个节点那么多。使用推送栈方法可能需要一整天的时间来完成 MLM'ers 认为是一个小百万节点层次结构的转换。

我想我会通过提出一种方法将 Celacency List 转换为嵌套集合，以一种看似不可能的速度给 Celko 带来一些竞争。这是 i5 笔记本电脑上推送栈方法的性能。

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

这是新方法的持续时间（在括号中使用推送堆栈方法）。

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

对，那是正确的。在不到一分钟的时间内转换了 100 万个节点，在 4 秒内转换了 100,000 个节点。

您可以阅读有关新方法的信息，并从以下 URL 获取代码的副本。 http://www.sqlservercentral.com/articles/Hierarchy/94040/

我还使用类似的方法开发了 “预聚合” 层次结构。 MLM'ers 和制作材料清单的人将对本文特别感兴趣。 http://www.sqlservercentral.com/articles/T-SQL/94570/

如果你停下来看看这两篇文章，请跳到 “加入讨论” 链接，让我知道你的想法。

这是对你的问题的非常局部的答案，但我希望仍然有用。

Microsoft SQL Server 2008 实现了两个对管理分层数据非常有用的功能：

HierarchyId数据类型。
公用表表达式，使用with关键字。

在 MSDN 上查看 Kent Tegels 的“使用 SQL Server 2008 建模您的数据层次结构”以获取启动。另请参阅我自己的问题： SQL Server 2008 中的递归同表查询

此设计尚未提及：

多个谱系列

虽然它有局限性，但如果你能承受它，那就非常简单而且效率很高。特征：

列：每个谱系级别一个，指向根目录下的所有父级，低于当前项级别的级别设置为 NULL
限制层次结构的深度
便宜的祖先，后代，水平
便宜的插入，删除，移动的叶子
昂贵的插入，删除，移动内部节点

下面是一个例子 - 鸟类的分类树，所以层次结构是 Class / Order / Family / Genus / Species - 物种是最低级别，1 行 = 1 个分类单元（对应于叶子节点的物种）：

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

以及数据的例子：

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

这很好，因为只要内部类别不改变树中的级别，这种方式就可以非常简单的方式完成所有需要的操作。