以有效和简单的方式实现层次结构、亲子关系

2022-01-30 00:00:00 algorithm sql hierarchical-data php mysql

我有一张这样的桌子

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.例如:

The requirement is that if I have a site_id as an input, and I need all the ids tagged below the site. For Example:

                    A
                   / 
                  B   C
                / |  /
               D  E F G H
              /
             I  J

所有节点都是site_Id.

All the nodes are the 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 的父级,以此类推.

A is the parent of B and C and so on.

如果 B 是给定的输入,则查询需要获取 D、E、I、F、J

If B is the input given then the query need to fetch D, E, I, F, J

目前是通过循环中的多个查询来实现的,但我想用最少的查询来实现.

It is currently achieved through multiple queries in a loop, but I was thinking to achieve this in a minimum number of queries.

我目前正在做的是::

投反对票

算法是这样的:

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.

我需要在我的数据模型约束范围内获得最佳优化的技术.如果您有任何建议,请随时回答.
请提出任何建议.提前致谢.

I need the best optimized technique within my data model constraint. Feel free to answer if you have any suggestion.
Please suggest anything. Thanks in advance.

推荐答案

不幸的是,如果你不能改变数据模型,而你正在使用 MySQL,你就会陷入需要递归查询的境地,而你'正在使用不支持递归查询的 DBMS.

Unfortunately, if you can't change the data model, and you're using MySQL, you're stuck in a situation where you need recursive queries and you're using a DBMS that doesn't support recursive queries.

Quassnoi 撰写了一系列有趣的博客文章,展示了查询分层数据的技术.他的解决方案非常聪明,但也非常复杂.http://explainextended.com/2009/03/17/hierarchical-query-in-mysql/

Quassnoi wrote an interesting series of blog articles, showing techniques for querying hierarchical data. His solutions are quite clever, but very complex. http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL 是另一个开源 RDBMS,它 支持递归查询,因此您可以获取以您显示的方式存储的整个树.但是,如果您无法更改数据模型,我会假设您无法切换到不同的 RDBMS.

PostgreSQL is another open-source RDBMS, which does support recursive queries, so you could fetch a whole tree stored in the way you show. But if you can't change the data model, I'd assume you can't switch to a different RDBMS.

有几种替代数据模型可以更轻松地获取任意深度的树:

There are several alternative data models that make it much easier to fetch arbitrarily-deep trees:

  • 闭包表
  • 嵌套集,即修改的预序树遍历
  • 路径枚举又名物化路径

我在我的演示文稿中介绍了这些 使用 SQL 和 PHP 的分层数据模型,在我的书中SQL 反模式:避免数据库编程的陷阱.

I cover these in my presentation Models for Hierarchical Data with SQL and PHP, and in my book SQL Antipatterns: Avoiding the Pitfalls of Database Programming.

最后,我在 Slashdot 的代码中看到了另一种解决方案,用于他们的注释层次结构:它们像在邻接列表中一样存储parent_id",但它们也存储root_id"列.给定树的每个成员都具有相同的 root_id 值,它是其树中最高的祖先节点.然后很容易在一个查询中获取一整棵树:

Finally, there's another solution that I've seen used in the code for Slashdot, for their comments hierarchies: They store "parent_id" like in Adjacency List, but they also store a "root_id" column. Every member of a given tree has the same value for root_id, which is the highest ancestor node in its tree. Then it's easy to fetch a whole tree in one query:

SELECT * FROM site WHERE root_id = 123;

然后您的应用程序将所有节点从数据库中取回到一个数组中,您必须编写代码来循环该数组,将节点插入到内存中的树数据结构中.如果您有许多单独的树,并且每棵树的条目相对较少,这是一个很好的解决方案.这对 Slashdot 的情况有好处.

Then your application fetches all the nodes back from the database into an array, and you have to write the code to loop over this array, inserting the nodes into a tree data structure in memory. This is a good solution if you have many separate trees, and each tree has relatively few entries. It's good for Slashdot's case.

相关文章