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

 

良好的概述

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

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

    • 选项

    我知道的和一般特征：

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

    • 数据库特定注释

    MySQL的

  • 使用邻接列表的会话变量

    • 神谕

  • 使用CONNECT BY遍历邻接列表

    • PostgreSQL的

  • 物化路径的ltree数据类型

    • SQL Server

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

    • 我最喜欢的答案是这个主题中的第一句话提示。 使用邻接列表来维护层次结构并使用嵌套集来查询层次结构。

    迄今为止的问题是，从Adjacecy List到Nested Sets的覆盖方法一直非常缓慢，因为大多数人使用称为“Push Stack”的极端RBAR方法进行转换，并且被认为是成本昂贵的方式通过邻接列表以及Nested Sets的卓越性能来达到Nirvana的简单维护。 结果，大多数人最终不得不为其中一个或另一个而定居，特别是如果有不止十万个节点等左右的情况。 使用推式堆栈方法可能需要一整天时间来对MLM人员认为是小型百万节点层级的转换进行转换。

    我想我会给Celko一点点竞争力，想出一种将邻接列表转换成嵌套集合的方法，其速度看起来不可能。 以下是我的i5笔记本电脑上的push stack方法的性能。 

    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/

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

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

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

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

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

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

    此设计尚未提及：

    多谱系列

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

  • 列：每个血统级别的一个，指的是所有的父母直到根，当前项目的水平以下的级别被设置为NULL
  • 限制层次结构的深度
  • 廉价的祖先，后代，水平
  • 廉价的插入，删除，移动的叶子
  • 昂贵的插入，删除，移动内部节点

    • 下面是一个例子 - 鸟类的分类树，所以层次结构是类别/顺序/家族/属/物种 - 物种是最低级别，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                   |

    这非常棒，因为只要内部类别不会在树中改变它们的级别，您就可以非常简单的方式完成所有需要的操作。

    链接地址: http://www.djcxy.com/p/37767.html

    上一篇: What are the options for storing hierarchical data in a relational database?

    下一篇: PHP expresses two different strings to be the same