使用物化路径对树进行排序？

Question

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

 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'的路径.但是,id 6是回复2,而不是直接为1,因此它得到1.2的matpath.这意味着对于具有适当嵌套的线程论坛,表中显示所有id,论坛的结构将如下所示,因此订购要求:

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

Answer 1

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

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

1
1.2
1
1.5

为什么第二个1不与第一个一起？

如果你有

1
1.2
2
2.5

这将是微不足道的.

编辑:我看了你的例子,你没有存储行的物化路径,但你正在存储父行的物化路径.以下是该行的物化路径实际应该如何.如果您将其存储为以下内容,则直接在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(它也有一些其他不错的属性)

Answer 2

我通常会为此创建一个额外的列,称为类似的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.这样,如果您想一次查询多个论坛(您可能不会),那么它仍然可以正确排序.

Answer 3

我不确定我理解为什么接受的解决方案根本没有任何意义.它可以工作,但它甚至比@Unreason的解决方案更简单,更低效(更多磁盘空间,更多索引等)(只是填充物化路径中的ID).

OP面临的整个场景似乎源于这样一个事实,正如@Unreason正确指出的那样,物化路径(MP)的实现是不正确的.OP已将MP提供给父节点,而不是当前节点.在接受的解决方案中,SortPath列通过提供到当前节点的物化路径来纠正这一点(这次使用日期 - 为什么？ - 而不是主键).

供参考,请参考以下摘录:

物化路径

在此方法中,每个记录都存储到根的整个路径.在前面的示例中,我们假设KING是根节点.然后,ename ='SCOTT'的记录通过路径SCOTT-> JONES-> KING连接到根.现代数据库允许将节点列表表示为单个值,但由于物化路径早在此之前就被发明,因此约定坚持与一些分隔符连接的普通字符串节点; 最经常 '.' 要么 '/'.

Answer 4

虽然@Unreason关于填充工作的答案,但我想提供另一种解决方案,我认为这是我自己对这个问题的发明.

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

用0填充到相同的长度肯定很容易获得这个目标.你拿两个数字,看看你的第一个非零字节.

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

请注意,填充和此缓存变量长度编码都不需要物化路径的分隔符,但为了便于阅读,它们通常包括在内.

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

但是如果你使用'二进制'字段,那么你可以做base256:而不是一个狡猾的编码只是把数字写成一系列字节,然后用字节流的长度作为单个字节作为整数.这将允许您编码任何小于2 ^ 2048左右的树.对于前256个节点,您使用两个字节,对于下一个65280,您正在查看三个字节.这已经非常有效了.

我提名这个utf8encode(x)功能.考虑一下!您需要下降到bitsorting而不是bytesorting,但这不会改变结果:找到最左边的零位.如果另一个字符串在那里有一个1,那么它将是一个更长的UTF-8编码,因此肯定会更大.如果他们在同一个地方有第一个零,那么我们有相同长度的位串,这对我们来说比较好.

这很好,但分离器呢.UTF-8算法在将其视为纯粹创建比特流的算法时可以处理31位数 - 因此它适用于包含少于20亿个节点的树.您的物化路径将是UTF-8编码数字的比特流,比较好:丢弃最左边相同的UTF-8编码数字,我们回到前一段.QED

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

总结一下:UTF-8最适合小树,并且比二十亿节点以下的base256差.除此之外,直到2 ^ 2048左右,前缀为长度为base256.除了那个带有前缀的长度的基础2141483647之外,除此之外什么都没有.