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

Question

良好的概述

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

• One more Nested Intervals vs. Adjacency List comparison : 我发现的邻接列表、物化路径、嵌套集和嵌套间隔的最佳比较。
• Models for hierarchical data : 幻灯片很好地解释了权衡和示例用法
• Representing hierarchies in MySQL : 特别是嵌套集的非常好的概述
• Hierarchical data in RDBMSs :我见过的最全面、组织最完善的一组链接，但没有太多解释

选项

我知道的和一般特征:

1. Adjacency List :

• 列:ID、ParentID
• 易于实现。
• 廉价节点移动、插入和删除。
• 查找级别、祖先和后代、路径的开销很大
• 通过 Common Table Expressions 避免 N+1在支持它们的数据库中

1. Nested Set (又名 Modified Preorder Tree Traversal )

• 列:左、右
• 廉价的祖先，后代
• 非常昂贵的O(n/2) 移动、插入、删除由于可变编码

1. Bridge Table (又名 Closure Table /w triggers )

• 使用具有祖先、后代、深度(可选)的单独连接表
• 廉价的祖先和后代
• 插入、更新、删除的写入成本 O(log n)(子树的大小)
• 规范化编码:适用于 RDBMS 统计和连接中的查询规划器
• 每个节点需要多行

1. Lineage Column (又名 Materialized Path，路径枚举)

• 列:世系(例如/parent/child/grandchild/etc...)
• 通过前缀查询的廉价后代(例如 LEFT(lineage, #) = '/enumerated/path')
• 插入、更新、删除的写入成本 O(log n)(子树的大小)
• 非关系型:依赖数组数据类型或序列化字符串格式

1. Nested Intervals

• 类似于嵌套集，但具有实数/ float /十进制数，因此编码不是易变的(廉价的移动/插入/删除)
• 有实数/ float /十进制表示/精度问题
• Matrix encoding variant为“免费”添加祖先编码(物化路径)，但增加了线性代数的技巧。

1. Flat Table

• 修改后的邻接列表，为每条记录添加级别和排名(例如排序)列。
• 迭代/分页成本低
• 昂贵的移动和删除
• 好的用途:线程式讨论 - 论坛/博客评论

1. Multiple lineage columns

• Columns:每个lineage level对应一个columns，指的是所有parents up to root，从item的level往下的levels被设置为NULL
• 贱祖、后裔、平
• 叶子的廉价插入、删除、移动
• 昂贵的插入、删除、移动内部节点
• 对层次结构的深度有硬性限制

数据库特定说明

MySQL

• Use session variables for Adjacency List

甲骨文

• 使用CONNECT BY遍历邻接表

PostgreSQL

• ltree datatype对于物化路径

SQL Server

• General summary
• 2008年报价HierarchyId似乎有助于沿袭列方法并扩展可以表示的深度的数据类型。

Answer 1

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

到目前为止的问题是，从邻接列表到嵌套集的转换方法非常慢，因为大多数人使用称为“推栈”的极端 RBAR 方法来进行转换，并且被认为是通过邻接列表和嵌套集的出色性能来达到维护简单性的必杀技的昂贵方式。结果，大多数人最终不得不接受一个或另一个，尤其是当节点数量超过 100,000 个左右时。使用 push stack 方法可能需要一整天的时间来完成 MLM'ers 认为是小型百万节点层次结构的转换。

我想我会想出一种方法，以看似不可能的速度将邻接列表转换为嵌套集，从而给 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!!!)

是的，没错。不到 1 分钟转换了 100 万个节点，不到 4 秒转换了 100,000 个节点。

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

我还使用类似的方法开发了一个“预聚合”层次结构。传销人员和制作 Material list 的人会对本文特别感兴趣。 http://www.sqlservercentral.com/articles/T-SQL/94570/

如果您确实路过查看任何一篇文章，请跳转到“加入讨论”链接，让我知道您的想法。