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


好的概述

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

选项

我知道和一般的功能:

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

数据库特定说明

MySQL的

神谕

  • 使用 连接 遍历邻接列表

PostgreSQL的

SQL Server

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

1063
2017-10-29 00:34


起源


是。 Libkin等人的“在SQL中保持图形的传递闭包”是关于该主题的经典论文。 - Tegiri Nenashi
根据 slideshare.net/billkarwin/sql-antipatterns-strike-back 第77页, Closure Tables 优于 Adjacency List, Path Enumeration 和 Nested Sets 在易用性方面(我也猜测性能)。 - Gili
“常规摘要”的MSDN链接不再显示该文章。它是在2008年9月版的MSDN杂志中,您可以将其作为CHM文件下载,或通过以下网址存档: web.archive.org/web/20080913041559/http://msdn.microsoft.com:80/... - David Kemp
那些日子关闭选民只读标题。没有努力尝试理解问题的范围而他们没有阅读答案,当你不理解某个话题时,真的会尝试使用更多的SKIP按钮 - jean
这个问题太深了,我想知道他们在哪里可以放这样的东西,肯定它可能很广泛,但考虑到它的深度没什么。无论如何投票重新开放 - Viney


答案:


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

到目前为止的问题是从邻接列表到嵌套集的转换方法一直非常缓慢,因为大多数人使用称为“推送栈”的极端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/

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


32





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

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

看一下 “使用SQL Server 2008建模数据层次结构” 作者:Kent Tegels在MSDN上的首发。另见我自己的问题: SQL Server 2008中的递归同表查询


21



有趣的是,HierarchyId并不知道那个: msdn.microsoft.com/en-us/library/bb677290.aspx - orangepips
确实。我使用了很多递归分层数据,我发现常用表表达式非常有用。看到 msdn.microsoft.com/en-us/library/ms186243.aspx 介绍。 - CesarGon


这个设计还没有提到:

多个谱系列

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

  • 列:每个谱系级别一个,指向根目录下的所有父级,低于当前项级别的级别设置为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                   |

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


20





邻接模型+嵌套集模型

我之所以这样做是因为我可以轻松地将新项目插入到树中(您只需要一个分支的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 柱。
  • 如果您需要任何父级的所有后代,则查询具有其子项的项目 lft 之间 lft 和 rgt 父母
  • 如果您需要任何节点的所有父节点直到树的根,则查询具有的项目 lft 低于节点的 lft 和 rgt 大于节点的 rgt 并按顺序排序 parent

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

唯一的问题是修复 left 和 right 插入新项目时的列。好吧,我为它创建了一个存储过程,并在每次插入一个新项目时调用它,这在我的情况下很少见,但它真的很快。 我从Joe Celko的书中得到了这个想法,并且在DBA SE中解释了存储过程以及我如何想出它 https://dba.stackexchange.com/q/89051/41481


13



+1这是一种合法的方法。根据我自己的经验,关键是决定在发生大型更新操作时是否可以使用脏读。如果没有,它就成了一个问题,或者阻止人们直接查询表并始终通过API-DB sprocs / functions或code。 - orangepips
这是一个有趣的解决方案;但是,我不确定查询父列在尝试寻找孩子时确实提供了任何主要优势 - 这就是为什么我们首先要有左右列。 - Thomas
@Thomas,有区别 children 和 descendants。 left 和 right 用来找到后代。 - azerafati


如果数据库支持数组,则还可以将lineage列或实现路径实现为父ID数组。

特别是使用Postgres,您可以使用set运算符来查询层次结构,并使用GIN索引获得出色的性能。这使得在单个查询中查找父母,子女和深度非常简单。更新也非常易于管理。

我有一个完整的使用说明 物化路径的数组 如果你很好奇


10





这实际上是一个方形钉,圆孔问题。

如果关系数据库和SQL是您拥有或愿意使用的唯一锤子,那么到目前为止已发布的答案就足够了。但是,为什么不使用专门用于处理分层数据的工具呢? 图数据库 是复杂的分层数据的理想选择。

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

将物料清单视为通用的分层数据结构。

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

相似:两个组件之间的相似程度是多少?在两个子树上执行遍历,计算两个子树的交集和并集。相似的百分比是交叉点除以并集。

传递闭包:遍历子树并总结感兴趣的字段,例如: “子组件中有多少铝?”

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


7



如果用例展示或更好地对比,如何使用SPARQL而不是RDBMS中的SQL查询图形数据库,这个答案将会非常有用。 - orangepips
SPARQL与RDF数据库相关,RDF数据库是更大的图形数据库域的子类。我使用InfiniteGraph,它不是RDF数据库,目前不支持SPARQL。 InfiniteGraph支持几种不同的查询机制:(1)用于设置视图,过滤器,路径限定符和结果处理程序的图形导航API,(2)复杂的图形路径模式匹配语言,以及(3)Gremlin。 - djhallx


我正在使用PostgreSQL和我的层次结构的闭包表。 我有一个用于整个数据库的通用存储过程:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

然后,对于每个具有层次结构的表,我创建一个触发器

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

为了从现有层次结构填充闭包表,我使用此存储过程:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

闭包表定义为3列 - ANCESTOR_ID,DESCENDANT_ID,DEPTH。有可能(我甚至建议)为ANCESTOR和DESCENDANT存储具有相同值的记录,并为DEPTH存储零值。这将简化检索层次结构的查询。它们确实非常简单:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

4