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

良好的概述

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

选件

我知道的和一般功能:

  1. 邻接表
    • 列:ID,ParentID
    • 易于实现。
    • 廉价节点移动,插入和删除。
    • 昂贵的查找级别,祖先和后代,路径
    • 在支持 N + 1 的数据库中通过公用表表达式避免 N + 1
  2. 嵌套集 (又名修改后的预排序树遍历
    • 列:左,右
    • 廉价祖先,后裔
    • 由于易失性编码,非常昂贵的O(n/2)移动,插入,删除
  3. 桥接表 (又名闭包表 / w 触发器
    • 使用单独的联接表,并带有:祖先,后代,深度(可选)
    • 便宜的祖先和后裔
    • 写入成本O(log n) (子树的大小)以进行插入,更新,删除
    • 标准化编码:适合联接中的 RDBMS 统计和查询计划程序
    • 每个节点需要多行
  4. 沿袭列 (又名物化路径 ,路径枚举)
    • 栏:沿袭(例如 / parent / child / grandchild / etc ...)
    • 通过前缀查询的廉价后代(例如, LEFT(lineage, #) = '/enumerated/path'
    • 写入成本O(log n) (子树的大小)以进行插入,更新,删除
    • 非关系:依赖于数组数据类型或序列化的字符串格式
  5. 嵌套间隔
    • 类似于嵌套集,但具有实数 / 浮点数 / 十进制数,因此编码不会不稳定(廉价的移动 / 插入 / 删除)
    • 有实数 / 浮点数 / 小数表示 / 精度问题
    • 矩阵编码变体为 “自由” 添加了祖先编码(物化路径),但增加了线性代数的技巧。
  6. 平面桌
    • 修改后的邻接表,将 “级别” 和 “等级”(例如,排序)列添加到每个记录。
    • 便宜地迭代 / 分页
    • 昂贵的移动和删除
    • 很好的用途:主题讨论 - 论坛 / 博客评论
  7. 多个谱系列
    • 列:每个谱系级别都有一列,指的是直到根目录的所有父级,从项的级别向下的级别都设置为 NULL
    • 廉价祖先,后代,等级
    • 便宜的插入,删除,移动叶子
    • 内部节点的昂贵插入,删除,移动
    • 严格限制层次结构的深度

数据库特定说明

的 MySQL

甲骨文

PostgreSQL 的

SQL 服务器

  • 一般总结
  • 2008 年提供的HierarchyId数据类型似乎有助于沿袭列方法并扩展了可以表示的深度。

答案

我最喜欢的答案是该线程的第一句话建议的内容。使用邻接列表维护层次结构,并使用嵌套集查询层次结构。

迄今为止的问题一直是,从邻接表到嵌套集的掩盖方法非常慢,因为大多数人使用称为 “推栈” 的极端 RBAR 方法进行转换,并被认为是昂贵的方法。通过邻接表和嵌套集的出色性能达到维护简单性的必杀技。结果,大多数人最终不得不适应一个或另一个,特别是如果存在超过 100,000 个左右的糟糕节点。使用推栈方法可能需要一整天的时间来完成 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!!!)

对,那是正确的。在不到一分钟的时间内转换了 100 万个节点,在不到 4 秒的时间内转换了 100,000 个节点。

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

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

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

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

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

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

此设计尚未提及:

多个谱系列

尽管它有局限性,但如果您能忍受的话,它非常简单而且非常有效。特征:

  • 列:每个谱系级别一列,指的是直到根目录的所有父级,当前项目级别以下的级别设置为 0(或 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                   |

这非常好,因为只要内部类别不更改其在树中的级别,就可以通过这种方式非常轻松地完成所有必需的操作。

邻接模型 + 嵌套集模型

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

我需要比插入更快地访问和查询树,这就是为什么我选择了这个

唯一的问题是在插入新项目时修复leftright列。好吧,我为此创建了一个存储过程,并在每次插入一个新项目时都调用它,这种情况对我来说是很少见的,但确实非常快。我从 Joe Celko 的书中得到了这个主意,并且在 DBA SE https://dba.stackexchange.com/q/89051/41481 中解释了存储过程以及如何提出它。

如果您的数据库支持数组,则还可以将沿袭列或实例化路径实现为父 ID 数组。

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

如果您好奇的话,我已经写了一篇关于将数组用于物化路径的完整文章。

这确实是一个方钉,圆孔的问题。

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

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

将物料清单视为常见的分层数据结构。

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

两个子装配之间的最短路径 :简单的图形遍历算法。可以根据条件限定可接受的路径。

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

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

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

我正在使用带有闭合表的 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;