postpresql 树形结构

原文网址
关系型数据库对树形结构没有一个很好的解决方案，本文针对 postgresql 数据库，列出以下解决方案:
jsonb 类型
xml 类型
邻接表(Adjacency List)
路径枚举(The Path to a Node)
先根遍历树(Modified Preorder Tree Traversal)

本文所有代码均以下图为例：

foods tree
jsonb
postgresql 自从 9.4 版本加入 jsonb 类型，用其表示树形结构很方便：
create table foods ( food jsonb);insert into foods values ( '{ "Fruit": { "Red": [ { "name": "Cherry" } ], "Yellow": [ { "name": "Banana" } ] }, "Meat": [ { "name": "Beef" }, { "name": "Pork" } ] }');
postgresql 提供了大量的对 jsonb 类型进行查询、修改操作。
xml
xml 本身就是一个树形结构，postgresql 内部已经实现了 xml 类型，用它来表示树形结构也是可以的：
create table foods ( food xml);insert into foods values ( '<Food> <Fruit> <Red> <name>Cherry</name> </Red> <Yellow> <name>Banana</name> </Yellow> </Fruit> <Meat> <name>Beef</name> <name>Pork</name> </Meat> </Food>');
postgresql 也针对 xml 类型提供了许多 xml 相关的操作函数。
邻接表
邻接表就是把所有的节点都放在一张表中，用一个属性记录其父节点：
create table foods ( id integer, name varchar(15), parent integer);insert into foods(id, name) values (1, 'Food');insert into foods(id, name, parent) values (2, 'Fruit', 1);insert into foods(id, name, parent) values (3, 'Meat', 1);insert into foods(id, name, parent) values (4, 'Red', 2);insert into foods(id, name, parent) values (5, 'Yellow', 2);insert into foods(id, name, parent) values (6, 'Cherry', 4);insert into foods(id, name, parent) values (7, 'Banana', 5);insert into foods(id, name, parent) values (8, 'Beef', 3);insert into foods(id, name, parent) values (9, 'Pork', 3);
遍历树形结构可以用通用表表达式(CTE, Common Table Expressions)来实现：
with recursive tree as ( select id, name from foods where id = 1 union all select origin.id, tree.name || '>' || origin.name from tree join foods origin on origin.parent = tree.id)select * from tree; id | name----+-------------------------- 1 | Food 2 | Food>Fruit 3 | Food>Meat 4 | Food>Fruit>Red 5 | Food>Fruit>Yellow 8 | Food>Meat>Beef 9 | Food>Meat>Pork 6 | Food>Fruit>Red>Cherry 7 | Food>Fruit>Yellow>Banana
路径枚举
路径枚举就是在 foods 表中设置一个 path 属性，用来存储从根节点到当前结点的路径，用分隔符隔开， 尽管 path 可以是 text 类型，但是 postgresql contrib 中的 ltree 模块专门针对这种情况定义了 ltree 类型：
create extension ltree;create table foods ( path ltree);insert into foods values('Food');insert into foods values('Food.Fruit');insert into foods values('Food.Meat');insert into foods values('Food.Fruit.Red');insert into foods values('Food.Fruit.Yellow');insert into foods values('Food.Fruit.Red.Cherry');insert into foods values('Food.Fruit.Yellow.Banana');insert into foods values('Food.Meat.Beef');insert into foods values('Food.Meat.Pork');
先根遍历树
用两个数字(left 和 right)对每个节点进行编码如下：
create table foods ( name text, left integer, right integer);insert into foods values('Food', 1, 18);insert into foods values('Fruit', 2, 11);insert into foods values('Meat', 12, 17);insert into foods values('Red', 3, 6);insert into foods values('Yellow', 7, 10);insert into foods values('Cherry', 4, 5);insert into foods values('Banana', 8, 9);insert into foods values('Beaf', 13, 14);insert into foods values('Pork', 15, 16);
foods preorder tree
规则如下：
left 的数值小于该节点的所有后代的 left
right 的数值大于该节点的所有后代 right