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

良好的概述

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

选项

我所知道的和一般特征：

  1. 邻接表：
  • 列：ID，父母ID
  • 易于实施。
  • 廉价的节点移动、插入和删除。
  • 寻找等级，祖先和后代，路径的成本很高
  • 在支持它们的数据库中通过常用表表达式避免N+1
  1. 嵌套集合（a. k. a修改的预排序树遍历）
  • 列：左，右
  • 廉价的祖先，后代
  • 由于易失性编码，非常昂贵的O(n/2)移动、插入、删除
  1. 桥接表（又名闭包表 /w触发器）
  • 使用具有祖先、后代、深度的单独连接表（可选）
  • 廉价的祖先和后代
  • 写入成本O(log n)（子树的大小）用于插入、更新、删除
  • 标准化编码：适用于连接中的RDBMS统计和查询规划器
  • 每个节点需要多行
  1. 宗族柱（又名物化路径，路径枚举）
  • 列：血统（例如/父母/子女/孙子/等…）
  • 通过前缀查询的廉价后代（例如LEFT(lineage, #) = '/enumerated/path'）
  • 写入成本O(log n)（子树的大小）用于插入、更新、删除
  • 非关系：依赖于数组数据类型或序列化字符串格式
  1. 嵌套区间
  • 类似于嵌套集，但使用true/浮点数/十进制，因此编码不易失性（廉价的移动/插入/删除）
  • 有真实/浮点数/十进制表示/精度问题
  • 矩阵编码变体为“自由”添加了祖先编码（物化路径），但增加了线性代数的复杂性。
  1. 平板
  • 修改后的邻接列表，向每个记录添加级别和等级（例如排序）列。
  • 廉价的迭代/分页
  • 昂贵的移动和删除
  • 良好使用：线程讨论-论坛/博客评论
  1. 多个沿袭列
  • 列：每个血统级别一个，指的是所有的父母，直到根，从项目的级别向下的级别设置为NULL
  • 便宜的祖先，后代，水平
  • 廉价的插入、删除、移动叶子
  • 内部节点的昂贵插入、删除、移动
  • 严格限制等级制度可以有多深

数据库特定注释

mysql

Oracle

PostgreSQL

SQL服务器

  • 概述
  • 2008提供了层级名称数据类型，似乎有助于使用沿袭列方法并扩展可以表示的深度。
314788 次浏览
小开

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

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

看看Kent Tegels在MSDN上的“使用SQLServer 2008建模您的数据层次结构”开始。另见我自己的问题：SQLServer 2008中的递归同表查询

小开

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

到目前为止的问题是，从AdJacecy List到嵌套集的coversion方法非常慢，因为大多数人使用被称为“Push Stack”的极端RBAR方法来进行转换，并且被认为是达到邻接列表维护简单性和嵌套集惊人性能的涅槃的方式昂贵。结果，大多数人最终不得不满足于一种或另一种，特别是如果有超过，比如说，糟糕的100,000个节点左右。使用推送堆栈方法可能需要一整天的时间来在MLM的人认为是一百万个节点的小层次结构上进行转换。

我想我会给Celko一点竞争，想出一种方法，以看似不可能的速度将邻接列表转换为嵌套集。这是我的i5笔记本电脑上推送堆栈方法的性能。

Duration for     1,000 Nodes = 00:00:00:870Duration 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万节点在不到一分钟的时间内转换，100,000个节点在不到4秒的时间内转换。

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

我还使用类似的方法开发了一个“预聚合”层次结构。MLM'ers和制作物料清单的人会对这篇文章特别感兴趣。http://www.sqlservercentral.com/articles/T-SQL/94570/

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

小开

如果您的数据库支持数组，您还可以将沿袭列或物化路径实现为父id数组。

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

如果你好奇，我有一个完整的使用物化路径的数组的文章。

小开

这个设计还没有提到：

多个沿袭列

虽然它有局限性，如果你能忍受它们，它是非常简单和非常有效的。特点：

  • 列：每个血统级别一个，指的是所有的父级到根，低于当前项目级别的级别设置为0（或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                   |

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

小开

这真是一个方方正正，圆圆的问题。

如果关系数据库和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列。
  • 如果您需要任何父级的所有后代，您可以查询其lft介于父级的lft和rgt之间的项。
  • 如果您需要任何节点的所有父节点，直到树的根，您可以查询lft低于节点的lft和rgt大于节点的rgt的项目，并按parent进行排序。

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

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

小开

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

CREATE FUNCTION nomen_tree() RETURNS triggerLANGUAGE plpgsqlAS $_$DECLAREold_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' THENEXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth)SELECT $1.id,$1.id,0 UNION ALLSELECT $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 insideEXECUTE '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) THENEXECUTE '-- prevent cycles in the treeUPDATE ' || 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 descendantsDELETE 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 childCROSS 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 voidLANGUAGE plpgsqlAS $$BEGINEXECUTE '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 ALLSELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS tJOIN tree ON child_id = ' || fld_parent || ')SELECT * FROM tree;';END;$$;

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

-- get all descendantsSELECT 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 descendantsSELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;-- get all ancestorsSELECT 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 childrenSELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

提交答案