SQL - 如何存储和导航层次结构？

SQL - How to store and navigate hierarchies?

提问by realcals

What are the ways that you use to model and retrieve hierarchical info in a database?

您使用哪些方法对数据库中的分层信息进行建模和检索？

采纳答案by andy47

The definitive pieces on this subject have been written by Joe Celko, and he has worked a number of them into a book called Joe Celko's Trees and Hierarchies in SQL for Smarties.

关于这个主题的权威性文章由 Joe Celko 编写，他将其中的一些内容编入了一本名为 Joe Celko 的 SQL for Smarties 中的树和层次结构的书中。

He favours a technique called directed graphs. An introduction to his work on this subject can be found here

他赞成一种称为有向图的技术。可以在这里找到他在这个主题上的工作介绍

回答by markus

I like the Modified Preorder Tree Traversal Algorithm. This technique makes it very easy to query the tree.

我喜欢修改的预序树遍历算法。这种技术使得查询树变得非常容易。

But here is a list of links about the topic which I copied from the Zend Framework (PHP) contributors webpage (posted there by Posted by Laurent Melmoux at Jun 05, 2007 15:52).

但这里是我从 Zend Framework (PHP) 贡献者网页（由 Laurent Melmoux 于 2007 年 6 月 5 日 15:52 发布）复制的有关该主题的链接列表。

Many of the links are language agnostic:

许多链接是语言不可知的：

There is 2 main representations and algorithms to represent hierarchical structures with databases :

有两种主要的表示和算法来表示数据库的层次结构：

• nested set also known as modified preorder tree traversal algorithm
• adjacency list model

• 嵌套集也称为修改前序树遍历算法
• 邻接表模型

It's well explained here:

这里很好解释：

• http://www.sitepoint.com/article/hierarchical-data-database
• Managing Hierarchical Data in MySQL
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

• http://www.sitepoint.com/article/hierarchical-data-database
• 在 MySQL 中管理分层数据
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

Here are some more links that I've collected:

以下是我收集的更多链接：

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

adjacency list model

邻接表模型

• http://www.sqlteam.com/item.asp?ItemID=8866

• http://www.sqlteam.com/item.asp?ItemID=8866

nested set

嵌套集

• http://www.sqlsummit.com/AdjacencyList.htm
• http://www.edutech.ch/contribution/nstrees/index.php
• http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
• http://www.dbmsmag.com/9604d06.html
• http://en.wikipedia.org/wiki/Tree_traversal
• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html(applet java montrant le fonctionnement )

• http://www.sqlsummit.com/AdjacencyList.htm
• http://www.edutech.ch/contribution/nstrees/index.php
• http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
• http://www.dbmsmag.com/9604d06.html
• http://en.wikipedia.org/wiki/Tree_traversal
• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html（appletjava montrant le fonctionnement）

Graphes

图

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Classes :

课程：

Nested Sets DB Tree Adodb

嵌套集数据库树 Adodb

• http://www.phpclasses.org/browse/package/2547.html

• http://www.phpclasses.org/browse/package/2547.html

Visitation Model ADOdb

访问模型 ADOdb

• http://www.phpclasses.org/browse/package/2919.html

• http://www.phpclasses.org/browse/package/2919.html

PEAR::DB_NestedSet

PEAR::DB_NestedSet

• http://pear.php.net/package/DB_NestedSet
• utilisation : https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html

• http://pear.php.net/package/DB_NestedSet
• 利用率：https: //www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html

PEAR::Tree

梨树

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

nstrees

树

• http://www.edutech.ch/contribution/nstrees/index.php

• http://www.edutech.ch/contribution/nstrees/index.php

回答by Josh

What's the best way to represent a hierachy in a SQL database? A generic, portable technique?

在 SQL 数据库中表示层次结构的最佳方式是什么？一种通用的便携式技术？

Let's assume the hierachy is mostly read, but isn't completely static. Let's say it's a family tree.

让我们假设层次结构主要是读取的，但不是完全静态的。假设它是一棵家谱。

Here's how not to do it:

以下是不这样做的方法：

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

And inserting data like this:

并插入这样的数据：

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

Instead, split your nodes and your relationships into two tables.

相反，将您的节点和关系拆分为两个表。

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

Data is created like this:

数据是这样创建的：

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

you can now run arbitary queries that don't involve joining the table back on itself, which would happen if you have the heirachy relationship in the same row as the node.

您现在可以运行不涉及将表重新连接到自身的任意查询，如果您在与节点相同的行中具有 heirachy 关系，就会发生这种情况。

Who has grandparents?

谁有祖父母？

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

All your descendants:

你所有的后代：

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

Who are uncles?

