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

Question

你在数据库中建模和检索层级信息的方式是什么？

- realcals

Answer 1

我喜欢修改过的先序遍历树算法。 这种技术使得对树进行查询非常容易。

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

其中许多链接是与语言无关的：

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

• 嵌套集合，也称为修改过的先序遍历树遍历算法
• 邻接列表模型

这在这里很好地解释了：

• 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://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

邻接列表模型

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

嵌套集

• 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 (展示操作的Java小程序)

图形

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

课程：

嵌套集合数据库树 Adodb

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

访问模型ADODb

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

PEAR::DB_NestedSet

• 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

nstrees

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

- tharkun

Answer 2

在这个主题上具有决定性作用的文章是由乔·塞尔科（Joe Celko）撰写的，他将其中一些文章整理成了一本名为《Joe Celko's Trees and Hierarchies in SQL for Smarties》的书。

他青睐一种叫做有向图的技术。有关他在这个主题上的工作介绍可以在这里找到。

- andy47

---

我认为人们称这种技术为“嵌套集”。 - ChrisW

这项技术的更详细解释位于http://dev.mysql.com/tech-resources/articles/hierarchical-data.html。 - lubos hasko

我认为嵌套集模型存在的问题是每次添加或删除节点时都必须更新整个树的右侧，这对于可扩展性来说并不好。是否有任何基准测试？我认为文件系统不使用嵌套集模型以防止遍历整个树，因此它们使用邻接表模型。@Quassnoi解释得很好：http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ - Eduardo

在这本书中，乔解释了各种可以减少树调整频率的技术。其中一个例子在“第5章 频繁插入树”中有所涉及。一般的技术是应用于每个节点左/右值之间的大差距，使其下属数量可以改变而不必对树的其余部分进行调整。这对于非常快速变化的深层次结构特别有用。 - James Wald

Answer 3

如何在SQL数据库中表示层次结构？有没有一种通用的、可移植的技术呢？假设层次结构大多是只读的，但并非完全静态。比如说家谱。

以下是不应该采用的方式：

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

像这样插入数据：

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

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

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

数据是这样创建的：

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

现在，您可以运行任意查询，而不需要将表重新连接回自身，如果您在同一行中具有层次关系，则会发生这种情况。

谁有祖父母？

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

所有子元素：

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

叔叔是谁？

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

通过子查询连接自身表格可能会遇到很多问题，而常见的限制是只有16个子查询。

然而，维护祖先表格相对较难，最好使用存储过程完成。

- Josh

---

对于某些目的来说还不错，我同意节点和边应该分别存储在不同的表中 - 但是跟踪每个节点如何连接到每个后代/祖先在大型复杂图中不会很好扩展 - 所呈现的是一种去规范化（用于“距离”和“垂直”连接）的优化，可能不适合大多数情况。请参见Telcontar的答案。 - bacar

这是我最喜欢的建模层次结构的方式，直到数据变得非常庞大。它简单而且非常灵活。 - Andrew

Answer 4

我不同意Josh的观点。如果你正在使用一个大型的分层结构，比如公司组织，人们可能会加入/离开公司，改变汇报线等等……这样就很难维护“距离”，你还需要维护两张数据表。

以下查询（适用于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;

- Khaaaan

---

递归查询不仅限于SQL Server。Postgres、Oracle、DB2、Firebird等许多数据库也可以实现相同的功能。 - user330315

Answer 5

提醒您：SQL Server 2008引入了一个新的HierarchyID数据类型，用于这种情况。它能让您在“树状结构”中水平和垂直地控制行所处的位置。

- Matt Hamilton

Answer 6

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

Oracle有一个扩展功能可以方便地进行基于树状结构的检索。也许SQL Server也有类似的扩展功能?

这个查询将遍历一个表，其中嵌套关系存储在parent和child列中。

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

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

- Mark Harrison

Answer 7

我更喜欢Josh和Mark Harrison使用的技术结合起来：

使用两个表，一个存储人员数据，另一个存储层级信息（person_id、parent_id [，mother_id]）。如果该表的主键是person_id，则每个节点只有一个父节点，这在本例中很有意义，但在其他情况下（如会计账户）可能没有意义。

可以通过递归过程或者如果你的数据库支持，可以使用类似于SELECT... BY PRIOR（Oracle）的语句来遍历此层次结构表。

另一种可能性是，如果您知道要维护的层次结构数据的最大深度，则可以使用单个表，并为每个层次结构级别设置一组列。

- Telcontar

Answer 8

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

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

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

- Markus Plesser

Answer 9

如果您正在使用SQL Server 2005，那么此链接将解释如何检索分层数据。

一旦您熟悉了通用表达式（CTE），它们就可以成为您的好朋友。

- Khaaaan

---

CTE在性能领域中查找父级的子项并不是很友好。但是从子项查找父级是可以接受的。 - BozoJoe