在日常开发中，我们经常需要存储树形结构的数据记录，类似菜单，文件系统等。日常开发中的用到的数据库注入mysql，oracle等都是关系型数据库，擅长表示一对多关系，所以如何合理的存储这些树形结构数据就是一个必须要考虑的问题
例如下面表示水果分类关系的树形结构图，下面的示例并不具有普适性。像文件系统这种可以无限分层的情况需要特别考虑。
水果分类图
以下是经常会用到的几种方案：
①邻接表：也即添加父子关系，通过将每条记录添加一个parent_id字段完成父节点与子节点的映射，如下图：
邻接表结构
优点：
这种表结构设计简单，不需要多余的字段就可以表示父子关系，方便查询某一个分类下的所有子节点。新增比较方便。
缺点：
但是这种方式缺点也比较明显，就是需要递归查询才能查询出某个目录下的所有子节点。同理删除也需要递归，移动文件夹也比较麻烦。
②嵌套子集：嵌套子集的方式即通过构建从父节点到各节点的关系表来方便查询某个节点下的所有子节点。如图通过select food_id from table where parent_id = 2可以很方便的查询2节点以下的所有子节点
嵌套子集
优点：方便查询某一节点下的所有子节点，同理删除节点下的所有子节点也同样方便。
缺点：但是需要额外的空间（Cn2：C(n,2)）存储关系表。而且随着层级的增加，所需要的空间也会增加。同时节点的新增，删除，修改都需要增加维护关系表的成本。
③左右值编码：左右值编码的方式是一种对于通过在节点左右编号的设计方案。如下图：
左右值编码
节点两侧编码如何确定：首先可以先将根节点的左侧设为1，然后树的前序遍历算法，每走一步将编号加1。
怎样进行增删改查？
先假定父节点的左右节点为p_left,p_right；
查询：查询某个节点下的所有子节点时，可以先查询出某个节点的左右节点(p_left,p_right)，然后通过select * from table where left between p_left and p_right得到所有的子节点。
新增：新增一个节点时，需要节点左侧的编号不需要改动，但是节点的右侧的编号重新设置，使用以下语句实现// 首先查询出需要插入的父节点信息 select * from table where parent_id = XX //将节点右侧的节点左右编号都加2 update table set `right` = `right` + 2 where `right` >= right1; update table set `left` = `left` + 2 where `left` >= right1; // 将新节点插入到固定的位置，left=父节点的节点 insert into tree_table(`parent_id`, `name`, `left`, `right`) values(id, name, self_right, right1 + 1);删除：删除逻辑与查询逻辑基本类似。删除某个节点的所有子节点时，可以先查询出某个节点的左右节点(self_left,self_right)，然后通过执行
delete from table where left > self_left and left < self_right得到结果，此时该节点以及子节点的序号都会删除，存在序号断层的问题，你可以通过。
更新：更新节点涉及到流程比较复杂，包括以下几步：// 记录一下需要移动的节点id以及所有的子节点id select id from tree_table where `left` >= self_left and `right` <= self_right; // 将需要移动节点后面的节点往前移, 填充空缺位置 update tree_table set `left` = `left` - (self_right-self_left+1) where `left` > self_right; update tree_table set `right` = `right` - (self_right-self_left+1) where `right` > self_right; // 记录一下目录文件夹的左右节点值，之后有用 select p_left,p_right from tree_table `parent_id` = parent_id // 将目标父节点之后的节点加上该节点之间的差值，表示 update tree_table set `right` = `right` + (self_right-self_left+1) where `right` >= p_right; update tree_table set `left` = `left` + (self_right-self_left+1) where `left` >= p_right; // 将该节点以及子节点插入到目标文件夹下 update tree_table set `right`=`right` - self_left + p_right, `left`=`left` - self_left + p_right where id in ids(第一步查询到的id集合);
优点：
这种不用递归就可以很快的查出一个节点下面所有的子节点，这对于某些需要频繁查询子文件集合的系统来说是一个很好的解决方案，而且这种方案不会对树结构层数有所限制。
缺点：
这种方式的缺点也很明显，就是新增和移动的时候需要涉及到其他节点，如果树结构本身的节点比较多，那么最坏的情况下可能会出现效率问题。
④全路径：全路径是通过新增字段，存储根节点到该节点父节点的路径。下图是通过向每一层设计一组编号的方式来完成，当然也可以直接存储根节点到父节点的id值。相比于存储自定义code，存储id值的好处每层的节点个数不受编码个数的限制。
note:如果路径存储code，需要考虑每层的节点数。以及每层不断新增，删除节点而导致code用光的问题。而且code的增长可能还涉及到多线程同时新增的问题。
全路径
优点：
这种方式相比于左右值来说实现比较简单，而且同样不需要递归就可以查询到某个节点下的子节点集合，而且新增，删除，查询，移动都比较简单。
缺点：
这种方式查询需要在path字段上建立索引，但是随着层数的增加，path字段的长度将超过索引的最佳范围，此时可能
网友评论