树是我们日常开发中经常会用到的一种数据类型，常用的应用场景有：无限级分类、任务列表等层次数据。为了便于理解，我们首先假设需要存储如下图所示的树结构：
对这样一颗树常用的树操作有：
- 树节点查询：
- 查询某节点下的所有子节点（子树）
- 查询某节点的所有父级（路径查询）
- 添加节点
- 移动节点
下面介绍两种我个人常用的树存储模型以及对树常用操作的实现。
- 邻接表模型
我们在使用关联数据库存储树结构的时候，通常使用的方法是一条数据存储一个节点，在节点中添加一个parentId字段存储当前节点的父节点ID来实现树的存储，这种方法我们称为邻接表模型。使用Mysql存储这颗树的数据表结构可能类似以下结构：
| ID | name | parentId |
|---|---|---|
| 1 | root | 0 |
| 2 | A | 1 |
| 3 | B | 1 |
| 4 | C | 1 |
| 5 | A1 | 2 |
| 6 | A2 | 2 |
| 7 | C1 | 4 |
| 8 | C2 | 4 |
| 9 | A2.1 | 6 |
下面，我们通过树的常用操作分析下这种存储模型的性能。
2.1 查询某节点下的所有子节点（子树查询）
假设我们现在需要查询节点A的子树，根据图1所示我们知道节点A的直接子节点有A1、A2，而A2又有子节点A2.1。而在邻接表模型中我们是通过parentId来管理树的层次接口，那么我们要获取A节点的子树就需要：
- 根据A节点的ID 2获取到A节点的直接子节点A1、A2。
- 遍历A节点的直接子节点获取所有孙级节点。
- 遍历A节点的所有孙级节点获取更下层节点，以次类推直到获取到整颗子树。
通过这个查询流程我们发现要获取A节点的子树实际上需要进行很多次查询性能是非常低的。当然，我们可以优化扩展邻接表模型以优化这类查询的性能。比如增加一个parentIds字段存储一个节点的所有父节点路径，例如A2.1的parentIds为”,0,2,6,”这时候我们可以通过如下SQL查询到A节点的子树：select * from true where parentIds like "%,2,%"。但是这种方法依然存在缺陷，首先，like查询的性能在大表下会有一定的影响，其次是在插入新节点时需要预先获取其所有父节点ID再写入parentIds字段中。
2.2 查询某节点的所有父级节点（路径查询）
假设我们现在需要查询节点A2.1的路径，根据图1所示我们知道A2.1的路径是A2.1 > A2 > A > root。类似2.1的查询方法我们需要：
- 通过A2.1的parentId查询到A2.1的直接父级A2
- 通过A2的parentId查询到A2.1的爷级节点A
- 通过A的parentId查询到A2.1的祖级节点root
同样，要实现这样的查询性能也是非常低的。当然，我们也可以像2.1那样优化在节点中添加一个childrenId字段存储节点的所有子节点ID来进行查询优化，但是很显然的问题如果这是一个颗很大的树，那么root节点的children字段将会非常大！噢No！
2.3 添加新节点
假设现在需要为A2.1添加一个子A2.1.1，很简单只需要插入一条数据将parentId设置为9就可以了。
2.4 移动节点
移动节点也非常简单快速，假设我们需要将A2.1节点移动到节点C下只需要更新A2.1节点的parentId字段为4就可以了。
- 先根遍历树模型
先根遍历树模型是另一种常用的树存储模型，实现方法是从根节点左侧开始分别为每个节点进行编号直到树的最底层，再从最底成节点右侧反向编号直到回到根节点。如下图所示：
这样每个节点都获得了一个左值和右值，使用Mysql存储的表结构类似下表：
| ID | name | leftValue | rightValue |
|---|---|---|---|
| 1 | root | 1 | 18 |
| 2 | A | 2 | 9 |
| 3 | B | 10 | 11 |
| 4 | C | 12 | 17 |
| 5 | A1 | 3 | 4 |
| 6 | A2 | 5 | 8 |
| 7 | C1 | 13 | 14 |
| 8 | C2 | 15 | 16 |
| 9 | A2.1 | 6 | 7 |
同样，基于先根遍历树模型我们看下如何进行树的常用操作。
3.1 查询某节点下的所有子节点（子树查询）
同样假设需要查询节点A的子树，通过观察图2中节点的左右值可以发现A节点的所有子节点左值肯定都大于A节点的左值，而右值肯定都小于A节点的右值！根据这条规则我们使用一条SQL就可以查询到A节点的子树，SQL如下：
select * from tree
where leftValue > a.leftValue
and rightValue < a.rightValue
order by leftValue asc;
可见使用这种存储模型查询子树的性能远远高于邻接表模型。
3.2 查询某节点的所有父级节点（路径查询）
同样假设需要查询节点A2.1的路径，通过观察图2中节点A2.1的所有父节点左右值可以发现，A2.1的所有父节点左值肯定都小于A2.1的左值，而右值肯定都大于节点A2.1的右值！根据这条规则我们同样可以使用一条SQL查询到A2.1的所有父节点，SQL如下：
select * from tree
where leftValue < a21.leftValue
and rightValue > a21.rightValue
order by leftValue acs;
可见使用这种存储模型查询节点路径的性能也是远远高于邻接表模型。
3.3 添加新节点
通过前面两种查询操作可以看到先根遍历树模型在查询数据方面性能非常卓越。可惜人无完人，方法也是！这种模型在进行数据插入方面可就不能直接一条SQL搞定了。
还是以向A2.1添加一个A2.1.1节点为例。因为这种模型下树初始化后节点的左右值是连续的，所以如果想要添加一个节点就必须先给新节点腾出一个空位来。根据左右值的编码规则我们可以推算出新节点A2.1.1的左值应该是7、右值应该是8。如果要腾出这样一个位置的话，就必须将A2.1、A2、A、Root节点的右值加2，将B、C、C1、C2的左值和右值都加2。SQL如下：
update tree
set rightValue = rightValue+2
where leftValue <= a21.leftValue
and rightValue >= a21.rightValue;
update true
set leftValue = leftValue + 2，rightValue = rightValue + 2
where leftValue > a21.rightValue;
这种就为新节点A2.1.1空出了一个位置，接下来再使用insert语句将A2.1.1插入即可。由于需要更新A2.1所以右值节点和父节点的所以大一颗比较大的数下插入一个新节点性能消耗还是比较大的。
3.4 移动节点
使用先根遍历数模型移动节点位置和插入新节点的方法基本相同，也是需要先在新位置为节点空出一个位置，然后再将节点的左右值修改为新位置的左右值。
总结
两种树的存储模型以及它们分别实现树的常用操作方法就介绍完成了，可以发现这两种模型各有优缺点。
邻接表模型插入新节点、移动节点位置性能非常好，但是要进行复杂的树查询性能就很糟糕了。
先根遍历树模型在查询方面性能突出，但是在插入新节点和移动节点时虽然SQL也只有两三条但是在一个大表下考虑到数据量以及索引重建性能还是会有问题。
所以，世界上没有最好的语言更没有最好的方法！只有根据自己的业务特点选择最合适存储模型才是最佳实践，如果对树的操作更多是查询应该使用先根遍历树模型；如果对树的写操作比较多则应该使用邻接表模型。当然也可以将两种模型同时使用，插入的时候使用邻接表模型然后在后台重建左右值结构，查询的时候使用先根遍历树模型。结合现代的新技术还可以分析树的规模，如果树的规模肯定不会很大则还可以使用redis存储JSON对象的方式来进行存储。总之一句话：首先分析业务场景，再根据业务场景选择最合适的方法！
