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

良好的概述

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

• 多一个嵌套间隔与邻接表比较 ：我发现的邻接表，物化path，嵌套集和嵌套间隔的最佳比较 。
• 分级数据的模型 ：幻灯片中有很好的权衡解释和示例用法
• 在MySQL中表示层次结构 ：特别是对嵌套集的很好的概述
• 关系数据库系统中的分层数据 ：我所见过的最全面和最有条理的链接集，但对解释的方式并不多

选项

我知道的一般特征：

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

数据库特定注释

MySQL的

• 使用邻接列表的会话variables

神谕

• 使用CONNECT BY遍历邻接列表

PostgreSQL的

• 物化path的ltree数据types

SQL Server

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

Answer 1

即使所有三大供应商都实现了recursionWITH子句，这仍然是一个有趣的问题。 我build议不同的读者会喜欢不同的答案。

1. 由Troels Arvin提供的综合清单 。
2. 由于缺乏竞争，Joe Celko的介绍性教科书“Trees and Hierarchies in SQL for Smarties”确实被认为是经典。
3. 回顾各种树编码，重点是嵌套间隔 。

Answer 2

关于这个问题的一些文章来自我的博客：

• 邻接列表与嵌套集：MySQL
• 邻接列表与嵌套集：PostgreSQL
• 邻接列表与嵌套集：Oracle

• 邻接列表与嵌套集：SQL Server

• MySQL中的分层查询（在MySQL中查询邻接列表）

Answer 3

Joe Celko在SQL Trees＆Hiearichies上写了这本书

这是第一版。 看Bob的评论第二版。

Answer 4

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

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

我想我会给Celko一点点的竞争，想出一个方法来把一个邻接表转换成Nested套接字的速度，这似乎是不可能的。 以下是我的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/

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

Answer 5

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

Microsoft SQL Server 2008实现了两个对pipe理分层数据非常有用的function：

• HierarchyId数据types。
• 公用表expression式，使用with关键字。

查看Kent Tegels在MSDN上为“开始时使用SQL Server 2008build模数据层次结构” 。 另请参阅我自己的问题： SQL Server 2008中的recursion同表查询

Answer 6

这个devise还没有提到：

多谱系列

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

• 列：每个血统级别的一个，指的是所有的父母直到根，当前项目的水平以下的级别被设置为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 | 

这很好，因为这样你可以非常容易地完成所有需要的操作，只要内部类别不改变它们在树中的级别即可。

Answer 7

邻接模型+嵌套集模型

我去了，因为我可以很容易地插入新的项目（你只需要一个分支的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和rgt低lft项目，并且要比parent节点的rgt大。

我需要比插入更快地访问和查询树，这就是为什么我select这个

唯一的问题是在插入新项目时修正right列。 那么我为它创build了一个存储过程，并在每次插入一个在我的例子中很less使用的新项目时调用它，但是它非常快。 我从Joe Celko的书中得到了这个想法，以及存储过程，以及我如何使用它，在DBA SE中解释https://dba.stackexchange.com/q/89051/41481

Answer 8

如果您的数据库支持数组，则还可以将父系列或物化path实施为父数据标识的数组。

特别是使用Postgres，您可以使用集合运算符来查询层次结构，并使用GIN索引获得优异的性能。 这使得在单个查询中find父母，孩子和深度非常微不足道。 更新也相当易于pipe理。

如果您好奇，我已经写了一些使用物理path的数组 。

Answer 9

这实在是一个方形钉，圆孔的问题。

如果关系型数据库和SQL是你已经或者愿意使用的唯一的锤子，那么到目前为止已经发布的答案是足够的。 但是，为什么不使用devise来处理分层数据的工具呢？ graphics数据库是复杂分层数据的理想select。

与graphics数据库解决scheme可以轻松解决相同问题相比，关系模型的低效率以及将graphics/分层模型映射到关系模型上的任何代码/查询解决scheme的复杂性都不值得。

考虑将材料清单作为常见的分层数据结构。

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

两个子组件之间的最短path ：简单图遍历algorithm。 可接受的path可以根据标准进行限定。

相似性 ：两个程序集之间的相似程度是多less？ 对两个子树执行遍历，计算两个子树的交集和联合。 百分比类似的是十字路口除以工会。

传递闭包 ：走子树并总结感兴趣的领域，例如“多less铝在一个子assembly中？

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

Answer 10

对于更复杂的层次结构（如LDAP树），OpenLDAP-MySQL集群体系结构在2009年MySQL用户大会上提出。

http://en.oreilly.com/mysql2009/public/schedule/detail/6219

这与上面显示的“Multiple lineage columns”scheme很相似。

Answer 11

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

然后对于每个我有层次结构的表，我创build一个触发器

 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。 有可能（甚至build议）为ANCESTOR和DESCENDANT存储具有相同值的logging，深度值为零。 这将简化对层次结构检索的查询。 他们确实很简单：

 -- 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; 

Answer 12

这是我个人最喜欢的一个很好的例子，桥表（或封闭表）。