Postgresql 的 ltree 處理階層式資料的好幫手

階層式的資料,在日常中隨處可見.但是要怎樣儲存處理,
有幾種常見的方式, Adjacency List, 可以透過遞迴的
方式,在 Postgresql Oracle 以及現在8版的 MySQL
都可以處理.
另一種是 Nested Set 的方式,無需特殊功能,
新增或移動節點時,自給自足.
另一個方式是 Materialized Path,把路徑存起來,用空間換時間.
Postgresql 的 ltree 用此方式,方便大家使用此種方式,來儲存處理階層式資料.
另外還提供了 ltree_plpython3u , 可以整合進 plpython.

首先要建立 extension

create extension ltree;
CREATE EXTENSION
 
安裝好以後,可以在 contrib/ltree/ 目錄下找到 ltreetest.sql 

裡面會有一個簡單的範例.也是官網文件上的例子.

我們這次改用先看一些應用,再來探討運算子與函數.

create table tree1013a (
  id smallint generated always as identity
, node text not null
, path ltree not null
);

insert into tree1013a (node, path) values
('A', 'A'),
('B', 'A.B'),
('C', 'A.C'),
('D', 'A.B.D'),
('E', 'A.C.E'),
('F', 'A.C.F');

     A
  +--+--+
  B     C
  +   +-+-+
  D   E   F

大致上如上圖所示.


select * from tree1013a;
+----+------+-------+
| id | node | path  |
+----+------+-------+
|  1 | A    | A     |
|  2 | B    | A.B   |
|  3 | C    | A.C   |
|  4 | D    | A.B.D |
|  5 | E    | A.C.E |
|  6 | F    | A.C.F |
+----+------+-------+
(6 rows)

若是用 Adjacency List 要求出這棵小樹, Node A 底下(包含A)共有哪些節點? 
需要用遞迴語法,一來語法繁瑣,二來遞迴思考需要一段適應期.

在 ltree 有一個運算子, ltree @> ltree , return boolean
左邊的ltree 是否為 右邊ltree的祖先.

我們用它來協助計算吧.

select count(*)
  from tree1013a
 where 'A'::ltree @> path;
+-------+
| count |
+-------+
|     6 |
+-------+

列出 C節點 子樹下各節點

with ctree as (
select path cpath
  from tree1013a
 where node = 'C'
)
select t.*
  from tree1013a t
     , ctree
 where cpath @> path;
 
+----+------+-------+
| id | node | path  |
+----+------+-------+
|  3 | C    | A.C   |
|  5 | E    | A.C.E |
|  6 | F    | A.C.F |
+----+------+-------+
(3 rows)


也可以用 反向的 後裔運算子 <@

with ctree as (
select path cpath
  from tree1013a
 where node = 'C'
)
select t.*
  from tree1013a t
     , ctree
 where path <@ cpath;

+----+------+-------+
| id | node | path  |
+----+------+-------+
|  3 | C    | A.C   |
|  5 | E    | A.C.E |
|  6 | F    | A.C.F |
+----+------+-------+
(3 rows)

還可以用字串函數 strpos() 這招,注意到我們使用 ::varchar 轉型.
select *
  from tree1013a
 where strpos(path::varchar, 'C') = 3;

+----+------+-------+
| id | node | path  |
+----+------+-------+
|  3 | C    | A.C   |
|  5 | E    | A.C.E |
|  6 | F    | A.C.F |
+----+------+-------+
(3 rows)

接著來把 子樹 刪除

delete
  from tree1013a
 where 'A.C'::ltree @> path;

DELETE 3

剩下

select *
  from tree1013a;

+----+------+-------+
| id | node | path  |
+----+------+-------+
|  1 | A    | A     |
|  2 | B    | A.B   |
|  4 | D    | A.B.D |
+----+------+-------+
(3 rows)

rollback;
ROLLBACK

select *
  from tree1013a;

+----+------+-------+
| id | node | path  |
+----+------+-------+
|  1 | A    | A     |
|  2 | B    | A.B   |
|  3 | C    | A.C   |
|  4 | D    | A.B.D |
|  5 | E    | A.C.E |
|  6 | F    | A.C.F |
+----+------+-------+
(6 rows)

