SQL 在关系数据库中存储分层数据有哪些选项？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4048151/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What are the options for storing hierarchical data in a relational database?
提问by orangepips
Good Overviews
好的概述
Generally speaking, you're making a decision between fast read times (for example, nested set) or fast write times (adjacency list). Usually, you end up with a combination of the options below that best fit your needs. The following provides some in-depth reading:
一般来说，您要在快速读取时间（例如，嵌套集）或快速写入时间（邻接列表）之间做出决定。通常，您最终会得到以下最适合您需求的选项组合。以下提供了一些深入阅读：
- One more Nested Intervals vs. Adjacency List comparison: the best comparisonof Adjacency List, Materialized Path, Nested Set and Nested Interval I've found.
- Models for hierarchical data: slides with good explanations of tradeoffs and example usage
- Representing hierarchies in MySQL: very good overview of Nested Set in particular
- Hierarchical data in RDBMSs: most comprehensive and well-organized set of links I've seen, but not much in the way of explanation
- 另一个嵌套间隔与邻接列表的比较：我发现的邻接列表、物化路径、嵌套集和嵌套间隔的最佳比较。
- 分层数据模型：幻灯片很好地解释了权衡和示例用法
- 在 MySQL 中表示层次结构：特别是对嵌套集的非常好的概述
- RDBMS 中的分层数据：我见过的最全面和组织良好的链接集，但解释方式不多
Options
选项
Ones I am aware of and general features:
我所知道的和一般特征：
- Adjacency List:
- Columns: ID, ParentID
- Easy to implement.
- Cheap node moves, inserts, and deletes.
- Expensive to find the level, ancestry & descendants, path
- Avoid N+1 via Common Table Expressionsin databases that support them
- Nested Set(a.k.a Modified Preorder Tree Traversal)
- Columns: Left, Right
- Cheap ancestry, descendants
- Very expensive
O(n/2)moves, inserts, deletes due to volatile encoding
- Bridge Table(a.k.a. Closure Table /w triggers)
- Uses separate join table with: ancestor, descendant, depth (optional)
- Cheap ancestry and descendants
- Writes costs
O(log n)(size of subtree) for insert, updates, deletes - Normalized encoding: good for RDBMS statistics & query planner in joins
- Requires multiple rows per node
- Lineage Column(a.k.a. Materialized Path, Path Enumeration)
- Column: lineage (e.g. /parent/child/grandchild/etc...)
- Cheap descendants via prefix query (e.g.
LEFT(lineage, #) = '/enumerated/path') - Writes costs
O(log n)(size of subtree) for insert, updates, deletes - Non-relational: relies on Array datatype or serialized string format
- Nested Intervals
- Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
- Has real/float/decimal representation/precision issues
- Matrix encoding variantadds ancestor encoding (materialized path) for "free", but with added trickiness of linear algebra.
- Flat Table
- A modified Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.
- Cheap to iterate/paginate over
- Expensive move and delete
- Good Use: threaded discussion - forums / blog comments
- Multiple lineage columns
- Columns: one for each lineage level, refers to all the parents up to the root, levels down from the item's level are set to NULL
- Cheap ancestors, descendants, level
- Cheap insert, delete, move of the leaves
- Expensive insert, delete, move of the internal nodes
- Hard limit to how deep the hierarchy can be
- 邻接表：
- 列：ID、ParentID
- 易于实施。
- 廉价的节点移动、插入和删除。
- 寻找级别、祖先和后代、路径的成本很高
- 在支持它们的数据库中通过公共表表达式避免 N+1
- 嵌套集（又名Modified Preorder Tree Traversal）
- 列：左，右
- 廉价的祖先，后代
O(n/2)由于易失性编码，非常昂贵的移动、插入、删除
- 桥接表（又名闭包表/w 触发器）
- 使用单独的连接表：祖先、后代、深度（可选）
- 廉价的祖先和后代
- 写入
O(log n)插入、更新、删除的成本（子树的大小） - 规范化编码：适用于连接中的 RDBMS 统计和查询规划器
- 每个节点需要多行
- 沿袭列（又名物化路径、路径枚举）
- 列：血统（例如/parent/child/grandchild/etc...）
- 通过前缀查询的廉价后代（例如
LEFT(lineage, #) = '/enumerated/path'） - 写入
O(log n)插入、更新、删除的成本（子树的大小） - 非关系：依赖于数组数据类型或序列化字符串格式
- 嵌套间隔
- 类似于嵌套集，但使用实数/浮点数/十进制数，因此编码不会不稳定（移动/插入/删除便宜）
- 有实数/浮点数/十进制表示/精度问题
- 矩阵编码变体为“免费”添加了祖先编码（物化路径），但增加了线性代数的技巧。
- 平桌
- 修改后的邻接列表，为每个记录添加级别和等级（例如排序）列。
- 迭代/分页便宜
- 昂贵的移动和删除
- 很好的用途：线程讨论 - 论坛/博客评论
- 多个世系列
- Columns：每个血统级别一个，指的是所有父级直到根，从项目级别向下的级别设置为NULL
- 便宜的祖先、后代、等级
- 廉价的插入、删除、移动叶子
- 昂贵的插入、删除、移动内部节点
- 层次结构深度的硬限制
Database Specific Notes
数据库特定注释
MySQL
MySQL
Oracle
甲骨文
- Use CONNECT BYto traverse Adjacency Lists
- 使用CONNECT BY遍历邻接表
PostgreSQL
PostgreSQL
- ltree datatypefor Materialized Path
- 物化路径的ltree 数据类型
SQL Server
数据库服务器
- General summary
- 2008 offers HierarchyIddata type appears to help with Lineage Column approach and expand the depth that can be represented.
- 一般摘要
- 2008 年提供的HierarchyId数据类型似乎有助于使用 Lineage Column 方法并扩展可以表示的深度。
回答by Jeff Moden
My favorite answer is as what the first sentence in this thread suggested. Use an Adjacency List to maintain the hierarchy and use Nested Sets to query the hierarchy.
我最喜欢的答案是这个帖子中的第一句话所建议的。使用邻接列表来维护层次结构并使用嵌套集来查询层次结构。
The problem up until now has been that the coversion method from an Adjacecy List to Nested Sets has been frightfully slow because most people use the extreme RBAR method known as a "Push Stack" to do the conversion and has been considered to be way to expensive to reach the Nirvana of the simplicity of maintenance by the Adjacency List and the awesome performance of Nested Sets. As a result, most people end up having to settle for one or the other especially if there are more than, say, a lousy 100,000 nodes or so. Using the push stack method can take a whole day to do the conversion on what MLM'ers would consider to be a small million node hierarchy.
到目前为止的问题是，从邻接列表到嵌套集的覆盖方法非常缓慢，因为大多数人使用称为“推送堆栈”的极端 RBAR 方法进行转换，并且被认为是昂贵的方法达到邻接表维护的简单性和嵌套集的惊人性能的涅磐。结果，大多数人最终不得不满足于其中之一，尤其是当节点数量超过 100,000 个左右时。使用推送堆栈方法可能需要一整天的时间才能对 MLM 人员认为是小型百万节点层次结构进行转换。
I thought I'd give Celko a bit of competition by coming up with a method to convert an Adjacency List to Nested sets at speeds that just seem impossible. Here's the performance of the push stack method on my i5 laptop.
我想我会给 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'
And here's the duration for the new method (with the push stack method in parenthesis).
这是新方法的持续时间（括号中是推栈方法）。
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!!!)
Yes, that's correct. 1 million nodes converted in less than a minute and 100,000 nodes in under 4 seconds.
对，那是正确的。不到一分钟转换了 100 万个节点，不到 4 秒转换了 100,000 个节点。
You can read about the new method and get a copy of the code at the following URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/
您可以在以下 URL 中阅读有关新方法的信息并获取代码副本。 http://www.sqlservercentral.com/articles/Hierarchy/94040/
I also developed a "pre-aggregated" hierarchy using similar methods. MLM'ers and people making bills of materials will be particularly interested in this article. http://www.sqlservercentral.com/articles/T-SQL/94570/
我还使用类似的方法开发了一个“预聚合”层次结构。传销人员和制作物料清单的人将对本文特别感兴趣。 http://www.sqlservercentral.com/articles/T-SQL/94570/
If you do stop by to take a look at either article, jump into the "Join the discussion" link and let me know what you think.
如果您确实停下来看看任何一篇文章，请跳到“加入讨论”链接，让我知道您的想法。
回答by CesarGon
This is a very partial answer to your question, but I hope still useful.
这是对您问题的非常部分的回答，但我希望仍然有用。
Microsoft SQL Server 2008 implements two features that are extremely useful for managing hierarchical data:
Microsoft SQL Server 2008 实现了两个对管理分层数据非常有用的功能：
- the HierarchyIddata type.
- common table expressions, using the withkeyword.
- 所述HierarchyId的数据类型。
- 公共表表达式，使用with关键字。
Have a look at "Model Your Data Hierarchies With SQL Server 2008"by Kent Tegels on MSDN for starts. See also my own question: Recursive same-table query in SQL Server 2008
看看Kent Tegels 在 MSDN上的“Model Your Data Hierarchies With SQL Server 2008”作为开始。另请参阅我自己的问题：SQL Server 2008 中的递归同表查询
回答by TMS
This design was not mentioned yet:
这个设计还没有提到：
Multiple lineage columns
多个世系列
Though it has limitations, if you can bear them, it's very simple and very efficient. Features:
虽然它有局限性，但如果你能忍受，它是非常简单和非常有效的。特征：
- Columns: one for each lineage level, refers to all the parents up to the root, levels below the current items' level are set to 0 (or NULL)
- There is a fixed limit to how deep the hierarchy can be
- Cheap ancestors, descendants, level
- Cheap insert, delete, move of the leaves
- Expensive insert, delete, move of the internal nodes
- Columns：每个血统级别一个，指的是直到根的所有父项，当前项级别以下的级别设置为0（或NULL）
- 层次结构的深度有一个固定的限制
- 便宜的祖先、后代、等级
- 廉价的插入、删除、移动叶子
- 昂贵的插入、删除、移动内部节点
Here follows an example - taxonomic tree of birds so the hierarchy is Class/Order/Family/Genus/Species - species is the lowest level, 1 row = 1 taxon (which corresponds to species in the case of the leaf nodes):
下面是一个示例 - 鸟类的分类树，因此层次结构是类/目/科/属/种 - 物种是最低级别，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 ''
);
and the example of the data:
以及数据示例：
+---------+---------+---------+----------+---------+-------------------------------+
| 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 |
This is great because this way you accomplish all the needed operations in a very easy way, as long as the internal categories don't change their level in the tree.
这很棒，因为这样您就可以以非常简单的方式完成所有需要的操作，只要内部类别不改变它们在树中的级别。
回答by azerafati
Adjacency Model + Nested Sets Model
邻接模型+嵌套集模型
I went for it because I could insert new items to the tree easily (you just need a branch's id to insert a new item to it) and also query it quite fast.
我选择它是因为我可以轻松地将新项目插入到树中（你只需要一个分支的 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 |
+-------------+----------------------+--------+-----+-----+
- Every time you need all children of any parent you just query the
parentcolumn. - If you needed all descendants of any parent you query for items which have their
lftbetweenlftandrgtof parent. - If you needed all parents of any node up to the root of the tree, you query for items having
lftlower than the node'slftandrgtbigger than the node'srgtand sort the byparent.
- 每次您需要任何父母的所有孩子时，您只需查询该
parent列。 - 如果您需要任何父级的所有后代，您可以查询具有父级
lft之间lft和rgt父级之间的项目。 - 如果您需要任何节点的所有父节点直到树的根，您可以查询
lft低于节点lft和rgt大于节点的项目rgt并按 排序parent。
I needed to make accessing and querying the tree faster than inserts, that's why I chose this
我需要比插入更快地访问和查询树，这就是我选择这个的原因
The only problem is to fix the leftand rightcolumns when inserting new items. well I created a stored procedure for it and called it every time I inserted a new item which was rare in my case but it is really fast.
I got the idea from the Joe Celko's book, and the stored procedure and how I came up with it is explained here in DBA SE
https://dba.stackexchange.com/q/89051/41481
唯一的问题是在插入新项目时修复left和right列。好吧，我为它创建了一个存储过程，并在每次插入一个新项目时调用它，这在我的情况下很少见，但它真的很快。我从 Joe Celko 的书中得到了这个想法，DBA SE https://dba.stackexchange.com/q/89051/41481 中解释了存储过程以及我是如何想出它的
回答by Adam Sanderson
If your database supports arrays, you can also implement a lineage column or materialized path as an array of parent ids.
如果您的数据库支持数组，您还可以将谱系列或物化路径实现为父 ID 数组。
Specifically with Postgres you can then use the set operators to query the hierarchy, and get excellent performance with GIN indices. This makes finding parents, children, and depth pretty trivial in a single query. Updates are pretty manageable as well.
特别是使用 Postgres，您可以使用集合运算符来查询层次结构，并使用 GIN 索引获得出色的性能。这使得在单个查询中查找父项、子项和深度变得非常简单。更新也很容易管理。
I have a full write up of using arrays for materialized pathsif you're curious.
如果你很好奇，我有一篇关于将数组用于物化路径的完整文章。
回答by djhallx
This is really a square peg, round hole question.
这真的是一个方钉圆孔问题。
If relational databases and SQL are the only hammer you have or are willing to use, then the answers that have been posted thus far are adequate. However, why not use a tool designed to handle hierarchical data? Graph databaseare ideal for complex hierarchical data.
如果关系数据库和 SQL 是您拥有或愿意使用的唯一锤子，那么到目前为止发布的答案就足够了。但是，为什么不使用旨在处理分层数据的工具呢？图数据库非常适合复杂的分层数据。
The inefficiencies of the relational model along with the complexities of any code/query solution to map a graph/hierarchical model onto a relational model is just not worth the effort when compared to the ease with which a graph database solution can solve the same problem.
与图数据库解决方案可以轻松解决相同问题相比，关系模型的低效率以及将图/分层模型映射到关系模型的任何代码/查询解决方案的复杂性都不值得付出努力。
Consider a Bill of Materials as a common hierarchical data structure.
将物料清单视为常见的分层数据结构。
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: Simple graph traversal algorithm. Acceptable paths can be qualified based on criteria.
两个子组件之间的最短路径：简单的图遍历算法。可接受的路径可以根据标准进行限定。
Similarity: What is the degree of similarity between two assemblies? Perform a traversal on both sub-trees computing the intersection and union of the two sub-trees. The percent similar is the intersection divided by the union.
相似度：两个程序集之间的相似度是多少？对两个子树执行遍历，计算两个子树的交集和并集。相似百分比是交集除以并集。
Transitive Closure: Walk the sub-tree and sum up the field(s) of interest, e.g. "How much aluminum is in a sub-assembly?"
传递闭包：遍历子树并总结感兴趣的字段，例如“子组件中有多少铝？”
Yes, you can solve the problem with SQL and a relational database. However, there are much better approaches if you are willing to use the right tool for the job.
是的，您可以使用 SQL 和关系数据库来解决这个问题。但是，如果您愿意使用正确的工具来完成工作，还有更好的方法。
回答by IVO GELOV
I am using PostgreSQL with closure tables for my hierarchies. I have one universal stored procedure for the whole database:
我正在为我的层次结构使用带有闭包表的 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 .id,.id,0 UNION ALL
SELECT .id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=.' || TG_ARGV[2] USING NEW;
ELSE
-- EXECUTE does not support conditional statements inside
EXECUTE 'SELECT .' || TG_ARGV[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] || ' = .' || TG_ARGV[2]
|| ' WHERE id=.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
|| TG_ARGV[1] || ' WHERE child_id=.' || TG_ARGV[2] || ' AND ancestor_id=.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 = .id)
AND ancestor_id IN
(SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = .id AND ancestor_id <> .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=.id) AS child
CROSS JOIN
(SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=.'
|| TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
END IF;
END IF;
RETURN NULL;
END;
$_$;
Then for each table where I have a hierarchy, I create a trigger
然后对于我有层次结构的每个表，我创建一个触发器
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');
For populating a closure table from existing hierarchy I use this stored procedure:
为了从现有层次结构填充闭包表，我使用这个存储过程：
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;
$$;
Closure tables are defined with 3 columns - ANCESTOR_ID, DESCENDANT_ID, DEPTH. It is possible (and I even advice) to store records with same value for ANCESTOR and DESCENDANT, and a value of zero for DEPTH. This will simplify the queries for retrieval of the hierarchy. And they are very simple indeed:
闭包表由 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;
