我有一个像这样的表格
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作为输入,并且我需要在站点下方标记的所有 ID。例如:
A
/
B C
/ | /
D E F G H
/
I J
所有节点都是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 是给定的输入,则查询需要获取 D、E、I、F、J
它目前是通过循环中的多个查询实现的,但我正在考虑在最少数量的查询中实现这一目标。
我目前正在做的是:
反对票
算法是这样的:
- 最初创建一个数据集对象,您将通过从数据库中获取数据来填充该对象。
- 创建一个方法,该方法将父 id 作为参数并返回其子节点(如果存在),如果没有子节点,则返回 -1。
- 步骤1:获取所有没有父(根)节点的行。
- 步骤2:遍历此结果。例如,如果 prod1 和 prod2 是结果集中的初始返回节点。
- 迭代这个 RS,我们得到 prod1,并在我们的 DataSET obj 中插入一行。
- 然后,我们将 prod1 的 id 发送到 getCHILD 方法,以获取其子节点,然后再次迭代返回的结果集,并再次调用 getCHILD 方法,直到我们没有得到最低的节点。
我需要在我的数据模型约束内获得最佳优化技术。
不幸的是,如果您无法更改数据模型,并且使用的是MySQL,那么您将陷入需要递归查询并且使用的DBMS不支持递归查询的情况。
Quassnoi写了一系列有趣的博客文章,展示了查询分层数据的技术。 他的解决方案非常聪明,但非常复杂。http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/
PostgreSQL是另一个开源RDBMS,它确实支持递归查询,因此您可以获取以显示方式存储的整个树。 但是,如果您无法更改数据模型,我假设您无法切换到不同的RDBMS。
有几种替代数据模型可以更轻松地获取任意深度的树:
- 闭合表
- 嵌套集又名修改的预序树遍历 路径
- 枚举又名具体化路径
我在演讲《使用 SQL 和 PHP 的分层数据模型》和《SQL Antipatterns Volume 1: Voidthe Pitfalls of Database Programming》一书中介绍了这些内容。
最后,我在 Slashdot 的代码中看到另一种解决方案,用于它们的注释层次结构:它们像在邻接列表中一样存储"parent_id",但它们也存储"root_id"列。 给定树的每个成员都具有相同的root_id值,这是其树中最高的祖先节点。 然后,在一个查询中获取整个树就很容易了:
SELECT * FROM site WHERE root_id = 123;
然后,应用程序将所有节点从数据库提取回数组中,并且您必须编写代码以遍历此数组,将节点插入内存中的树数据结构中。 如果您有许多单独的树,并且每棵树的条目相对较少,这是一个很好的解决方案。 这对Slashdot的情况有好处。
昨天,我已经回答了这个问题,它与您描述的问题完全相关:在给定的邻接列表中,您希望获取特定父节点的所有子节点 - 并且可能位于可以轻松迭代的一维数组中。
您可以只使用对数据库的一次调用来执行此操作,但有一个问题:您必须返回表中的所有行。MySQL不支持递归查询,因此,您基本上必须在应用程序代码中进行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
)
)
您可以使用此递归函数检索任何site_id
的所有子/孙/曾孙/依此类推(前提是您知道 id):
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
的所有子项,您将像这样使用该函数:
$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
)
请注意,我们保留了父级的信息,以及它的子项、孙项等(无论嵌套有多深)。
查看嵌套集模型,如果您希望能够在单个查询中执行此操作: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
另一种方法是将所有关系包含在链接表中。因此,每个站点都会有一个指向其父级、祖父级等的链接。每一种关系都是明确的。然后,您只需查询该链接表即可获取所有后代。
首先,我推荐一种不同的方法来存储树:闭包表。如果你想了解更多,你会发现SQL反模式书非常有趣。
可是。在我看来,生成这种结构的最简单方法是:http://jsbin.com/omexix/3/edit#javascript
我希望你阅读JavaScript代码没有问题。我之所以使用它,是因为在 JavaScript 中创建未分类的对象看起来并不那么黑客化。通过使用多维数组可以在不中继对象(或引用)的情况下实现相同的内容,但它看起来有点令人困惑。
以下是算法的作用:
- 我们循环遍历节点列表,一次
- 如果节点的父节点未退出,则在数组中创建占位符
- 如果节点没有父节点,则将其放置在根节点列表中
- 如果节点在数组中没有占位符,则创建占位符
- 节点中的值分配给占位符
- 节点已注册到父节点(如果它有父节点)
这是关于它的。基本上,您生成两个列表:包含所有节点和仅包含根节点的列表。
你可能想看看闭包表模式。我发现这个网站内容丰富。据我所知,还有几个关于这个概念的StackOverflow问题,例如,在这里。
如果不经常更新site
表,则可以使用以下策略:
create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100),
parents_path varchar(X)
);
parents_path
等于从根到所选节点的路径。例如,对于叶J
它应该是 |A|B|D|
.
优点:- 您将需要单个查询才能获得结果;
缺点:- 更新期间的更多查询(但您可以明智地进行更新);
希望对你有帮助
其他人已经提出了如何通过对表格进行轻微修改来做到这一点结构。
如果您不想修改结构(即使这是最好的),那么您可以这样做喜欢这个:
- 选择 * 从网站订购 Parent_ID, Site_id;
通常可以安全地假设,一旦分配,ID就不会改变;如果ID不会改变不要四处乱窜,即节点 C 没有移动到节点 B 下,那么它将是确实子节点的 ID 始终高于其父节点,并且排序以上将保证所有父母在孩子之前被接走。
所以这些是假设:
- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around
因此,可以在内存中创建树(甚至减少查询)本身添加一个 WHERE Site_ID>= B)。
第一个通过的节点将是 B 的,将被放入树中。
所有后续节点都可以存储在它们的第 Parent_ID 个节点中,该节点肯定是之前加载。
这在 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.
另一种方式
相当蛮力
另一种可能性是将"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);
。再次直到后代停止增加(它将需要等于最大级别数)。JOIN 的总数将是级别数的两倍。
现在,如果您想获取节点 16 的所有后代,您只需查询
SELECT node FROM descendants WHERE of = 16;
可以为此创建一个存储过程。
这是我在 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');
它返回预期的结果。
根据您在此处的评论,我假设您不愿意更改现有的数据模型,因为数百个应用程序正在使用它(如果您用其他东西替换它,则会中断)。
问题的根源在于,对于任何网站,我们只知道它是直接父级,因此我们需要递归查找该父级的父级,直到找到根网站。
如果你能摆脱对网站可以嵌套的深度/级别的限制,你可以编写一个很好的查询,为你完成所有工作,甚至可能没有那么慢的启动速度。触发查询的大部分开销来自设置连接、网络带宽等。MySQL可以非常快。
触发多个查询会使所有开销成倍增加,所以我们不希望这样。执行 SELECT * 然后在应用程序逻辑中进行计算意味着您每次都会获取所有数据,从而最大化网络开销,所以我们不希望这样。
如果树的深度限制是可以接受的,则可以将多个查询组合成一个巨大的查询,该查询完成所有工作并返回所需的确切结果集。例如,我使用了您的数据,但将 A、B、C 等替换为 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
)
我想你会看到这是如何工作的。对于每个额外的级别,创建一个查询,以查找距离您要搜索后代的站点许多级别的节点,并将该查询添加到超级查询中,并带有额外的"或 ()中的site_id"...
现在如您所见,仅对于三个级别,这已经成为一个大查询。如果您需要支持 10 个级别,这个查询将变得很大,其中的所有 OR 和 IN 都会减慢它的速度......但是,它仍然可能比获取所有内容或使用多个查询更快。如果您需要支持任意数量的可能级别,则此查询无法为您提供帮助。它必须变得无限大。在这种情况下,剩下的就是使用更好的方法......
也就是说,在复制粘贴并开始编码之前,有一种方法可以避免如此巨大的查询,支持任意深度并且不会破坏向后兼容性。它确实需要更改数据模型,但它是一个很小的更改,不会损害使用此数据模型的其他程序。总之有...
更好的方式
添加一个额外的列parent_paths,使用他的答案中提到的 ravnur 之类的东西来编码从每个节点一直到根的完整路径
使用插入、更新和删除的触发器动态填充该列。您现在正在维护冗余数据。它不会伤害其他程序,但可以为您的程序带来显着的性能优势。确保您的触发器是防弹的(这可能是最难的部分),因为额外列中的数据应始终与表中的常规数据同步
使用一个简短而甜蜜的查询,例如 ravnur 显示的查询,该查询在parent_paths列中的任何位置查找site_id的出现情况,以直接获取具有该site_id的站点的所有后代,而无需任何递归。
我还问自己如何递归查询关系,我的大脑生成了这个解决方案(:
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 作为他的父母(这应该是正常情况),那么这可能是一个解决方案?