用postgresql实现树形结构

关系型数据库对树形结构没有一个很好的解决方案，本文针对 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