在 PostgreSQL 中表示一棵树

在 PostgreSQL 中表示一棵树 · I/O OVER 转载自我博客

近在尝试写一个笔记本，类似于 org-mode 以及 workflowy 的感觉，支持笔记的无穷层级嵌套。所以天然形成了一个树结构。

对我来说这种结构的笔记本非常适合管理各种复杂的信息。

闲话少说。我在前端采用了imutable数据结构储存信息，但是在后端则需要找到一种储存树状数据的方式。MongoDB似乎有这些功能，但是我审美上难以接受这个项目。想了一下关于SQL和NoSQL的诸多梗，还是使用传统的SQL来表示数据了。

SQL数据库表示树状数据已经有很多资料了，这篇知乎回答帮了我很大的忙。

Adjacency List：每一条记录存parent_id
Path Enumerations：每一条记录存整个tree path经过的node枚举
Nested Sets：每一条记录存 nleft和nright
Closure Table：维护一个表，所有的tree path作为记录进行保存。

Adjacency List 在查询所有后代的时候需要递归查询。本来中意 Closure Table，也就是另外维护一个查询后代关系的表，但是需要更多的空间。

通过 stack overflow，我知道 PostgreSQL有一个用户贡献的扩展叫做 ltree。从方法上，其实不外乎是 Path Enumerations，i.e. 把经过的路径记录在一个字段上。但是因为是精心设计的用来表示树的字段，所以PostgreSQL可以高效地索引和搜索树状数据，并且有很多方便的操作。

CREATE EXTENSION IF NOT EXISTS ltree; -- 启用扩展

CREATE TABLE nodes (
    id uuid PRIMARY KEY,
    path ltree NOT NULL UNIQUE,
);

CREATE INDEX node_path ON nodes USING GIST (path);