如何对使用嵌套集模型存储的树进行排序？ [英] How do you sort a tree stored using the nested set model?

问题描述

当我提及嵌套集模型时，我的意思是这里。

When I refer to nested set model I mean what is described here.

我需要在用户定义的层次结构中构建一个新的系统来存储类别（我不能想到更好的词）。因为嵌套集合模型是针对读取而不是写优化的，所以我决定使用它。不幸的是在我研究和测试嵌套集合，我遇到了如何显示层次树与排序节点的问题。例如，如果我有层次结构：

I need to build a new system for storing "categories" (I can't think of better word for it) in a user defined hierarchy. Since the nested set model is optimized for reads instead of writes, I decided to use that. Unfortunately during my research and testing of nested sets, I ran into the problem of how do I display the hierarchical tree with sorted nodes. For example if I have the hierarchy:

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

我想要排序，使其显示为：

I want that to be sorted so that it displays as:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

注意，制作在研究之前出现。

Notice that the fabrication appears before research.

无论如何，经过长时间的搜索，我看到了答案，二维数组和排序和度假树，并序列化回到你的嵌套集模型（我是paraphashing ...）。无论哪种方式，第一个解决方案是RAM和CPU的可怕的浪费，这是非常有限的资源...第二个解决方案看起来像很多痛苦的代码。

Anyway, after a long search I saw answer such as "store the tree in a multi-dimensional array and sort it" and "resort the tree and serialized back into your nested set model" (I'm paraphrazing...). Either way, the first solution is a horrible waste of RAM and CPU, which are both very finite resources... The second solution just looks like a lot of painful code.

无论如何，我可以找出如何（使用嵌套集模型）：

Regardless, I was able to figure out how to (using the nested set model):

1. 在SQL中启动一个新树


2. 在树中插入节点作为另一个节点的子节点


3. 在树中的同级节点之后插入节点


4. 从树中拉取具有层次结构的整棵树


5. 从层次结构中的特定节点（包括根）中提取子树，有或没有深度限制


6. 查找树中任何节点的父级

1. Start a new tree in SQL
2. Insert a node as a child of another node in tree
3. Insert a node after a sibling node in the tree
4. Pull the entire tree with the hierarchy structure from SQL
5. Pull a subtree from a specific node (including root) in the hierarchy with or without a depth limit
6. Find the parent of any node in the tree

所以我认为＃5和＃6可以用于排序

So I figured #5 and #6 could be used to do the sorting I wanted, and it could also be used to rebuild the tree in sorted order as well.

但是，现在我已经查看了所有这些事情学会了我看到＃3，＃5和＃6可以一起使用来执行排序的插入。如果我做了排序插入它总是排序。但是，如果我更改了排序标准，或者想要不同的排序顺序，我会回到第一个排序顺序。

However, now that I've looked at all of these things I've learned to do I see that #3, #5, and #6 could be used together to perform sorted inserts. If I did sorted inserts it always be sorted. However, if I ever change the sort criteria or I want a different sort order I'm back to square one.

这可能是嵌套集模型的限制？它的使用禁止在输出的查询排序？

Could this just be the limitation of the nested set model? Does its use inhibit in query sorting of the output?

推荐答案

我认为这确实是嵌套集模型的限制。您不能轻松地在其各自父节点中对子节点排序，因为结果集的排序对于重建树结构是必不可少的。

I think this is indeed a limitation of the nested set model. You can not easily sort the child nodes within their respective parent node, because the ordering of the result set is essential to reconstruct the tree structure.

我认为它可能是在插入，更新或删除节点时保持树排序的最佳方法。这甚至使查询非常快，这是此数据结构的主要目标之一。如果你为所有操作实现存储过程，它是很容易使用。

I think it is probably the best approach to keep the tree sorted when inserting, updating or deleting nodes. This even makes queries very fast, which is one of the main goals of this data structure. If you implement stored procedures for all operations, it is very easy to use.

你也可以反转预排序的树的排序顺序。您只需使用 ORDER BY node.rgt DESC ，而不是 ORDER BY node.lft ASC 。

You can also reverse the sort order of a presorted tree. You just have to use ORDER BY node.rgt DESC instead of ORDER BY node.lft ASC.

如果你真的需要支持另一个排序标准，你可以通过添加第二个 lft 和 rgt 索引到每个节点，并按每个插入/更新/删除的其他条件保持此排序。

If you really need to support another sort criteria, you could possible implement it by adding a second lft and rgt index to each node and keep this sorted by the other criteria on every insert/update/delete.

这篇关于如何对使用嵌套集模型存储的树进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！