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在支持它们的数据库中

Nested Set (又名 Modified Preorder Tree Traversal )

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

Bridge Table (又名 Closure Table /w triggers )

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

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

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

Nested Intervals

• 与嵌套集类似，但使用实数/浮点/小数，以便编码不易变化(移动/插入/删除成本低廉)
• 存在实数/浮点/小数表示/精度问题
• Matrix encoding variant添加“免费”的祖先编码(物化路径)，但增加了线性代数的技巧。

Flat Table

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

Multiple lineage columns

• 列:每个谱系级别一列，指的是直到根为止的所有父级，从项目级别向下的级别设置为 NULL
• 廉价的祖先、后代、等级
• 叶子的插入、删除、移动成本低廉
• 内部节点的插入、删除、移动成本高昂
• 对层次结构的深度进行硬性限制

数据库特定注释

MySQL/MariaDB

• <罢工> Use session variables for Adjacency List
• 在 MySQL 8.0 或 MariaDB 10.2 中使用 CTE

甲骨文

• 使用CONNECT BY遍历邻接表

PostgreSQL

• ltree datatype对于物化路径

SQL Server

• General summary
• 2008年优惠HierarchyId这种数据类型似乎有助于使用谱系列方法并扩展可表示的深度。

Answer 1

我最喜欢的答案是本主题第一句话所建议的。使用邻接列表来维护层次结构并使用嵌套集来查询层次结构。

到目前为止的问题是，从邻接列表到嵌套集的转换方法非常慢，因为大多数人使用称为“推栈”的极端 RBAR 方法来进行转换，并且被认为是通过邻接列表来实现维护简单性和嵌套集的出色性能的涅槃的方式是昂贵的。结果，大多数人最终不得不选择其中一个，特别是当节点数量超过 100,000 个左右时。使用推栈方法可能需要一整天的时间才能对传销者认为的小型百万节点层次结构进行转换。

我想通过提出一种以看似不可能的速度将邻接表转换为嵌套集的方法来给 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 万个节点在不到一分钟内完成转换，100,000 个节点在 4 秒内完成转换。

您可以通过以下 URL 了解新方法并获取代码副本。 http://www.sqlservercentral.com/articles/Hierarchy/94040/

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

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