[Sql] 在关系数据库中存储分层数据有哪些选项?


Answers

这是你的问题的一个非常部分的答案,但我希望仍然有用。

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

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

Question

良好的概述

一般而言,您正在快速读取时间(例如,嵌套集)或快速写入时间(邻接列表)之间做出决定。 通常情况下,您最终会得到最适合您需求的选项组合。 以下内容提供了一些深入的解读:

选项

我知道的和一般特征:

  1. 邻接表
    • 列:ID,ParentID
    • 易于实施。
    • 便宜的节点移动,插入和删除。
    • 昂贵的找到关卡(可以存储为计算列),祖先和后代(桥表结合等级列可以解决),路径(Lineage Column可以解决)。
    • 在支持它们遍历的那些数据库中使用公用表表达式
  2. 嵌套集合 (又名修改先序树遍历)
    • Joe Celko在众多文章中以及他的书中的Trees and Hierarchies in SQL for Smarties中得到了推广
    • 列:左,右
    • 便宜的水平,血统,后代
    • 易失性编码 - 移动,插入,删除更昂贵。
    • 需要特定的排序顺序(例如创建)。 因此,以不同顺序排序所有后代需要额外的工作。
  3. 嵌套间隔
    • 像嵌套集合,但与真正/浮点/小数,使编码不挥发(便宜的移动/插入/删除)
    • 必须处理真实/浮点/小数表示问题
    • 一个更复杂的矩阵编码变体增加了祖先编码的好处,就像物化路径的“自由”
  4. 桥接表 (又名Closure Table :关于如何使用触发器维护这种方法的一些好主意)
    • 专栏:祖先,后代
    • 与它描述的表格分开。
    • 可以在一个以上的层次结构中包含一些节点。
    • 廉价的祖先和后代(尽管不是以什么顺序)
    • 对于层次结构的完整知识需要与另一个选项相结合。
  5. 平的表
    • 邻接列表的修改,为每条记录添加级别和排名(例如排序)列。
    • 昂贵的移动和删除
    • 廉价的祖先和后代
    • 好用:线程讨论 - 论坛/博客评论
  6. 沿袭列 (又名物化路径 ,路径枚举)
    • 专栏:谱系(例如/父母/孩子/孙子/等等)
    • 限制层次结构的深度。
    • 后代便宜(例如LEFT(lineage, #) = '/enumerated/path'
    • 祖先棘手(数据库特定查询)
  7. 多谱系列
    • 列:每个血统级别的一个,指的是所有的父母直到根,从该项目的级别下降的级别都设置为NULL
    • 限制层次结构的深度
    • 廉价的祖先,后代,水平
    • 廉价的插入,删除,移动的叶子
    • 昂贵的插入,删除,移动内部节点

数据库特定注释

MySQL的

神谕

PostgreSQL的

SQL Server

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



这真是一个方形钉,圆孔问题。

如果关系数据库和SQL是您已经或愿意使用的唯一锤子,那么到目前为止发布的答案已经足够。 但是,为什么不使用旨在处理分层数据的工具? 图形数据库非常适合复杂的分层数据。

与图形数据库解决方案可以轻松解决相同问题相比,关系模型的低效率以及将图形/分层模型映射到关系模型的任何代码/查询解决方案的复杂性都不值得。

考虑将材料清单作为常见的分层数据结构。

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

两个子组件之间的最短路径 :简单图遍历算法。 可接受的路径可以根据标准进行限定。

相似性 :两个程序集之间的相似程度是多少? 对两个子树执行遍历,计算两个子树的交集和并集。 百分比类似的是十字路口除以工会。

传递闭包 :步行子树并总结感兴趣的领域,例如“多少铝在一个子组件中?”

是的,您可以使用SQL和关系数据库解决问题。 但是,如果您愿意使用正确的工具进行工作,则有更好的方法。




邻接模型+嵌套集模型

我为此付出了努力,因为我可以很容易地将新项目插入树中(您只需要一个分支的ID来插入一个新项目),并且可以很快地查询它。

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • 每次你需要任何父母的所有孩子时,你只需查询parent列。
  • 如果您需要任何父母的所有后代,则查询其父母之间的lftrgt之间的lft项目。
  • 如果需要任何节点的所有父节点直到树的根节点,则查询比节点的lftrgtlft并且大于节点的rgt并按parent节点进行排序的项目。

我需要比插入更快地访问和查询树,这就是我选择它的原因

唯一的问题是在插入新项目时修复right列。 那么我为它创建了一个存储过程,并在每次插入一个在我的例子中很少见的新项目时调用它,但它非常快。 我从Joe Celko的书中获得了这个想法,以及存储过程以及我如何使用它的原因在DBA SE中解释https://dba.stackexchange.com/q/89051/41481




Links