在树结构中查找根节点 [英] Find root node in tree structure
问题描述
嘿！
任何人都可以给我一个提示，如何最好地实现这个问题：
我有一个用户表（见下文），每个用户都有一个
优质用户 （=父节点），这应该是一个完全无关的
树结构。根节点可以有你喜欢的任何值，我想b $ b假设NULL对于一个开始是好的。我想要做的是从树中任意节点的方式找到
。
示例：
ROOT
|
----------
AB
---- -----
CD
-------
EFG
查询应返回C，B，ROOT如果我给它输入G的
例子。
这是我的用户表：
用户
=====================
user_id（主键）
名称
superior_id
你觉得有没有可能做到这一点而不会解雇几个
疑问？我的意思是我可以为每个''get-parent''查询发送查询，但
在大树上接缝效率相当低，没有？
非常感谢
Phil
Hey!
Can anyone give me a hint, how this problem is best implemented:
I have a table of users (see below), where every user has one
"superior user" (= parent node), this should be a fully unambigous
tree structure. The root node can have whatever value you prefer, I
suppose NULL would be good for a start. What I want to do is finding
the way from an arbitrary node in the tree.
Example:
ROOT
|
----------
A B
---------
C D
-------
E F G
The query should return C, B, ROOT if i give it the input of G for
example.
This is my users table:
users
=====================
user_id (primary key)
name
superior_id
Do you think there''s any possibility to do this without firing several
queries? I mean I could send a query for each ''get-parent'' lookup, but
that seams to be rather inefficient on large trees, no?
Thank you very much
Phil
推荐答案
pillepop2003写道：
pillepop2003 wrote:
我想要什么从树中的任意节点发现
方式。
What I want to do is finding
the way from an arbitrary node in the tree.
这是SQL的常见问题。
I通常建议实施路径枚举。 table
用于存储树中的每个祖先 - 后代路径。
这样做而不是仅为每个用户存储superiod_id。
另请参阅：
http://groups-beta.google.com/group/...51ff05edbbe71/
http://groups-beta.google.com/group/...b6d55c69e32ff/
问候，
Bill K.
This is a frequent question for SQL.
I usually suggest implementing a "path enumeration" table
to store each ancestor-descendant path in your tree.
Do this instead of storing simply the superiod_id for each user.
See also:
http://groups-beta.google.com/group/...51ff05edbbe71/
http://groups-beta.google.com/group/...b6d55c69e32ff/
Regards,
Bill K.
pillepop2003写道：
pillepop2003 wrote:
嘿！
任何人都可以给我一个提示，如何最好地实现这个问题：
我有一个用户表（见下文），每个用户都有一个
优秀的用户 （=父节点），这应该是一个完全不显眼的树结构。根节点可以有你喜欢的任何值，我认为NULL对于一个开始是好的。我想要做的是从树中的任意节点找到
的方式。
示例：
ROOT
|
- ---------
AB
---------
CD
-------
EFG
查询应返回C，B，ROOT，如果我给它输入G的
示例。
这是我的用户表：
用户
=====================
user_id（主键）
名称
superior_id
你觉得有没有可能在没有解决几个问题的情况下做到这一点？我的意思是我可以为每个''get-parent''查询发送一个查询，但是
接缝在大树上效率相当低，不是吗？
非常感谢
Phil
Hey!
Can anyone give me a hint, how this problem is best implemented:
I have a table of users (see below), where every user has one
"superior user" (= parent node), this should be a fully unambigous
tree structure. The root node can have whatever value you prefer, I
suppose NULL would be good for a start. What I want to do is finding
the way from an arbitrary node in the tree.
Example:
ROOT
|
----------
A B
---------
C D
-------
E F G
The query should return C, B, ROOT if i give it the input of G for
example.
This is my users table:
users
=====================
user_id (primary key)
name
superior_id
Do you think there''s any possibility to do this without firing several
queries? I mean I could send a query for each ''get-parent'' lookup, but
that seams to be rather inefficient on large trees, no?
Thank you very much
Phil
Phil，
你正在使用的结构是一个有限制的相邻列表，如
你已经找到了，一个更好的模型是嵌套集。这些可能首先看起来更复杂但是如果你花时间去理解它会让你感到惊讶它的强大功能它会让你感到惊讶。
高于一块蛋糕......
http://www.intelligententerprise.com...questid=327517
-
谢谢
Murph
Phil,
The structure you are using is an adjacent list which has limitations, as
you''ve found already, a better model is that of nested sets. These may
appear more complicated at first however if you take the time to understand
it you will be amazed by it''s power and it makes queries such as the one
above a piece of cake...
http://www.intelligententerprise.com...questid=327517
--
Thanks
Murph
这取决于你有多大的表以及如何使用它。它是否很容易进行大量更新？
我建立了一种机制来存储与网页相关的树木。我的
需要涉及轻微的非规范化，我想在PHP中做我的递归
逻辑 - 尽可能避免代价高昂的递归查询。
它的工作原理如下：
page_id
element_id
parent_id（另一个element_id）
element_order（1-N，用于页面上的元素数量）
gen_level（世代级别）
{节点数据字段}
使用这种结构，我实际上能够在PHP中做相当多的逻辑，
并且多次避免代价高昂的递归查询。此外，我正在使用
mySQL 3.23缺少子选择，因此也通知了我的设计。
Paul Bramscher
pillepop2003写道：
It depends on how large a table you have and how it is used. Is it
prone to heavy updating?
I built a mechanism to store forests of trees, tied to web pages. My
needs involved slight denormalization, and I wanted to do my recursive
logic in PHP -- to avoid costly recursive queries whenever possible.
It worked like this:
page_id
element_id
parent_id (another element_id)
element_order (1-N, for the number of elements on the page)
gen_level (generational level)
{node data fields}
With this structure I''m actually able to do quite a bit of logic in PHP,
and avoid costly recursive queries a number of times. Also, I''m using
mySQL 3.23 which lacks subselects, so that informed my design as well.
Paul Bramscher
pillepop2003 wrote:
嘿！
任何人都可以给我一个提示，如何最好地实现这个问题：
我有一个用户表（见下文） ，每个用户都有一个优质用户。 （=父节点），这应该是一个完全不显眼的树结构。根节点可以有你喜欢的任何值，我认为NULL对于一个开始是好的。我想要做的是从树中的任意节点找到
的方式。
示例：
ROOT
|
- ---------
AB
---------
CD
-------
EFG
查询应返回C，B，ROOT，如果我给它输入G的
示例。
这是我的用户表：
用户
=====================
user_id（主键）
名称
superior_id
你觉得有没有可能在没有解决几个问题的情况下做到这一点？我的意思是我可以为每个''get-parent''查询发送一个查询，但是
接缝在大树上效率相当低，不是吗？
非常感谢
Phil
Hey!
Can anyone give me a hint, how this problem is best implemented:
I have a table of users (see below), where every user has one
"superior user" (= parent node), this should be a fully unambigous
tree structure. The root node can have whatever value you prefer, I
suppose NULL would be good for a start. What I want to do is finding
the way from an arbitrary node in the tree.
Example:
ROOT
|
----------
A B
---------
C D
-------
E F G
The query should return C, B, ROOT if i give it the input of G for
example.
This is my users table:
users
=====================
user_id (primary key)
name
superior_id
Do you think there''s any possibility to do this without firing several
queries? I mean I could send a query for each ''get-parent'' lookup, but
that seams to be rather inefficient on large trees, no?
Thank you very much
Phil
这篇关于在树结构中查找根节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
