以有效和简单的方式实现家长/子女关系
我有一张桌子
create table site ( site_Id int(5), parent_Id int(5), site_desc varchar2(100) ); 领域的意义：
- site_Id：网站的ID
- parent_Id：网站的父级ID
- site_desc：虽然与问题没有关系，但是有对网站的描述
要求是，如果我有一个site_id作为input，并且我需要在站点下面标记的所有id。 例如：
A / \ BC / | \ /\ DEFGH /\ IJ
所有节点都是site_Id。
该表包含这样的数据：
Site_id | Parent_ID | site_desc _________|____________|___________ A | -1 | B | A | C | A | D | B | E | B | F | B | I | D | J | D |
……
A是B和C的父母，等等。
如果B是给定的input，则查询需要获取D，E，I，F，J
它目前通过循环中的多个查询来实现，但是我正在考虑以最less数量的查询来实现这一点。
我目前正在做的是::
倒票
algorithm如下所示：
Initially create a data set object which you will populate, by fetching data from the data base. Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. Step1: Fetch all the rows, which doesn't have a parent(root) node. Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. Iterating this RS we get prod1, and we insert a row in our DataSET obj. Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.
我需要我的数据模型约束中最好的优化技术。 如果您有任何build议，请随时回答。
请提出任何build议。 提前致谢。
不幸的是，如果你不能改变数据模型，并且你正在使用MySQL，那么你就陷入了需要recursion查询的情况，而且你正在使用一个不支持recursion查询的DBMS。
Quassnoi写了一系列有趣的博客文章，展示了查询分层数据的技巧。 他的解决scheme很聪明，但非常复杂。 http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/
PostgreSQL是另一个开源的RDBMS，它支持recursion查询 ，所以你可以按照你展示的方式获取整个树。 但是，如果你不能改变数据模型，我假设你不能切换到不同的RDBMS。
有几种可供select的数据模型可以更容易地获取任意深度的树：
- closures表
- 嵌套集aka修改先序树遍历
- path枚举又称物化path
我在我的演示中使用SQL和PHP分层数据模型以及我的书“ SQL反模式：避免数据库编程陷阱”中介绍了这些内容 。
最后，还有另外一个解决scheme，我在Slashdot的代码中使用了他们的评论层次结构：它们存储“parent_id”就像在Adjacency List中一样，但是它们也存储一个“root_id”列。 给定树的每个成员都具有相同的root_id值，它是树中最高的祖先节点。 那么在一个查询中很容易获取整棵树：
SELECT * FROM site WHERE root_id = 123;
然后你的应用程序从数据库中取回所有的节点到一个数组中，并且你必须编写代码来循环这个数组，并把这些节点插入到内存中的树形数据结构中。 如果你有很多独立的树，每个树都有相对较less的条目，这是一个很好的解决scheme。 这对Slashdot的情况是有好处的。
昨天，我已经回答了这个问题 ，这个问题与你所描述的问题完全相关： 在给定的邻接表之外，你想要得到一个特定父节点的所有子节点 – 也许在一个一维数组中，你可以很容易迭代。
你可以只使用一次对数据库的调用来做到这一点，但有一个问题：你必须返回表中的所有行。 MySQL不支持recursion查询，所以相反，您必须在应用程序代码中执行SELECT操作。
我只是重申我的答案，我链接到上面，但基本上，如果你返回一个结果集（也许从PDOStatement->fetchAll(PDO::FETCH_ASSOC)或其他方法）的格式如下所示：
Array ( [0] => Array ( [site_id] => A [parent_id] => -1 [site_desc] => testtext ) [1] => Array ( [site_id] => B [parent_id] => A [site_desc] => testtext ) [2] => Array ( [site_id] => C [parent_id] => A [site_desc] => testtext ) [3] => Array ( [site_id] => D [parent_id] => B [site_desc] => testtext ) [4] => Array ( [site_id] => E [parent_id] => B [site_desc] => testtext ) [5] => Array ( [site_id] => F [parent_id] => B [site_desc] => testtext ) [6] => Array ( [site_id] => I [parent_id] => D [site_desc] => testtext ) [7] => Array ( [site_id] => J [parent_id] => D [site_desc] => testtext ) )
您可以使用此recursion函数检索任何site_id （提供您知道的id）的所有子/孙/ greatgrandchildren / so-on：
function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array()) { foreach($src_arr as $row) { if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id) { $rowdata = array(); foreach($row as $k => $v) $rowdata[$k] = $v; $cats[] = $rowdata; if($row['parent_id'] == $id) $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true)); } } return $cats; }
例如，假设您想要检索site_id D所有子site_id ，则可以使用如下所示的函数：
$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D'); print_r($nodelist);
输出：
[0] => Array ( [site_id] => D [parent_id] => B [site_desc] => testtext ) [1] => Array ( [site_id] => I [parent_id] => D [site_desc] => testtext ) [2] => Array ( [site_id] => J [parent_id] => D [site_desc] => testtext )
注意，我们保留父母及其子女，孙辈等的信息（不pipe嵌套深度如何）。
检查出嵌套集模型，如果你想能够在单个查询中做到这一点： http : //mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
另一种select是将所有关系包含在链接表中。 所以每个网站都会有一个链接到其父母，祖父母等等。每一个关系都是明确的。 然后你只需查询该链接表来获取所有的后代。
首先，我会推荐一个不同的方法来存储树： 闭包表 。 如果你想知道更多关于它，你可以findSQL Antipatterns书相当有趣。
那就说。 在我看来，最简单的方法是生成这样的结构： http : //jsbin.com/omexix/3/edit#javascript
我希望你阅读JavaScript代码没有问题。 我使用它，因为在JavaScript中创build未分类的对象看起来不那么黑客。 可以通过使用multidimensional array来实现相同的对象（或引用），但它看起来有点混乱。
这是什么algorithm：
- 我们遍历节点列表， 一次
- 如果节点的父节点不存在，则在数组中创build占位符
- 如果节点没有父节点，则放在根节点列表中
- 如果节点在数组中没有占位符，则创build占位符
- 来自节点的值被分配给占位符
- 如果父节点具有父节点，则向父节点注册节点
这是关于它。 基本上你会生成两个列表：所有的节点，只有根节点。
您可能需要查看闭合表格模式。 我发现这个网站的信息。 据我所见，也有几个关于这个概念的StackOverflow问题，例如这里 。
如果您不经常更新site表，则可以使用以下策略：
create table site ( site_Id int(5), parent_Id int(5), site_desc varchar2(100), parents_path varchar(X) );
parents_path等于从根节点到选定节点的path。 例如，叶J应该是|A|B|D| 。
优点： – 您将需要单个查询来获得结果;
缺点： – 更新期间查询更多（但可以明智地更新）;
希望它有帮助
其他人已经提出了如何通过对表格结构的轻微修改来做到这一点。
如果你不想修改结构（即使这是最好的），那么你可以这样做：
- SELECT * FROM site ORDER BY Parent_ID，Site_id;
通常可以安全地假定，一旦分配，ID不会改变; 如果ID没有被洗牌，也就是说，节点C不会在节点B下移动，那么确实子节点的ID总是比其父母高，并且上面的sorting将保证所有的父母在他们的孩子之前被抓取。
所以这些是假设：
- we prefer not to change the table layout - we never change the IDs once assigned - we never reorder the tree, moving IDs around
因此，可以在内存中创build树（甚至可以减less查询本身添加一个WHERE Site_ID> = B）。
要通过的第一个节点将是B的，将被放入树中。
所有后续的节点可以存储在它们的Parent_ID-th节点中，该节点确实已经被加载。
这将在Python中相当好（你直接修改父节点）。
请求“获取B的所有后裔”可能会在PHP中这样回答：
$nodes = array( $parent_id ); $cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? " . "ORDER BY Parent_ID, Site_Id ;", $parent_id); while ($tuple = SQLFetchTuple($cursor)) if (in_array($tuple['Parent_ID'], $nodes)) $nodes[] = $tuple['Site_Id']; SQLFree($cursor); // The first node is the global parent, and may be array_shift'ed away // if desired.
其他方式
相当蛮力
另一种可能性是在另一个表中recursion地存储“descendant_of”关系：
TRUNCATE descendants; INSERT INTO descendants ( node, of ) VALUES ( -1, NULL ); INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN descendants ON ( site.ParentId = descendants.of );
并重复插入，直到插入的行数等于零（或后代中的行总数停止增加;查询表大小在大多数数据库中是非常快的）。
在这一点上，你将存储所有的一级关系。 现在：
INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);
…直到后代停止增长（这将需要插入的数量等于最大数量的水平）。 连接总数将是层数的两倍。
现在，如果你想获得节点16的所有后代，你只需要查询
SELECT node FROM descendants WHERE of = 16;
您可以为此创build一个存储过程。
这是我在mysql中的实现
DROP PROCEDURE IF EXISTS SearchTree; DELIMITER go CREATE PROCEDURE SearchTree( IN root CHAR(1) ) BEGIN DECLARE rows SMALLINT DEFAULT 0; DROP TABLE IF EXISTS reached; CREATE TABLE reached ( site_Id CHAR(1) PRIMARY KEY ) ENGINE=HEAP; INSERT INTO reached VALUES (root); SET rows = ROW_COUNT(); WHILE rows > 0 DO INSERT IGNORE INTO reached SELECT DISTINCT s.site_Id FROM site AS s INNER JOIN reached AS r ON s.parent_Id = r.site_Id; SET rows = ROW_COUNT(); DELETE FROM reached WHERE site_Id = root; END WHILE; SELECT * FROM reached; DROP TABLE reached; END; go DELIMITER ; CALL SearchTree('B');
它返回预期的结果。
根据你在这里的意见，我假设你不愿意改变现有的数据模型，因为数百个应用程序正在使用（如果你用其他东西replace它会破坏）。
问题的根源在于，对于任何站点，我们只知道它是直接的父节点，所以我们需要recursion地查找父节点的父节点，直到find根节点为止。
如果您可以避开限制网站可以嵌套的深度/级别，则可以编写一个很棒的查询，为您完成所有工作，甚至可能不会很慢启动。 发射查询的大部分开销来自于build立连接，networking带宽等。MySQL可以非常快速。
触发多个查询会增加所有开销，所以我们不希望这样做。 做一个SELECT *，然后在应用程序逻辑中进行计算意味着您将每次都获取所有数据，从而最大限度地提高networking开销，所以我们不希望这样做。
如果树的深度限制是可以接受的，那么可以将多个查询组合成一个巨大的查询，完成所有工作并返回所需的确切结果集。 作为一个例子，我用你的数据，但用A，B，C等replace为1，2，3（因为你的列是int）。
要获取根节点的所有直接子项（使用site_id = 1），请执行以下操作：
select site_id from site where parent_id = 1
为了得到根节点的孙辈，做到这一点：
select grandchild.site_id from site grandchild, site child where grandchild.parent_id = child.site_id and child.parent_id = 1
为了得到根节点的曾孙，做到这一点：
select greatgrandchild.site_id from site greatgrandchild, site grandchild, site child where greatgrandchild.parent_id = grandchild.site_id and grandchild.parent_id = child.site_id and child.parent_id = 1
要获得根节点的所有后代，只需将上述查询合并为一个巨大的查询，如下所示：
select site_id from site where site_id in ( select site_id from site where parent_id = 1 ) or site_id in ( select grandchild.site_id from site grandchild, site child where grandchild.parent_id = child.site_id and child.parent_id = 1 ) or site_id in ( select greatgrandchild.site_id from site greatgrandchild, site grandchild, site child where greatgrandchild.parent_id = grandchild.site_id and grandchild.parent_id = child.site_id and child.parent_id = 1 )
我想你看这是如何工作的。 对于每个额外的级别，创build一个查询，查找离您正在search的后代多个级别的节点，并将该查询添加到具有额外'或site_id in（）'的超级查询中…
现在你可以看到，只有三个级别，这已经成为一个大问题。 如果你需要支持10个级别，这个查询将会变得非常庞大，所有的OR和IN都会减慢它的速度……但是，只是获取所有内容或者使用多个查询，它仍然可能会更快。 如果您需要支持任意数量的可能级别，则此查询无法帮助您。 它将不得不变得无限大。 在那种情况下，剩下的就是用更好的方法
也就是说，在复制粘贴并开始编码之前，有一种方法可以避免这种巨大的查询，支持任意深度并且不会破坏向后兼容性。 它确实需要对数据模型进行更改，但这是一个不会损害使用此数据模型的其他程序的小模型。 简而言之…
一个更好的方式
添加一个额外的列parent_paths，使用类似于他的答案中提到的ravnur来编码从每个节点一直到根的完整path
在插入，更新和删除时使用触发器dynamic填充该列。 您现在正在维护冗余数据。 它不会伤害其他程序，但可以给你的显着的性能好处。 确保你的触发器是防弹的（这可能是最难的部分），因为额外列中的数据应该始终与表中的常规数据同步
使用一个短而甜的查询，就像ravnur显示的那样，在parent_paths列中的任何地方查找site_id的发生，直接获得具有该site_id的所有后代，而没有任何recursion。
我也问自己如何recursion查询关系，我的大脑产生了这个解决scheme（：
SELECT * FROM ( SELECT t2.* FROM table t1, table t2 where t2.parent = t1.id OR t2.parent 0 GROUP BY t2.id, t2.parent ) as all_relations WHERE all_relations.parent >= '_the_id_' # if you dont want a subtree use only the inner select
我不是100％肯定的，但我认为只要id是自动递增的，一个孩子从来没有一个较小的id作为他的父母（这应该是正常的情况下），那么这可能是一个解决scheme？
