Postgres存储树形数据

碰到一个树形数据需要存储再数据控制，碰到以下两个问题：

• 在PG数据库中如何表达树形数据
• 如何有效率的查询以任意节点为Root的子树

测试数据

为了更加简单一些，我们将使用一下数据

Section A
    |--- Section A.1

Section B
    |--- Section B.1
    |--- Section B.1
               |--- Section B.1.1

简单的自引用

当设计自引用表(有时候自己join自己)。最简单明了的就是有一个parent_id字段。

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_id INTEGER REFERENCES section,
);
ALTER TABLE page ADD COLUMN parent_id INTEGER REFERENCES page;
CREATE INDEX section_parent_id_idx ON section (parent_id);

然后插入一些样例数据，用parent_id来关联其他节点

INSERT INTO section (id, name, parent_id) VALUES (1, 'Section A', NULL);
INSERT INTO section (id, name, parent_id) VALUES (2, 'Section A.1', 1);
INSERT INTO section (id, name, parent_id) VALUES (3, 'Section B', NULL);
INSERT INTO section (id, name, parent_id) VALUES (4, 'Section B.1', 3);
INSERT INTO section (id, name, parent_id) VALUES (5, 'Section B.2', 3);
INSERT INTO section (id, name, parent_id) VALUES (6, 'Section B.2.1', 5);

再进行一些简单的查询时，这个方法非常好使。比如我们要查询Section B的所有一级子节点

SELECT * FROM section WHERE parent = 3

但是如果要做复杂一些的查询时，就很蛋疼了，查询中会有许多复杂和递归的问题。比如我们要查询Section B的所有子节点

WITH RECURSIVE nodes(id,name,parent_id) AS (
    SELECT s1.id, s1.name, s1.parent_id
    FROM section s1 WHERE parent_id = 3
        UNION
    SELECT s2.id, s2.name, s2.parent_id
    FROM section s2, nodes s1 WHERE s2.parent_id = s1.id
)
SELECT * FROM nodes;

这种方案解决了第一个问题，但是没有解决第二个问题(高效的找到子树)

Ltree extension

ltree extension来查询树形数据是个不错的选择，在自引用的关系表中表现的更加优秀。用ltree重新建一个表。我将用每一个section的主键作为ltree路径中的标识。用root标识顶节点。

CREATE EXTENSION ltree;

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_path LTREE
);

CREATE INDEX section_parent_path_idx ON section USING GIST (parent_path);

INSERT INTO section (id, name, parent_path) VALUES (1, 'Section 1', 'root');
INSERT INTO section (id, name, parent_path) VALUES (2, 'Section 1.1', 'root.1');
INSERT INTO section (id, name, parent_path) VALUES (3, 'Section 2', 'root');
INSERT INTO section (id, name, parent_path) VALUES (4, 'Section 2.1', 'root.3');
INSERT INTO section (id, name, parent_path) VALUES (4, 'Section 2.2', 'root.3');
INSERT INTO section (id, name, parent_path) VALUES (5, 'Section 2.2.1', 'root.3.4');

OK，一切搞定，我们可以用ltree操作符@>和<@来查询Section B的所有子节点

SELECT * FROM section WHERE parent_path <@ 'root.3';

但是还是有一些小问题：

• 在parent_id这种方案中，我们有外键约束来维系节点之间的关系，但是在Ltree版本中我们是没有这种约束的
• 维户这个树每一个路径都是有效，这其实是非常痛苦的。比如你的树变大了，比如你操作的是很久之前的树。总之搞不好有时候你查出来的是孤儿节点

最终解决方案

为了解决上章的两个小问题，我们需要一种混搭(有parent_id还要高效易于维护)。为了达到这个目标，我们设计一个trigger来封装树操作的过程，更新树仅仅靠更新parent_id。

CREATE EXTENSION ltree;

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_id INTEGER REFERENCES section,
    parent_path LTREE
);

CREATE INDEX section_parent_path_idx ON section USING GIST (parent_path);
CREATE INDEX section_parent_id_idx ON section (parent_id);

CREATE OR REPLACE FUNCTION update_section_parent_path() RETURNS TRIGGER AS $$
    DECLARE
        path ltree;
    BEGIN
        IF NEW.parent_id IS NULL THEN
            NEW.parent_path = 'root'::ltree;
        ELSEIF TG_OP = 'INSERT' OR OLD.parent_id IS NULL OR OLD.parent_id != NEW.parent_id THEN
            SELECT parent_path || id::text FROM section WHERE id = NEW.parent_id INTO path;
            IF path IS NULL THEN
                RAISE EXCEPTION 'Invalid parent_id %', NEW.parent_id;
            END IF;
            NEW.parent_path = path;
        END IF;
        RETURN NEW;
    END;
$$ LANGUAGE plpgsql;


CREATE TRIGGER parent_path_tgr
    BEFORE INSERT OR UPDATE ON section
    FOR EACH ROW EXECUTE PROCEDURE update_section_parent_path();

这样就爽多了.^_^.