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

你用什么方法来build模和检索数据库中的分层信息？

Answer 1

关于这个主题的权威性文章是由Joe Celko撰写的，他已经将其中的许多文章写入了一本名为Joe Celko的“树和层次结构”的书籍，以供Smarties使用。

他主张一种叫做有向图的技术。 他在这方面的工作介绍可以在这里find

Answer 2

我喜欢修改先序树遍历algorithm。 这种技术使查询树非常容易。

但是，这里是一个关于我从Zend Framework（PHP）贡献者网页复制的主题的链接列表（发布者Laurent Melmoux在Jun 05，2007 15:52）。

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

有两个主要的表示和algorithm来表示具有数据库的分层结构：

• 嵌套集合也被称为修改前序树遍历algorithm
• 邻接表模型

这里有很好的解释：

• http://www.sitepoint.com/article/hierarchical-data-database
• 在MySQL中pipe理分层数据
• 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（applet java montrant le fonctionnement）

Graphes

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

课程：

嵌套集DB Tree 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

梨树

• 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

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

数据是这样创build的：

 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 

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

谁有祖父母？

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

您避免了通过子查询join表的所有问题，常见的限制是16个子查询。

麻烦的是，维护祖先表是用存储过程来完成的。

Answer 4

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

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

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

Answer 5

仅供参考：SQL Server 2008为这种情况引入了新的HierarchyID数据types。 让您可以控制行中“树”的位置，水平以及垂直。

Answer 6

Oracle：SELECT … START WITH … CONNECT BY

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

Answer 7

我更喜欢乔希和马克·哈里森所用的技术：

两个表，其中一个带有Person的数据，另一个带有层次结构信息（person_id，parent_id [，mother_id]），如果此表的PK是person_id，则有一个简单的树，只有一个父节点这种情况下，但在其他情况下，如会计帐户）

这个喜好表可以通过recursion过程横向化，或者如果你的数据库支持像SELECT … BY PRIOR（Oracle）这样的句子。

其他可能性是，如果您知道层次结构数据的最大深度，则要使用单个表，并在每个层次结构中使用一组列

Answer 8

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

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

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

Answer 9

如果您使用的是SQL Server 2005，那么这个链接解释了如何检索分层数据。

一旦你习惯使用它们，通用表格expression式（CTE）可以成为你的朋友。