Web中常见的四种树形结构

写在前面

最近开发博客的时候Tag Model想写成树形结构,翻了一些博客文章,写篇小结,仅供参考。


Web中常见的四种树形结构

  • Adjacency List::记录父节点parent_id(变种加上深度值)
  • Path Enumerations:记录整个Node Path
  • Closure Table:专门一张表维护Path
  • Nested Sets:记录左值和右值

基本上web中最常见的就是这四种mysql设计。

Alt text

各方面的比较图


Adjacency List

这是最常见也是最简单的一种方式,仅仅加上一个parent_id就可以。

1
| node_id | parent_id |
CRUD方面

由于互相之间的关系只由一个parent_id维护,所以增删改都是非常容易,只需要改动和他直接相关的记录就可以。
但是,查询和展现开销比较大,举个例子,如果想要返回所有水果,也就是水果的所有子孙节点,看似很简单的操作,就需要用到duang一堆递归了。所以异步加载这个特性也不太友好,天生不适合,不如一次性返回整个数。

如果数据量很有限,那么这是一个很好(简单暴力)的选择。(比如一个博客程序的tags归类)

Path Enumerations

将整个Node Path作为一个字段,单独存储

这样可以改善一些Adjacency List查询方面的的缺陷,加入类似于A-B-C-D这样的路径字段,可以让查询子孙节点,查询树结构中的一部分,这样的操作更加简单。
还有类似的改进方案是加入level值,有时候也被命名为depth,也就是代表是第几层。也可以实现类似的效果。

不过,查询只能说是相对高效。


Closure Table

这和上面的Path思路一致,但是不同的是用单独的一张表,维护Path

参考文章 Closure Tables for Browsing Trees in SQL

用comment表煮个栗子

1
2
3
4
5
6
7
8
9
comment
- id
- name
- parent
- rank
comment_closure
- ancester(the parent)
- descendant(the child)
- depth

比如有这样的一个评论结构

1
2
3
4
5
6
1
| - 2
| - 3
| - 6
| - 5
| - 4

那么我们的cloure_table就会这么设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
INSERT INTO `comment_closure` (`ancestor`, `descendant`, `depth`) VALUES
(1, 1, 0),
(0, 1, 0),
(2, 2, 0),
(1, 2, 1),
(0, 2, 1),
(3, 3, 0),
(1, 3, 2),
(2, 3, 1),
(0, 3, 2),
(4, 4, 0),
(1, 4, 1),
(0, 4, 1),
(5, 5, 0),
(1, 5, 2),
(2, 5, 1),
(0, 5, 2),
(6, 6, 0),
(1, 6, 3),
(2, 6, 2),
(3, 6, 1),
(0, 6, 3);

取6这个节点说明,(6, 6, 0)就是这个节点本身,(1, 6, 3),(2, 6, 2),(3, 6, 1),(0, 6, 3)分别代表这个节点和0(root),1,2,3这四个节点的深度关系。
来做一次查询,我们查询2节点下的整个树:

1
2
3
4
SELECT `id`,`parent` FROM `comments` `comment`
JOIN `comments_closure` `closure`
ON `comment`.`id` = `closure`.`descendant`
WHERE `closure`.`ancestor` = 2

于是很愉快的返回了

1
2
3
4
5
id parent
2 1
3 2
5 2
6 3

rank这个字段是由他的Path生成的,类似于这样:0000000001-0000000002-0000000003,在上面提到的文章中,原作者将他的适用场景描述为:对comments进行排序操作。个人觉得不是这个方法的精髓,所以不放在文章里面了,有兴趣的童鞋请移步传送们

查询优化了很多,不过缺点也是显而易见的,查询删除这样的操作会涉及非常多的东西,需要单独写函数来做了= =
如果树结构很庞大,对查询、定位这样的效率需求高,又不是很追求改动的效率的话(改动次数少、只有管理员可以改动),这个方式比较适合


Nested Sets

记录左值和右值,比较独特的一种方式,查询非常高效

这个必须先上图了

Alt text

PS:好像也叫Modified Preorder Tree

按照深度优先,由左到右的原则遍历整个树,从1开始给每个节点标注上left值和right值,并将这两个值存入对应的name之中。
因为跳出了父子节点这样一个框架,所以看起来就比较复杂,不直观,不过复杂自然有复杂的道理,不然就称不上一个优秀的树形结构设计了。

CRUD
  1. 获取某节点的子孙节点
    SELECT * FROM Tree WHERE Lft BETWEEN 左值 AND 右值 ORDER BY Lft ASC
  2. 获取某节点的Path
    SELECT* FROM Tree WHERE Lft < 左值 AND Rgt > 右值 ORDER BY Lft ASC
  3. 添加一个节点
    需要两步,这里讨论的是,加入的节点是个末端节点,所谓末端节点,就是插入的这个节点,不是任何当前已存在的节点的父节点
    1. 首先,需要给这个节点腾出地方,比如我要在6、7中间插入一个元素,那么所有左值和右值大于6的节点,左值右值都得+2;
    2. 其次,把这个节点加进来,给他左右值附值7、8。
  4. 删除一个节点
    同样比较复杂,如果我们想要删除某个节点,会同时删除该节点的所有子孙节点,而这些被删除的节点的个数为:(被删除节点的右值 – 被删除节点的左值+ 1) / 2,而剩下的节点左、右值在大于被删除节点左、右值的情况下会进行调整。

优缺点非常明显:
查询高效,增删改非常难。。


总结

根据使用场景,选择适合的方案


相关文章和站点