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();

這樣就爽多了.^_^.