高效持久的递归数据结构
递归数据结构的常用方法是在每个对象中都有一个父指针。我的问题是,通常的实现无法在一次操作中回答以下问题;相反,我需要多次查询我的数据库。有没有一个解决方案可以在单个查询中给出结果?
获取节点的所有子节点的列表
查找所有父节点(==到根节点的最短路径)
注意:我正处于规划阶段,所以我还没有局限于某个数据库。
The usual approach with recursive data structures is to have a parent pointer in each object. My problem is that the usual implementation can't answer the questions below in a single operation; instead I need to query my database several times. Is there a solution which gives me the result in a single query?
Get a list of all children of a node
Find all parent nodes (== shortest path to the root node)
Note: I'm in the planning stage, so I'm not yet limited to a certain database.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
至少Oracle可以进行分层查询。考虑数据库用户角色的示例:
现在选择用户“CM_MARY”的所有角色:
结果:
商业_DEP
创建_订单
客户
SELECT_ORDERS
选择拥有角色“CLIENT”的所有角色和用户
结果:
CL_约翰
CL_MATT
商业_DEP
CM_MARY
更新:
既然你提到,树将是相当静态的,尝试 Joe Celko 的树(大约需要阅读 180 行)。
它根本不需要自我加入!因此,我希望它的执行速度比 CONNECT BY 快几倍。虽然我刚刚在 30 分钟前读到它,但不知道它在现实世界中有多好
更新 2: 使用 MySQL 的“嵌套集模型”:管理 MySQL 中的分层数据 这与上面 Joe Celko 的 Trees 相同,但有更多示例和解释。
At least Oracle can do hierarchical queries. Consider example of db users' roles:
Now select all roles of user 'CM_MARY':
Result:
COMMERCIAL_DEP
CREATE_ORDERS
CLIENT
SELECT_ORDERS
Select all roles and users, who owns role 'CLIENT'
Result:
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY
UPDATE:
Since you mentioned, tree will be pretty static, it may be interesting to try Joe Celko's Trees (aprox 180 lines to read).
It doesn't require self joins at all! So, I expect it to perform times faster then CONNECT BY. Though I've just read about it just 30 min ago, and don't know how good it is in real world
Update2: "Nested Set Models" with MySQL: Managing Hierarchical Data in MySQL This is the same as Joe Celko's Trees above but with more examples and explanation.
如果“所有子节点”仅表示直接子节点,则只需在每个节点上放置一个子节点列表以及指向父节点的指针即可。请注意,这将使将节点移动到另一个父节点的成本更高,因为所有(孙)子节点也必须更新。
如果“所有子级”确实意味着所有子级,则一种选择是构建每个父级 ID 的字符串,并将其添加为索引列。例如,如果您有
A
、子B
、孙子C
,则您将有C 值为
A/B/C
的列。现在,要查找A
的所有子级,您只需对"A/%"
执行LIKE
查询即可。不过,当您需要更改具有子节点的父节点时,这又是昂贵的。我认为,如果您需要能够快速更改父母,则需要将父母信息维护为链接列表。但是,您可以使用存储过程来执行此查询操作,只需一次数据库往返。
If "all children" means only direct children, simply put a list of children, as well as a pointer to the parent on each node. Note that this will make moving a node to another parent more expensive, as all (grand)-children must be updated as well.
If "all children" really means all children, one option would be to build a string of the IDs of each parent, and add it as an indexed column. For example, if you have
A
, with the childB
, with the grandchildC
, you'd have inC
a column with valueA/B/C
. Now to find all children ofA
you can simply do aLIKE
query on"A/%"
. Again, though, this is expensive when you need to change the parent of a node with children.If you need to be able to change parents quickly, you're going to need to maintain parent information as a linked list, I think. You could, however, use a stored procedure to perform this query operation with only one database round trip.