使用 PostgreSQL ltree 对节点进行排序

Question

假设我有一个使用 ltree 存储的树：

   id   |   path   |   sort   
------------------------------
0       |0         |1
1       |0.1       |2
2       |0.1.2     |3
3       |0.1.3     |1
4       |0.1.4     |2
5       |0.5       |3
6       |0.6       |1

我想选择节点，以便：

1. 子节点紧跟在父节点之后；
2. 具有较小“排序”值的兄弟节点首先出现；

像这样：

   id   |   path   |   sort   
------------------------------
0       |0         |1
6       |0.6       |1
1       |0.1       |2
3       |0.1.3     |1
4       |0.1.4     |2
2       |0.1.2     |3
5       |0.5       |3

第一个要求是可能的ORDER BY path，但我不知道如何实现第二个要求，这甚至可能吗？

Answer 1

我正在用第二个 ltreesort_path和一些触发器解决这个问题。

最终，您将对 sort_path 树进行排序，其值基于所有祖先的排序列的 lpad 加上当前行的排序列的 lpad。

   id   |   path   |   rank   |  sort_path
--------------------------------------------
0       |0         |1         | 0001
6       |0.6       |1         | 0001.0001
1       |0.1       |2         | 0001.0002
3       |0.1.3     |1         | 0001.0002.0001
4       |0.1.4     |2         | 0001.0002.0002
2       |0.1.2     |3         | 0001.0002.0003
5       |0.5       |3         | 0001.0003

顺便说一句，即使您拥有的简单路径排序也不完全正确，一旦遇到两位数的路径段，您就会遇到麻烦，因为路径排序是基于 alpha 的，而不是数字的。

请注意，一个完整的解决方案包括一个触发器，当任何父节点行的排序值更改时，该触发器会重新计算所有后代的 sort_path 值。

示例实现：

CREATE EXTENSION IF NOT EXISTS ltree;

CREATE TABLE tree_nodes (path LTREE, rank INT, sort_path LTREE);

CREATE OR REPLACE FUNCTION calc_sort_path(tree_path LTREE, sibling_rank INT) RETURNS LTREE AS $$
DECLARE
  sort_ranks TEXT[];
  sort_path LTREE;
  ancestor RECORD;
BEGIN
  -- Default to the segment text (prepended with underscore).
  -- If some ancestors are missing, this ensures the children will still sort together.
  FOR iterator IN 1..NLEVEL(tree_path) LOOP
    sort_ranks[iterator] := '_' || SUBPATH(tree_path, iterator-1, 1)::TEXT;
  END LOOP;
  -- Format a sort rank path segment for each ancestor.
  FOR ancestor IN
    SELECT NLEVEL(tree_nodes.path) AS level, tree_nodes.rank FROM tree_nodes
      WHERE tree_nodes.path @> tree_path AND tree_nodes.path != tree_path
  LOOP
    sort_ranks[ancestor.level] := LPAD(ancestor.rank::TEXT, 4, '0');
  END LOOP;
  -- Format a final sort rank path segment for this leaf node.
  sort_ranks[NLEVEL(tree_path)] := LPAD(sibling_rank::TEXT, 4, '0');
  -- Convert array to LTREE path.
  SELECT STRING_AGG(padded_rank, '.')::LTREE INTO sort_path FROM
    (SELECT UNNEST(sort_ranks) AS padded_rank) path_ranks;

  RETURN sort_path;
END
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION update_sort_paths() RETURNS trigger AS $$
DECLARE
  has_changed BOOLEAN;
BEGIN
  has_changed := TG_OP = 'UPDATE' AND (OLD.path IS DISTINCT FROM NEW.path OR OLD.rank IS DISTINCT FROM NEW.rank);
  IF (TG_OP = 'DELETE' OR has_changed) THEN
    UPDATE tree_nodes SET sort_path = calc_sort_path(path, rank) WHERE OLD.path @> path;
  END IF;
  IF (TG_OP = 'INSERT' OR has_changed) THEN
    UPDATE tree_nodes SET sort_path = calc_sort_path(path, rank) WHERE NEW.path @> path;
  END IF;
  RETURN NULL;
END;
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS on_rank_change ON tree_nodes;
CREATE TRIGGER on_rank_change AFTER INSERT OR UPDATE OR DELETE ON tree_nodes
    FOR EACH ROW EXECUTE PROCEDURE update_sort_paths();