16

我在表格中有一个树结构，它使用物化路径让我可以快速找到孩子。但是，我还需要对结果进行深度优先排序，正如人们对线程论坛回复所期望的那样。

 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

所以最终的结果实际上应该是这样排序的：

 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）来执行此操作，还是应该将其他信息添加到此表中？

更新：试图更好地解释排序标准。

想象一下 id '1' 是论坛的根帖子，所有以 '1' 开头的 'matpath' 都是该帖子的子项。所以 ids 2 到 5 是对 1 的直接回复并得到'1'的matpaths。但是，id 6 是回复 2，而不是直接回复 1，因此它的 matpath 为 1.2。这意味着对于具有正确嵌套的线程论坛，所有 id 都显示在表格中，论坛的结构将如下所示，因此排序要求：

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

5 回答 5

18

我相信你的物化路径是不对的。

你有什么逻辑可以对这样的事情进行排序

1
1.2
1
1.5

为什么第二个 1 不和第一个在一起？

如果你有

1
1.2
2
2.5

这将是微不足道的。

编辑：我查看了您的示例，您没有存储行的具体化路径，但您正在存储父行的具体化路径。这是行的具体化路径实际上应该是什么样子。如果您将其存储为以下形式，则如果您的分支不超过 9 个，则直接在 matpath 上排序将起作用：

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

否则（> 9）你将不得不把它matpath变成类似的东西

001.002.006
001.002.006.008

这将支持多达 999 个分支。

请注意

  • 即使是具有 4 个固定数字的方法，例如0001.0002.0006会给你一个比接受的答案更短的字段
  • 您可以使用用户函数动态解析 matpath 并生成排序值
  • 您可以直接以这种格式存储 matpath（它也有一些其他不错的属性）
于 2010-05-09T13:21:32.247 回答
9

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

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。这样一来，如果您想一次查询多个论坛（您可能不会），那么它仍然会正确排序。
于 2010-05-09T13:19:34.723 回答
7

我不确定我是否理解为什么接受的解决方案有任何意义。它可以工作，但与@Unreason 的解决方案（仅在物化路径中填充 ID）相比，它的标准化和效率更低（更多磁盘空间、更多索引等）。

OP 面临的整个情况似乎源于这样一个事实，正如@Unreason 正确指出的那样，物化路径（MP）的实现是不正确的。OP 已将 MP 提供给父节点，而不是当前节点。在接受的解决方案中，该SortPath列通过提供当前节点的具体化路径来纠正此问题（这次使用日期——为什么？——而不是主键）。

作为参考，请考虑以下摘录：

物化路径

在这种方法中，每条记录都存储到根的整个路径。在我们之前的示例中，假设 KING 是一个根节点。然后，ename = 'SCOTT' 的记录通过路径 SCOTT->JONES->KING 连接到根。现代数据库允许将节点列表表示为单个值，但由于在此之前很久就发明了物化路径，因此约定坚持使用与某些分隔符连接的节点的纯字符串；最经常 '。' 或者 '/'。

于 2012-07-14T19:17:01.940 回答
6

虽然@Unreason 对填充的回答有效，但我想提供另一种解决方案，我相信这是我自己对这个问题的发明。

您正在寻找创建字节流的函数，一个f(x)=b_1b_2..b_i（对不起，SO 上没有 MatJax）b_i是一个字节。我们知道两个字节流与第一个不同的字节比较相同。我们想要这样一个功能f(x)<f(y) iff x<y。

用 0 填充到相同的长度肯定很容易达到这个目标。你拿两个数字，看看第一个非零字节，你就在那里。

大约八年前，Steven Wittens (acko.net) 向 Drupal 核心引入了一个不同的技巧：将字符串前面的位数作为另一个数字。因此，数字 97685 变成了字符5 9 7 6 8 5。这也有效：先看长度字节，如果它们不一样，那么越大肯定越大。除此之外，您知道这两个数字的长度相等。他还使用了以 0-9a-z 为数字的 36 进制数字，就像每个字母的十六进制一样。这种编码需要两个字节用于前 36 个节点，三个用于接下来的 1260...

请注意，填充和这种狡猾的可变长度编码都不需要用于具体化路径的分隔符，尽管为了便于阅读，它们通常被包含在内。

numconv支持 base85 编码，但需要区分大小写的排序规则。如果您删除小写字母，您仍然有 base68，则有 94 个 ASCII 字符。

但是，如果您使用“二进制”字段，那么您可以使用 base256：而不是巧妙的编码，只需将数字写为一系列字节，然后在整个事物前面加上字节流的长度作为单个字节。这将允许您对小于 2^2048 左右的任何树进行编码。对于前 256 个节点，您使用两个字节，对于接下来的 65280，您使用三个字节。这已经很有效了。

我提名这个utf8encode(x)功能。考虑一下！您需要进行位排序而不是字节排序，但这不会改变结果：找到最左边的零位。如果另一个字符串在那里有一个 1，那么它将是一个更长的 UTF-8 编码，所以肯定会更大。如果它们在同一个地方有第一个零，那么我们就有相同长度的位串，这对我们来说比较好。

这很好，但是分隔符呢。将 UTF-8 算法视为纯粹的创建比特流的算法时，它可以处理 31 位数字——因此它适用于包含少于 20 亿个节点的树。您的具体化路径将是 UTF-8 编码数字的比特流，它们比较好：丢弃最左边相同的 UTF-8 编码数字，我们回到上一段。量子点

因为我们不需要分隔符或前缀字节，我们可以将前 128 个节点编码为一个字节，然后将下一个 1920 编码为两个字节，最多 65535 个三个字节。对于四个字节，base256 将获胜。对于非常大的树，您可以将 UTF-8 视为 0-2147483647 到字节流的编码器。所以你可以用它作为base2147483647编码：D

总结一下：UTF-8 最适合小树，并且不比 20 亿节点以下的 base256 差多少。除此之外，直到 2^2048 左右前缀长度-base256 获胜。除此之外，prefixed-with-length-base2147483647 获胜，除此之外没有什么。

于 2014-02-10T05:15:17.690 回答
3

我想不出一个简单的方法来用直接的 SQL 做到这一点。我将在这里使用 node_path 而不是 matpath。node_path 是 matpath||'.'||id

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

现在您想根据 node_path 对树进行排序，排序字段由您运行排序的次数定义。

在 split_part(node_path, '.', recursion_depth) 上排序的 plpgsql 中的自定义递归函数将起作用。您将不得不检查 split_part 中的 NULL 值（并忽略这些值）。

于 2010-05-09T14:46:19.947 回答