谁是叔叔？

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

You avoid all the problems of joining a table to itself via subqueries, a common limitation is 16 subsuqeries.

您可以避免通过子查询将表连接到自身的所有问题，一个常见的限制是 16 个子查询。

Trouble is, maintaining the ancestor table is kind of hard - best done with a stored procedure.

问题是，维护祖先表有点困难——最好用存储过程来完成。

回答by NakedBrunch

I've got to disagree with Josh. What happens if you're using a huge hierarchical structure like a company organization. People can join/leave the company, change reporting lines, etc... Maintaining the "distance" would be a big problem and you would have to maintain two tables of data.

我必须不同意乔希。如果您使用像公司组织这样的巨大层次结构会发生什么。人们可以加入/离开公司，更改报告线等......保持“距离”将是一个大问题，您必须维护两个数据表。

This query (SQL Server 2005 and above) would let you see the complete line of any person AND calculates their place in the hierarchy and it only requires a single table of user information. It can be modified to find any child relationship.

此查询（SQL Server 2005 及更高版本）可以让您查看任何人的完整行并计算他们在层次结构中的位置，它只需要一个用户信息表。可以修改它以查找任何子关系。

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;

回答by Matt Hamilton

FYI: SQL Server 2008 introduces a new HierarchyIDdata type for this sort of situation. Gives you control over where in the "tree" your row sits, horizontally as well as vertically.

仅供参考：SQL Server 2008针对这种情况引入了一种新的HierarchyID数据类型。使您可以控制行在“树”中的水平和垂直位置。

回答by Mark Harrison

Oracle: SELECT ... START WITH ... CONNECT BY

甲骨文：SELECT ... START WITH ... CONNECT BY

Oracle has an extension to SELECT that allows easy tree-based retrieval. Perhaps SQL Server has some similar extension?

Oracle 对 SELECT 进行了扩展，可以轻松地进行基于树的检索。也许 SQL Server 有一些类似的扩展？

This query will traverse a table where the nesting relationship is stored in parentand childcolumns.

此查询将遍历一个表，其中嵌套关系存储在父列和子列中。

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

http://www.adp-gmbh.ch/ora/sql/connect_by.html

回答by Telcontar

I prefer a mix of the techinques used by Josh and Mark Harrison:

我更喜欢 Josh 和 Mark Harrison 使用的技术组合：

Two tables, one with the data of the Person and other with the hierarchichal info (person_id, parent_id [, mother_id]) if the PK of this table is person_id, you have a simple tree with only one parent by node (which makes sense in this case, but not in other cases like accounting accounts)

两个表，一个包含 Person 的数据，另一个包含层次结构信息 (person_id, parent_id [, Mother_id]) 如果此表的 PK 是 person_id，则您有一个简单的树，每个节点只有一个父级（这在这种情况，但不是在其他情况下，如会计账户）

This hiarchy table can be transversed by recursive procedures or if your DB supports it by sentences like SELECT... BY PRIOR (Oracle).

这个层次表可以通过递归过程或者如果你的数据库通过像 SELECT... BY PRIOR (Oracle) 这样的句子来支持它。

Other posibility is if you know the max deep of the hierarchy data you want to mantain is use a single table with a set of columns per level of hierarchy

其他可能性是，如果您知道要维护的层次结构数据的最大深度是使用单个表，每个表层级都有一组列

回答by Markus Plesser

We had the same issue when we implemented a tree component for [fleXive]and used the nested set tree model approach mentioned by tharkun from the MySQLdocs.

当我们为[fleXive]实现树组件并使用MySQL文档中的 tharkun 提到的嵌套集树模型方法时，我们遇到了同样的问题。

In addition to speed things (dramatically) up we used a spreadedapproach which simply means we used the maximum Long value for the top level right bounds which allows us to insert and move nodes without recalculating all left and right values. Values for left and right are calculated by dividing the range for a node by 3 und use the innerthird as bounds for the new node.

除了（显着地）加快速度之外，我们还使用了一种扩展方法，这只是意味着我们使用了顶级右边界的最大 Long 值，这允许我们插入和移动节点，而无需重新计算所有左值和右值。左侧和右侧的值是通过将节点的范围除以 3 并使用内部三分之一作为新节点的边界来计算的。

A java code example can be seen here.

可以在此处查看Java 代码示例。

回答by NakedBrunch

If you're using SQL Server 2005 then this linkexplains how to retrieve hierarchical data.

如果您使用的是 SQL Server 2005，那么此链接将说明如何检索分层数据。

Common Table Expressions (CTEs) can be your friends once you get comfortable using them.

一旦您习惯使用通用表表达式 (CTE)，它们就可以成为您的朋友。