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

Question

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

score 31 · Accepted Answer

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

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

许多链接与语言无关：

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

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

这里解释得很好：

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

邻接表模型

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

嵌套集

图表

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

课程：

嵌套集 DB 树 Adodb

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

访问模型 ADOdb

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

PEAR::DB_NestedSet

梨树

恩斯特里

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

score 15 · Accepted Answer

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

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

score 11 · Accepted Answer

在 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 个子查询。

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

score 10 · Accepted Answer

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

此查询（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;

score 4 · Accepted Answer

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

score 3 · Accepted Answer

甲骨文：选择...开始...连接方式

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

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

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

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

score 2 · Accepted Answer

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

两个表，一个包含 Person 的数据，另一个包含层次信息（person_id，parent_id [，mother_id]）这种情况下，但不是在其他情况下，如会计账户）

这个层次表可以通过递归过程进行横向处理，或者如果您的数据库通过 SELECT... BY PRIOR (Oracle) 等语句支持它。

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

score 1 · Accepted Answer

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

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

可以在这里看到一个 java 代码示例。

score 0 · Accepted Answer

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

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

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

9 回答 9

Related

Reference