7

我有这个使用 PostgreSQL 的 ltree 模块构建的物化路径树结构。

  • id1
  • id1.id2
  • id1.id2.id3
  • id1.id2.id5
  • id1.id2.id3.id4 ...等

我当然可以轻松地使用 ltree 从整个树或特定路径/子路径中获取所有节点，但是当我这样做时，自然得到的是很多行（这等于结束.. Golang/您使用的任何编程语言）

我所追求的是获取树 - 理想情况下从某个开始和结束路径/点 - 作为分层 JSON 树对象等

{
  "id": 1,
  "path": "1",
  "name": "root",
  "children": [
    {
      "id": 2,
      "path": "1.2",
      "name": "Node 2",
      "children": [
        {
          "id": 3,
          "path": "1.2.3",
          "name": "Node 3",
          "children": [
            {
              "id": 4,
              "path": "1.2.3.4",
              "name": "Node 4",
              "children": [

              ]
            }
          ]
        },
        {
          "id": 5,
          "path": "1.2.5",
          "name": "Node 5",
          "children": [

          ]
        }
      ]
    }
  ]
}

我从线性（非分层）行/数组/切片结果集中知道，我当然可以在 Golang 中爆炸路径并在那里创建必要的业务逻辑来创建这个 json，但是如果有一个方便的，它肯定会好得多直接用 PostgreSQL 实现这一点的方法。

那么，您将如何在 PostgreSQL 中将 ltree 树结构输出到 json - 可能是从开始到结束的路径？

如果你不知道 ltree，我想这个问题可以更概括为“Materalized path tree to hierachical json”

此外，我正在考虑在除了 ltree 路径之外的所有节点上添加 parent_id 的想法，因为至少那时我将能够使用递归调用使用该 id 来获取我猜想的 json ......我也有考虑过在该 parent_id 上放置一个触发器，以根据父 ID 发生更改的时间来管理路径（保持更新） - 我知道这是另一个问题，但也许你也可以告诉我你的意见，关于这个？

我希望一些天才可以帮助我解决这个问题。:)

为了您的方便，这里有一个示例创建脚本，您可以使用它来节省时间：

CREATE TABLE node
(
  id bigserial NOT NULL,
  path ltree NOT NULL,
  name character varying(255),
  CONSTRAINT node_pkey PRIMARY KEY (id)
);

INSERT INTO node (path,name) 
VALUES ('1','root');

INSERT INTO node (path,name) 
VALUES ('1.2','Node 1');

INSERT INTO node (path,name) 
VALUES ('1.2.3','Node 3');

INSERT INTO node (path,name) 
VALUES ('1.2.3.4','Node 4');

INSERT INTO node (path,name) 
VALUES ('1.2.5','Node 5');
4

2 回答 2

4

我能够找到并稍微更改它以使用 ltree 的物化路径，而不是像邻接树结构中经常使用的父 ID。

虽然我仍然希望有更好的解决方案，但我想这会完成工作。

我觉得除了 ltree 路径之外，我还必须添加 parent_id，因为这当然不像引用父 ID 那样快。

这要归功于这个人的解决方案，这是我使用 ltree 的子路径、ltree2text 和 nlevel 稍作修改的代码，以实现完全相同的效果：

WITH RECURSIVE c AS (
    SELECT *, 1 as lvl
    FROM node
    WHERE id=1
  UNION ALL
    SELECT node.*, c.lvl + 1 as lvl
    FROM node
    JOIN c ON ltree2text(subpath(node.path,nlevel(node.path)-2 ,nlevel(node.path))) = CONCAT(subpath(c.path,nlevel(c.path)-1,nlevel(c.path)),'.',node.id)
),
maxlvl AS (
  SELECT max(lvl) maxlvl FROM c
),
j AS (
    SELECT c.*, json '[]' children
    FROM c, maxlvl
    WHERE lvl = maxlvl
  UNION ALL
    SELECT (c).*, json_agg(j) children FROM (
      SELECT c, j
      FROM j
      JOIN c ON ltree2text(subpath(j.path,nlevel(j.path)-2,nlevel(j.path))) = CONCAT(subpath(c.path,nlevel(c.path)-1,nlevel(c.path)),'.',j.id)
    ) v
    GROUP BY v.c
)
SELECT row_to_json(j)::text json_tree
FROM j
WHERE lvl = 1;

不过，到目前为止，此解决方案存在一个大问题.. 请参阅下图了解错误（缺少节点 5）：

JSON 对象中缺少节点 5

于 2014-11-18T17:06:50.710 回答
2

节点 5 没有出现的原因是因为它是一个不在最大级别的叶节点，并且随后的加入条件将其排除在外。

递归遍历树的真正基本情况是一个节点，它是一个叶子。通过从最大级别开始，隐式选择所有叶节点，但会错过出现在较低级别的叶节点。这是我们想要在伪代码中做的事情：

for each node:
   if node is leaf, then return empty array
   else return the aggregated children

我发现这很难用 SQL 来表达。相反，我使用了相同的策略，从最高级别开始，然后一次提升一个级别。但是，当我高于最大级别时，我添加了一些代码来处理叶节点基本情况。

这是我想出的：

WITH RECURSIVE c AS (
  SELECT
    name,
    path,
    nlevel(path) AS lvl
  FROM node
),
maxlvl AS (
  SELECT max(lvl) maxlvl FROM c
),
j AS (
  SELECT
    c.*,
    json '[]' AS children
  FROM c, maxlvl
  WHERE lvl = maxlvl
  UNION ALL
  SELECT
    (c).*,
    CASE
      WHEN COUNT(j) > 0 -- check if returned record is null
        THEN json_agg(j) -- if not null, aggregate
      ELSE json '[]' -- if null, then we are a leaf, so return empty array
    END AS children
  FROM (
    SELECT
      c,
      CASE
        WHEN c.path = subpath(j.path, 0, nlevel(j.path) - 1) -- c is a parent of the child
          THEN j
        ELSE NULL -- if c is not a parent, return NULL to trigger base case
      END AS j
    FROM j
    JOIN c ON c.lvl = j.lvl - 1
  ) AS v
  GROUP BY v.c
)
SELECT row_to_json(j)::text AS json_tree
FROM j
WHERE lvl = 1;

我的解决方案只使用path（以及从路径派生的级别）。它不需要name或id正确地递归。

这是我得到的结果（我包括一个节点 6 以确保我在同一级别处理多个叶节点）：

{
  "name": "root",
  "path": "1",
  "lvl": 1,
  "children": [
    {
      "name": "Node 1",
      "path": "1.2",
      "lvl": 2,
      "children": [
        {
          "name": "Node 5",
          "path": "1.2.5",
          "lvl": 3,
          "children": []
        },
        {
          "name": "Node 3",
          "path": "1.2.3",
          "lvl": 3,
          "children": [
            {
              "name": "Node 6",
              "path": "1.2.3.4",
              "lvl": 4,
              "children": []
            },
            {
              "name": "Node 4",
              "path": "1.2.3.4",
              "lvl": 4,
              "children": []
            }
          ]
        }
      ]
    }
  ]
}
于 2020-01-24T00:19:52.363 回答