在关系数据库中存储分层数据有哪些选项？-Java 学习之路

1117

Good Overviews

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

One more Nested Intervals vs. Adjacency List comparison：我发现的邻接列表，物化路径，嵌套集和嵌套间隔的最佳比较 .
Models for hierarchical data：幻灯片中有很好的解释权衡和示例用法
Representing hierarchies in MySQL：特别是对嵌套集的非常好的概述
Hierarchical data in RDBMSs：我见过的最全面，组织良好的一系列链接，但解释方式不多

Options

我知道和一般的功能：

Adjacency List：
列：ID，ParentID
易于实施 .
便宜节点移动，插入和删除 .
昂贵的找到水平，祖先和后代，路径
在支持它们的数据库中通过Common Table Expressions避免N 1
Nested Set（a.k.a Modified Preorder Tree Traversal）
列：左，右
便宜的血统，后代
非常昂贵 O(n/2) 由于易失性编码而移动，插入，删除
Bridge Table（a.k.a . Closure Table /w triggers）
使用单独的连接表：ancestor，descendant，depth（optional）
便宜的血统和后代
为插入，更新，删除写入成本 O(log n) （子树的大小）
规范化编码：适用于连接中的RDBMS统计信息和查询规划器
每个节点需要多行
Lineage Column（a.k.a . Materialized Path，Path Enumeration）
专栏：血统（例如/ parent / child / grandchild / etc ......）
通过前缀查询的廉价后代（例如 LEFT(lineage, #) = '/enumerated/path' ）
为插入，更新，删除写入成本 O(log n) （子树的大小）
非关系型：依赖于Array数据类型或序列化字符串格式
Nested Intervals
与嵌套集类似，但使用实数/浮点数/小数，以便编码不易变（廉价的移动/插入/删除）
具有实/浮点/十进制表示/精度问题
Matrix encoding variant为"free"添加了祖先编码（物化路径），但增加了线性代数的诡计 .
Flat Table
修改后的邻接列表，为每条记录添加级别和排名（例如排序）列 .
便宜迭代/分页
昂贵的移动和删除
好用：线程讨论 - 论坛/博客评论
Multiple lineage columns
列：每个谱系级别一个，指向根目录下的所有父级，从项目级别向下的级别设置为NULL
便宜的祖先，后代，水平
廉价插入，删除，移动叶子
昂贵的插入，删除，移动内部节点
层次结构有多深的硬限制

Database Specific Notes

MySQL的

Use session variables for Adjacency List

神谕

使用CONNECT BY遍历邻接列表

PostgreSQL的

物化路径

ltree datatype

SQL Server

General summary
2008提供HierarchyId数据类型似乎有助于Lineage Column方法并扩展可以表示的深度 .

7 回答

41
这实际上是一个方形钉，圆孔问题 .

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

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

将物料清单视为通用的分层数据结构 .
```
class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};
```
Shortest path between two sub-assemblies ：简单的图形遍历算法 . 可接受的路径可以根据标准进行限定 .

Similarity ：两个组件之间的相似程度是多少？在两个子树上执行遍历，计算两个子树的交集和并集 . 相似的百分比是交叉点除以并集 .

Transitive Closure ：遍历子树并总结感兴趣的字段，例如"How much aluminum is in a sub-assembly?"

是的，您可以使用SQL和关系数据库解决问题 . 但是，如果您愿意使用正确的工具来完成工作，那么有更好的方法 .
回复于 2024-04-29T06:03:16+08:00
11
这是对你的问题的非常局部的答案，但我希望仍然有用 .

Microsoft SQL Server 2008实现了两个对管理分层数据非常有用的功能：
- HierarchyId数据类型 .
- 公用表表达式，使用with关键字 .
在MSDN上看看Kent Tegels的"Model Your Data Hierarchies With SQL Server 2008"开始 . 另见我自己的问题：Recursive same-table query in SQL Server 2008
回复于 2024-04-29T06:03:16+08:00
23
邻接模型嵌套集模型

我之所以这样做是因为我可以轻松地将新项目插入到树中（您只需要一个分支的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 和 rgt 之间具有 lft 的项目 .
- 如果需要任何节点的所有父节点直到树的根节点，则查询 lft 低于节点 lft 和 rgt 大于节点 rgt 的项目，并按 parent 排序 .
I needed to make accessing and querying the tree faster than inserts, that's why I chose this

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

我正在使用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;

回复于 2024-04-29T06:03:16+08:00

16

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

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

如果你很好奇，我会完整地写一下使用arrays for materialized paths .

回复于 2024-04-29T06:03:16+08:00

这个设计还没有提到：

多个谱系列

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

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

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

回复于 2024-04-29T06:03:16+08:00

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

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

我还使用类似的方法开发了一个"pre-aggregated"层次结构 . MLM'ers和制作材料清单的人将对本文特别感兴趣 . http://www.sqlservercentral.com/articles/T-SQL/94570/

如果你停下来看看这两篇文章，请跳到“加入讨论”链接，让我知道你的想法 .
回复于 2024-04-29T06:03:16+08:00

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

7 回答

邻接模型嵌套集模型

多个谱系列

相关问题