因為我在 psqlrc 中設定, \set AUTOCOMMIT OFF
所以沒有 commit 之前,這道 delete 是可以 rollback 的.
若沒這樣設定的,請注意先加上  begin transaction , 或是
直接下  \set AUTOCOMMIT OFF
確認變更後下 commit;

將 C 節點以下分家獨立.
先將 C 獨立為 root
這個先別急著下喔

update tree1013a
   set path = 'C'
 where path = 'A.C';

然後將原本 C 以下節點一個接一個下 update ....

當然我們不會這樣做,那是 SQL沒學好,迴圈跑到老.

聰明的SQL寫法,先要理解有哪些手段,而不是迴圈硬幹.
既然是層級資料,有一個回報層級的函數也是很合理的.

nlevel(ltree) , return integer

深度優先排序

select node
     , path
     , nlevel(path)
  from tree1013a
 order by path;
+------+-------+--------+
| node | path  | nlevel |
+------+-------+--------+
| A    | A     |      1 |
| B    | A.B   |      2 |
| D    | A.B.D |      3 |
| C    | A.C   |      2 |
| E    | A.C.E |      3 |
| F    | A.C.F |      3 |
+------+-------+--------+
(6 rows)

廣度優先排序
select node
     , path
     , nlevel(path)
  from tree1013a
 order by 3;
+------+-------+--------+
| node | path  | nlevel |
+------+-------+--------+
| A    | A     |      1 |
| B    | A.B   |      2 |
| C    | A.C   |      2 |
| D    | A.B.D |      3 |
| E    | A.C.E |      3 |
| F    | A.C.F |      3 |
+------+-------+--------+
(6 rows)

這時候要是有根據層級切割path的函數, 就好像 substr(),
最好是叫做 subpath 而且能指定 offset
像這樣 subpath(ltree, offset) 
就好辦多了.

select node
     , path
     , nlevel(path)
     , subpath(path, 1)
  from tree1013a
 where nlevel(path) >= 2
 order by 3;

+------+-------+--------+---------+
| node | path  | nlevel | subpath |
+------+-------+--------+---------+
| B    | A.B   |      2 | B       |
| C    | A.C   |      2 | C       |
| D    | A.B.D |      3 | B.D     |
| E    | A.C.E |      3 | C.E     |
| F    | A.C.F |      3 | C.F     |
+------+-------+--------+---------+
(5 rows)

既然有了 nlevel(), subpath() 兩個函數,
我們來看 node C 也就是 path 'A.C'::ltree 底下的

select node
     , subpath(path, 1)
     , subpath(path, nlevel('A.C'::ltree) -1)
  from tree1013a
 where path <@ 'A.C'::ltree;
+------+---------+---------+
| node | subpath | subpath |
+------+---------+---------+
| C    | C       | C       |
| E    | C.E     | C.E     |
| F    | C.F     | C.F     |
+------+---------+---------+
(3 rows)

我們先加入一個節點 G ,在節點 E 底下,用來提高一點複雜度

insert into tree1013a (node, path) values
('G', 'A.C.E.G');

select node
     , subpath(path, nlevel('A.C'::ltree) -1)
  from tree1013a
 where path <@ 'A.C'::ltree;

+------+---------+
| node | subpath |
+------+---------+
| C    | C       |
| E    | C.E     |
| F    | C.F     |
| G    | C.E.G   |
+------+---------+
(4 rows)

update tree1013a
   set path = subpath(path, nlevel('A.C'::ltree)-1) 
 where path <@ 'A.C'::ltree;
 
UPDATE 4

select * from tree1013a;
+----+------+-------+
| id | node | path  |
+----+------+-------+
|  1 | A    | A     |
|  2 | B    | A.B   |
|  4 | D    | A.B.D |
|  3 | C    | C     |
|  5 | E    | C.E   |
|  6 | F    | C.F   |
|  7 | G    | C.E.G |
+----+------+-------+
(7 rows)

commit; 
確認變化!

今天我們先探討到這裡,明天繼續愛與勇氣的冒險.

在Postgresql 我們還可以很任性的使用 emoji tree, 來當欄位名稱.