在数据库中存储树时，常见的存储结构有以下几种：
常见存储结构
邻接列表
每个节点都有一个指向其父节点(pid)的引用。这种方法简单直观，也是最容易理解和常用的，但在获取整棵树或子树时可能需要多次查询。
存储结构
一般表结构如下：
CREATE TABLE tree (id INT PRIMARY KEY,pid INT,name VARCHAR(100),FOREIGN KEY (pid) REFERENCES nodes(id)
);
示例数据如下：
| id | pid | name |
|---|---|---|
| 1 | NULL | root |
| 2 | 1 | A |
| 3 | 1 | B |
| 4 | 1 | C |
| 5 | 2 | A-1 |
| 6 | 2 | A-2 |
| 7 | 2 | A-3 |
表示的树如下：
- root
- A
- A-1
- A-2
- A-3
- B
- C
- A
需要注意
pid树的查询和删除操作涉及到的递归操作，无法通过优化SQL解决，必须通过程序递归实现，这也意味着，在复杂树查询和操作时，需要在客户端与数据库之间频繁传输数据，效率较低。
优缺点
邻接列表模型,有明也简称为pid树,是最简单和常见的树结构存储模型。
- 查询效率低
当需要以下查询时,一般需要进行递归查询，效率较低：
- 查询整棵树或子树
- 查询某个节点的所有后代
- 查询某个节点的祖先节点
- 删除节点效率低
同样的，当我们要删除一个节点时，也需要递归删除其所有子节点，效率较低。
比如我们要删除节点A(id=100)，只执行DELETE tree WHERE id=100 AND pid=100是不够的，因为A可能还存在多级后代节点，因此还需要递归删除其所有子节点,效率比较低下。
- 无序树
树节点的之间的无序的，为此我们需要额外的字段来维护节点之间的顺序。
因此，在实际使用需要为表结构添加一个order字段，用来代表同一层级内节点的顺序，从而使得树变成有序树。
| id | pid | order | name |
|---|---|---|---|
| 1 | NULL | 1 | root |
| 2 | 1 | 1 | A |
| 3 | 1 | 2 | B |
| 4 | 1 | 3 | C |
| 5 | 2 | 1 | A-1 |
| 6 | 2 | 2 | A-2 |
| 7 | 2 | 3 | A-3 |
然后，我们通过select * from tree where pid=1 order by order来查询A的所有有序子节点集。
问题是，如果整棵树是有序的呢？
如果整棵树是有序的，则order字段必须是扩展到全树，如下：
| id | pid | order | name |
|---|---|---|---|
| 1 | NULL | 1 | root |
| 2 | 1 | 2 | A |
| 3 | 1 | 7 | B |
| 4 | 1 | 8 | C |
| 5 | 2 | 4 | A-1 |
| 6 | 2 | 5 | A-2 |
| 7 | 2 | 6 | A-3 |
这样，我们就可以通过select * from tree order by order来查询整棵树的有序节点集。
但是问题来了，如果我们要调整树结构，比如将节点A移动到节点B下，那么我们就需要调整order字段，这样会导致大量的数据更新，效率较低。同时也无法避免order字段的唯一性问题，因此order字段的值必须是唯一的，这也增加了调整树结构的难度。
更糟糕的是， 始终无法避免递归调用更新的问题。
所以pid树的要实现完全的有序树是比较麻烦的。
- 更新树结构
pid树需要调整树结构时效率是比较高的。
比如将节点A移动到节点B下 ，只需要将节点A的pid修改为B的id即可。
但是由于其是无序树，所以如果要将节点A移动为节点B的下一个兄弟节点，则比较麻烦，需要额外的处理。
路径枚举
每个节点都保存了从根节点到自己的路径。这种方法可以方便地查询子树，但在插入或删除节点时需要更新大量数据。
存储结构
CREATE TABLE nodes (id INT PRIMARY KEY,path VARCHAR(255),name VARCHAR(100)
);
示例数据如下：
| id | path | name |
|---|---|---|
| 1 | /root | root |
| 2 | /root/A | A |
| 3 | /root/B | B |
| 4 | /root/C | C |
| 5 | /root/A/A-1 | A-1 |
| 6 | /root/A/A-2 | A-2 |
| 7 | /root/A/A-3 | A-3 |
优缺点
- 子树查询效率高
由于其在每个节点都保存了从根节点到自己的路径，因此查询子树非常方便，只需要一次查询即可。
比如查询节点A的所有子节点，只需要执行如下SQL即可：
select * from nodes where path like '/A/B%'
- 路径组成
首要问题是我们该使用哪个字段来表示和组合路径，一般来说，我们可以使用id或者name来组合路径。
-
如果使用
id字段，一般也就表的主键，这样可以保证路径的唯一性。但是id不能使用UUID之类的字段，否则path字段会变得非常长。也不能使用自增字段字段，因此其id值不可预测。所以只能使用人工分配的数字值，这就比较麻烦。 -
如果使用
name字段，一般来说name字段是唯一的，但是name字段可能会变化，这样会导致path字段的变化，因此需要额外的处理。 -
同级路径名称重名
路径组成字段在同级中不允许存在重名。如果存在重名，那么就会导致path字段的唯一性问题，因此path字段的值必须是唯一。
- 路径长度限制
path字段的长度可能有限制的，因此我们需要限制树的深度。
- 无序树
同样地，树节点的之间的无序的，与pid树一样，要维护一棵有序树也是比较麻烦的。
- 更新树结构
路径枚举模型下，如果需要调整树结构，比如将节点/root/A移动到节点/root/B下。
- 首先需要将节点
/root/A的所有子节点的path字段修改为/root/B/A/开头的路径。对应的SQL语句如下：
update nodes set path = replace(path,'/root/A/','/root/B/A/') where path like '/root/A/%'
- 然后将节点
/root/A的path字段修改为/root/B/A。对应的SQL语句如下：
update nodes set path = '/root/B/A' where path = '/root/A'
左右值
存储结构
每个节点都有两个数字，代表了一个范围，这个范围内的所有节点都是它的子节点。这种方法可以方便地查询子树和父节点，但在插入或删除节点时需要更新大量数据。
CREATE TABLE nodes (id INT PRIMARY KEY,leftValue INT,rightValue INT,name VARCHAR(100)
);
示例数据如下：
| id | lft | rgt | name |
|---|---|---|---|
| 1 | 1 | 14 | root |
| 2 | 2 | 9 | A |
| 3 | 10 | 11 | B |
| 4 | 12 | 13 | C |
| 5 | 3 | 4 | A-1 |
| 6 | 5 | 6 | A-2 |
| 7 | 7 | 8 | A-3 |
表示的树如下：
- root
- A
- A-1
- A-2
- A-3
- B
- C
- A
优缺点
左右值结构是一种非常高效的树存储结构，它可以方便地查询子树和父节点。
基本原理是给每个节点分配两个数字，代表了一个范围，这个范围内的所有节点都是它的子节点。
- 高效查询
左右值结构可以方便地查询子树和父节点，比如查询节点A的所有子节点，只需要执行如下SQL即可：
select * from nodes where lft > 2 and rgt < 9
左右值结构除了可以方便查询子树外，还可以方便查询：
- 查询某个节点的所有后代
- 查询某个节点的祖先节点
- 查询整棵树
- 查询子树节点数量
- 查询兄弟节点
最大的特点就是可以避免pid树面临的的递归查询，效率非常高。
- 有序树
左右值结构表示的树天然就是有序树，因此不需要额外的字段来维护节点之间的顺序。
- 更新树结构
由于树是通过左右值来表示的，节点的移动、更新、删除等操作均会造成相关节点的左右值的变化，因此调整树结构时，需要更新大量数据。
每个更新操作均可能涉到多条SQL的执行，因此效率较低。
比如添加子节点：
LOCK TABLE Tree WRITE;
SELECT @parent_id := node_id, @myLeft := lft FROM Tree WHERE name = "Food";
UPDATE Tree SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE Tree SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO Tree( name, lft, rgt) VALUES( "Fruit", @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;
更多可以查看这里
闭包表
存储结构
使用一个单独的表来存储每个节点与其所有祖先节点之间的关系。这种方法可以方便地查询子树和父节点，但需要额外的存储空间。
CREATE TABLE nodes (id INT PRIMARY KEY,name VARCHAR(100)
);CREATE TABLE closure (ancestor INT,descendant INT,depth INT,PRIMARY KEY (ancestor, descendant),FOREIGN KEY (ancestor) REFERENCES nodes(id),FOREIGN KEY (descendant) REFERENCES nodes(id)
);
示例数据如下：
nodes 表：
| id | name |
|---|---|
| 1 | root |
| 2 | A |
| 3 | B |
| 4 | C |
| 5 | A-1 |
| 6 | A-2 |
| 7 | A-3 |
closure 表：
| ancestor | descendant | depth |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 1 | 3 | 1 |
| 1 | 4 | 1 |
| 1 | 5 | 2 |
| 1 | 6 | 2 |
| 1 | 7 | 2 |
| 2 | 2 | 0 |
| 2 | 5 | 1 |
| 2 | 6 | 1 |
| 2 | 7 | 1 |
| 3 | 3 | 0 |
| 4 | 4 | 0 |
| 5 | 5 | 0 |
| 6 | 6 | 0 |
| 7 | 7 | 0 |
优缺点
- 高效查询
通过Join操作也可以比较方便进行查询操作，比如查询节点A的所有子节点，只需要执行如下SQL即可：
select * from nodes n join closure c on n.id=c.descendant where c.ancestor=2
- 空间换时间
相对于前几种存储结构，ClosureTable结构是一种空间换时间的算法，这也意味着
- 需要额外的存储空间。
- 需要额外的
Join操作。
总结
邻接列表模型最简单直观，但是无法避免的递归查询让其只能用在一些简单的场合。路径枚举模型查询效率高，但路径字段选择比较重要，当路径字段更新或重名时，面临很大的问题，所以并不推荐。左右值模型查询效率高，但是严格的左右值的完整性，使得调整树结构时，需要更新大量数据，效率较低，所以树的结构完整性比较脆弱，任意更新操作均需要进行锁表操作，否则任何错误的左右值更新均可能导致树结构损坏。闭包表模型查询效率高，但需要额外的存储空间。
总体而言，在以查询为主的场景中，本人更推荐使用左右值的存储结构，因为查询的确是比较方便，并且天然是有序的。
最后给大家推荐一个基于Nodejs下使用基于左右值算法的树存储管理库FlexTree
