用物化路径对树进行排序？ [英] Sorting tree with a materialized path?

问题描述

我在表中有一个树形结构，它使用物化路径使我能够快速找到孩子。但是，我也需要按照深度优先的顺序对结果进行排序，就像有人希望在论坛中回复主题一样。

I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I also need to sort the results depth-first, as one would expect with threaded forum replies.

 id | parent_id | matpath |          created           
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  7 |         1 | 1       | 2010-05-08 18:18:11.849735
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695

因此，最终结果实际上应按以下方式排序：

So the final results should actually be sorted like this:

 id | parent_id | matpath |          created
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  7 |         1 | 1       | 2010-05-08 18:18:11.849735

我该如何解决？我可以在直接SQL（这是PostgreSQL 8.4）中做到这一点，还是应该向该表中添加其他信息？

How would I work that out? Can I do that in straight SQL (this is PostgreSQL 8.4) or should additional information be added to this table?

Update ：试图解释

想象一下，id'1'是论坛的根帖子，所有以'1'开头的'matpath'都是该帖子的子级。因此，id 2到5是对1的直接答复，并获得了 1的后代。但是，id 6是回复2，而不是直接回复1，因此其matpath为1.2。这意味着对于具有适当嵌套的线程化论坛（表中显示了所有ID），论坛的结构应如下所示，因此需要订购：

Imagine that id '1' is the root post to a forum and everything with a 'matpath' beginning with '1' is a child of that post. So ids 2 through 5 are direct replies to 1 and get matpaths of '1'. However, id 6 is a reply 2, not directly to 1, so it gets a matpath of 1.2. This means that for a threaded forum with proper nesting, with all ids shown in the tables, the structure of the forum would look like this, hence the ordering requirement:

* id 1 (root post)
    * id 2
        * id 6
            * id 8
    * id 3
    * id 4
    * id 5
        * id 9
    * id 7

推荐答案

我通常为此创建一个额外的columnn，称为 SortPath 之类的东西。它将包含您需要排序的数据，并将它们串联在一起。该列的类型为 varchar ，并按字符串排序。像这样的东西：

I typically create an additional columnn for this, called something like SortPath. It would contain the data that you need to sort by, concatenated together. That column would be of type varchar, and get sorted as a string. Something like this:

id | parent_id | matpath |          created            |                   sortpath
---+-----------+---------+-----------------------------+--------------------------------------------------------------------------------------
 2 |         1 | 1       | 2010-05-08 15:18:37.987544  | 2010-05-08 15:18:37.987544-2
 6 |         2 | 1.2     | 2010-05-08 17:50:43.288759  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6
 8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8
 3 |         1 | 1       | 2010-05-08 17:38:14.125377  | 2010-05-08 17:38:14.125377-3
 4 |         1 | 1       | 2010-05-08 17:38:57.26743   | 2010-05-08 17:38:57.267430-4 
 5 |         1 | 1       | 2010-05-08 17:43:28.211708  | 2010-05-08 17:43:28.211708-5
 9 |         5 | 1.5     | 2010-05-09 14:02:43.818646  | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9
 7 |         1 | 1       | 2010-05-08 18:18:11.849735  | 2010-05-08 18:18:11.849735-7

此处需要注意的几点：

• sortpath 将被排序为字符串，因此重要的是所有日期都必须长度相同，以便正确排序。例如，观察 2010-05-08 17：38：57.26743 如何在 sortpath 列中添加额外的零。


• 我将每个节点的PK附加到其日期的末尾。这样一来，如果您碰巧有两行具有完全相同的日期，由于要附加的其他数据，它们将总是以相同的顺序返回。


• 对我来说，数据看起来与我编写数据的方式不对称，因为我们在 sortpath 中显示当前节点的日期，但是它不在 matpath 中。我希望同时在两者中看到它。


• 您可能希望将节点ID 1的日期放在每个 sortcolumn 的开头也一样这样一来，如果您想一次查询多个论坛（可能不会），那么它仍然可以正确排序。

• sortpath will be sorted as a string, so it is important all dates have the same length for it to correctly sort. E.g., observe how 2010-05-08 17:38:57.26743 has an extra zero added in the sortpath column.
• I have appended the PK of each node to the end of its date. This is so that if you happen to have two rows with the exact same date, they will always get returned in the same order due to the additional data we are appending.
• To me, the data looks asymmetrical the way I have written it, because we are showing the current node's date in sortpath, but it is not in matpath. I would prefer to see it in both.
• You may want to put the date of node ID 1 at the beginning of each sortcolumn as well. This is so that if you ever want to query for more than one forum at a time (you probably won't), then it will still sort correctly.

这篇关于用物化路径对树进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！