非递归分类树

分类树这种结构存在于页面菜单、行政区划、部门层级、用户组等场景中，特点是有明确的上下级覆盖关系，本质数据结构是N叉树。

一、基础实现

分类树的基础实现是递归查询。在数据表中增加一个pid字段，储存当前记录的上级id。通过递归查询pid的方法将子节点集合从数据表中查出来放入children列表中，通过这种方式建成一棵树。

二、优化基础实现

递归查询建立分类树的方式有查询扩散问题，就是不知道递归深度有多少，数据库交互次数无法控制。针对这个问题，后来又出现了添加树深度字段deep、添加树路径字段path等方法，通过冗余字段来降低分类树的使用难度。

但是冗余字段造成一个问题——修改扩散。例如当分类树中的一条记录被修改，其深度发生变化时，那么它的子节点深度也会发生变化，它子节点的子节点深度亦发生变化，路径字段也是同理。一个修改导致多个修改，进而导致更多修改，其最终修改范围无法控制，可能遍布全表，这就是修改扩散。

三、非递归实现

递归查询会发生查询扩散、修改扩散。我意在构想一种算法，构建树的查询次数与树深度无关，修改扩散范围可控，不会无限波及。

递归的层数是无法预知的，所以我放弃用递归实现。

首先，我构造这样的一个表，除节点本身信息之外，其结构信息有主键id、子节点主键集合children、祖先节点主键集合ancestors。子节点主键集合children我采用Set避免重复。

在这里，我划分分类树为两类，一类是叶子只有唯一父节点的singleTree，一类是子节点允许多个父节点的crossTree。singleTree的祖先节点主键集合ancestors我采用List，以便记录其顺序，此时ancestors可以当作路径path用。crossTree的祖先节点主键集合ancestors我采用Set，因其多父节点有可能会有同一源头，采用Set去重。crossTree的优势在于，相同节点不必重复创建，可以复用节点，例如指向同一个页面的菜单项可以同时挂在不同的父菜单下，该菜单项地址修改时只需修改该项，不必像singleTree同名菜单项全部去改一遍。除此之外两类分类树使用是非常相似的。

children、ancestors两个字段，在数据库中用表示数组的字符串存储，其格式形如：[]或["id1","id2"]。

现在，我详细解释如何解决上面提到的查询扩散、修改扩散问题。

1、查询扩散

查询之所以会扩散，是因为无法穿透查询隔代节点。

但是现在向下查询各节点都有ancestors字段记录全部祖先，通过ancestors like '%"rootId"%'就可以一次性查到所有子孙节点的列表，不论子孙节点跟查询节点隔了几代。

向上查询的话，查询节点的ancestors字段本身就记载了所有关联的祖先，不会扩散到此范围之外。

2、修改扩散

将一个新节点node插入树中时，首先取得插入点的父节点parent。新节点的ancestors字段，就是parent.ancestors以及parent.id，这是singleTree的情况。如果是crossTree且node.ancestors原来就有内容，即还挂在别的父节点下，那除了parent.ancestors和parent.id之外，还要再加上node.ancestors原有内容，其是Set会自动去重。接着在parent.children集合中添加node自身id。

接着，根据node.children取得所有直接子节点，以及直接子节点的所有子孙节点。这次查询的结果列表就是所有ancestors字段需要修改的范围。在所有子孙节点的祖先主键集合ancestors中，添加node.ancestors以及node.id。

修改、删除节点也是同理。

综上，修改一个节点，所要关联修改的所有其他记录为其父节点、满足ancestors like '%"nodeId"%'的节点，不会扩散到此范围之外。

四、优化非递归实现

以上实现因为使用了like条件，在表规模较小时尚无问题，规模大了就有可能出现查询性能问题，因为like条件中的id不确定位于字符串何处，无法使用索引。

既然如此，当表规模膨胀了，可以将children字段和ancestors字段改为两个新表记录这两种关联关系，对childrenId和ancestorsId建立索引。这种改造对非树形表也同样可行，不需要修改原表结构。