主页 / 问题 / 629090
Accepted
Xander
Asked:2020-02-17 17:25:29 +0800 CST2020-02-17 17:25:29 +0800 CST

层次结构的同步

  • 772

有一个分层数据结构，它会根据从外部源上传的内容定期更新。卸载可以是完整的，也可以针对一个特定节点。

每个节点在上传时都有一个布尔值“隐藏”属性。另外，节点有一些内容，可能是空的。此外，每个节点都有一个布尔“空”属性，需要在同步时重新计算。

如果节点匹配所有条件，则必须将空属性设置为 true：

  • 节点内容为空
  • 节点没有非空和非隐藏的孩子

在卸载的时候，保证子进程跟在他们的父进程之后，所以之前empty的定义是这样的：

该程序按顺序进行卸载，每个节点都添加到数据库或更新它（如果它已经存在）。查看上传内容是否为空内容。在其基础中选择该节点的既不为空也不隐藏的直接子节点。基于此将值设置为空。

之后，程序依次沿着该节点的父节点链上升，并为它们执行相同的过程。这是必要的，因为卸载的未处理部分将包含有关子项的信息，如果他们的列表或空值和隐藏值被更新，那么这可能会使父项的空值无效，并且需要重新计算。

我知道该算法看起来不是最优的，但我没有编写它。

现在任务来了：使节点可以作为另一个节点的别名（链接）。这是实现并行层次结构所必需的。

相应地，在空计算中，必须考虑到如果引用非空节点，则该节点必须是非空的。问题是别名可以出现在它所指的节点之前和之后的卸载中。

考虑到所描述的要求，实现这种结构的最佳方法是什么？

UPD：PosgreSQL 通过 sqlalchemy 用作数据库。因此，所有同步工作都由 Python 脚本执行。

节点表有字段：id、parent_id、link_id、hidden、empty，以及一些不以任何方式参与此任务的字段。

parent_id 和 link_id 是来自同一张表的 id。

还有一个包含内容的表格，每个节点从中获取一定数量的元素。

алгоритм

1 个回答

  1. Best Answer

    添加一个changed类型的字段int。我们建立一个部分索引：在列上create index tree_change on tree(changed) where changed is not null。从外部加载数据时，直接changed=1为所有内容或隐藏发生变化的记录设置字段应更改的方式。在这个阶段根本不考虑记录的层次结构。所有新条目也有.emptychanged=1

    加载外部数据后，我们执行以下查询：

    with recursive Q(id, parent_id, link_id, changed) as(
  select id, parent_id, link_id, changed from tree where changed=1
 union all
  select t.id, t.parent_id, t.link_id, Q.changed+1
    from Q, tree t where t.id=Q.parent_id or t.link_id=Q.id
)
UPDATE tree AS t
   SET changed = n.changed
  FROM (
    select id, max(changed) changed
      from Q where changed>1
     group by id
  ) n
 WHERE t.id = n.id;

    它为层次结构中的所有父记录（以及它link_id指示更改的记录）公开changed比子记录多 1。事实上，这是树中从修改后的节点到给定父节点的转换次数。如果同一节点与多个更改的子元素的距离不同，则取其中的最大值。

    因此，将为所有（分层）依赖于已更改节点的节点设置已更改。

    然后，在循环中，当更新至少更改了一条记录时，我们执行以下请求：

    update tree t
   set empty=(case when content is not null then 0
              else (select coalesce(min(t1.empty::int),1)
                      from tree t1
                     where t1.parent_id=t.id or t1.id=t.link_id)
             end)::boolean,
       changed=NULL
 where changed=$N

    哪里$N是循环迭代的序号从1到changed第一个请求后收到的最大值（直接取最大值是没有意义的，改变记录本身就表明这样的数字仍然存在）。

    循环中的每个查询都会根据节点本身（首先）及其所有直接子节点（如果节点本身没有内容）的状态为树节点计算空值。没有必要在层次结构中走得更深，因为只有在所有孩子都重新计算后才会更新父母（因为孩子显然有一个更小的changed）。

    我没有考虑字段值hidden，将其添加到第二个请求的状态计算逻辑中。

    • 1

相关问题