在一些系统中，对内容进行分类是必须的功能。例如，电子商务公司需要对产品进行分类，以方便客户搜索；论坛也分为许多部分；门户网站也必须对网站内容进行分类。分类对于一个内容展示系统是必不可少的，本博客也需要这样的功能。众所周知，分类往往有隶属关系。比如铅笔盒笔就属于钢笔，钢笔是文具的一种。当然，钢笔也可以按品牌细分。每个品牌下都有各种系列...在这个例子中，affiliation有5层，从上到下：文具-钢笔-钢笔-XX品牌-A系列，但实际分类层数是无法估计的。显然，限制分类级别的数量是不合理的。一个好的分类系统应该能够做到最高级别的分类。我在写自己的博客站点的时候，正好需要这样一个功能。听起来很简单，但是当我实现的时候，我发现用关系型数据库来存储顶级分类并不容易。1.需求分析首先，分析类之间的关系。很明显，一个品类下还有很多子品类，比如钢笔下有铅笔、钢笔；那么反过来，一个子类又可以属于多少个子类呢？？这个其实也不一定，要看类型怎么划分。比如有办公用品和家具，那么书桌可以同时属于两者，但是这样会带来一些问题，比如：我想显示从***类别到它的所有类别，那么在这个case很容易办公用品和家具很难决定展示哪一个，如果是多对一的，实现起来会比较复杂，所以这里我们还是限制每个类目只能有一个父类目。现在，分类关系可以表示为一父多子的继承关系，正好对应数据结构中的树，那么问题转化为如何在数据库中存储一棵树，更好理解分类支持所需的操作。对于本博客，分类至少需要进行以下操作：单个分类的增删改查等基本操作查询一个分类的直属下属和所有下属，使用query通过**查找分类*当某个分类下的所有文章都是真实的到文章分类之间的所有分类，并且是有序的。用于在博客首页文章介绍的左下角显示查询类别的级别。比如***类是1，直接属于***类的下一级是2，然后一个类递增向下移动。换句话说，一个子树（或只有一个节点）被移动到另一个节点。这在分类结构上是不合理的。当需要修改时，使用某个级别的查询所有分类在性能方面都不是平等的。查询操作的使用频率更高。毕竟分类不会为了好玩而改变。性能方面的考虑应该优先考虑查询操作。特别是2和3用于搜索文章，在文章介绍中显示其分类，所以是最重要的。另外，每个类别除了继承关系外，还有名称、介绍等属性，也需要存入数据库。每个类别都有一个id，由数据库自动生成（自增主键）。state-of-the-artmulti-classification多存在于企业应用中，如电商、博客平台等，这些应用一般都有缓存机制。对于不经常修改的数据，比如分类，即使底层数据库有较慢的操作，只要能够激活上层缓存，也会有很快的响应速度。但是对于抽象的需求：在关系型数据库中存储一棵树并不仅仅存在于缓存应用中，因此设计一个高效的存储方案还是很有意义的。下面以卖文具的电商场景为例，针对这6个需求设计一个数据库存储方案（如果对流程不感兴趣，可以直接看第4节）。2、一些常见设计方案的不足2.1直接记录父类的引用在很多编程语言中，继承关系是一个类只继承一个父类。添加这种继承关系只需要声明父类即可，比如JAVA中extendsxxx。按照这个思路，我们只需要在每个类中加上直属上级的id，就可以存储它们之间的继承关系。表中的parent是其直属类别的id，***类别设置为0。这种方案简单易懂。只有一张表，没有冗余字段，存储空间很小。在数据库层面是一个很好的设计。然后再看对运营的支持。第一个单增改查询就一句话，就不多说了。如果删除了，记得把下级分类的id全部改成删除分类的上级分类，还有一个更新。第二个可能很麻烦。比如我要查文具的低级分类，期望结果是三支钢笔，铅笔，钢笔。但是，铅笔、钢笔、钢笔是没有办法一下子通过文具找到的，因为这两者之间的关系是间接的。存储在笔类中，需要先找出直属（笔）才能往下查询，也就是说需要递归，一下子性能会差很多。第三项同样需要递归，因为通过一个类目，数据库中只存储了它的直接父类目，它们之间的所有类目信息都需要通过递归到***类目来获取。综上所述，最关键的两个需求要求使用性能最差的递归方法，这种设计是肯定不行的。但是继续看剩下的。第四个需求：查询分类的级别是多少？这还是需要递归或者循环，找到所有上级类别的个数就是该类别的层级。移动端分类很简单，直接更新parentid就可以了，这是这个方案唯一的优势。。。如果你的分类修改多于查询，不妨这样做。***对某个级别的所有类别的查询对于这种设计来说是一场灾难。它需要先找到所有的一级类别，然后循环遍历，找出所有一级类别的子类别都是二级类别……如此循环，直到达到需要的阶段数。所以在这个设计中，这个功能基本没用。这个方法一开始也可以想到。在数据量不大（层次不深）的时候，简单直观的特点是不错的选择，但是对于本项目来说还不够（本项目立志成为***博客平台！!!).2.2路径列表从2.1节可以看出，__慢的原因是分类中只存储直属上级关系，但需求是查询非直属上级。__针对这一点，我们的表不仅记录了父节点id，还保存了它与***类别之间的所有类别的id。该字段存储的信息就像文件树中的路径，所以称为路径。如图，每个分类保存了一个其所有上级分类的列表，用逗号隔开，从左到右分别是***分类到父分类的id。使用Like运算符搜索下属，例如查找笔的所有下属：SELECTid,nameFROMpathlistWHEREpathLIKE'1,%'一句话就可以完成，LIKE右边是笔的路径字段的值加上模糊匹配，并且可以使用leftjoin索引的效率也还过得去。查询笔的直属也可以用LIKE:SELECTid,nameFROMpathlistWHEREpathLIKE'%2'求出所有上级分类的需求，直接找出path字段，然后在应用层划分，得到所有的上级，秩序也有保障。查询某一层级的分类也很容易，因为层级越深，路径越长，使用LENGTH()函数作为条件可以筛选出合适的结果。反之，也可以根据其长度计算分类级别。move操作需要递归，因为每个分类的路径都是其父类的路径加上父类的id，将分类及其所有子分类的路径设置为父类的路径并追加父类***id中的类的id就足够了。该方案在很多系统中都有使用，各方面表现尚可，也比较容易理解。但是它有两个缺点：1.不遵循数据库范式，直接将列表数据存储为字符串，会导致一些操作在上层解析path字段的值；2、字段长度有限，不能真正达到level1深度，大字段不利于索引。如果不关心范式，分类级别远没有字段长度的限制，那么这个方案是可行的。2.3前序树遍历这是一种将树存储在数据库中的解决方案。它的思路不是直接存储父节点的id，而是按照前序遍历的顺序来判断分类的直接关系。假设从根节点开始，依次遍历树中的节点。第一个节点（“Food”）最先被访问，将它的左边置为1，然后按顺序到达第二阶段“Fruit”，在它的左边写上2，数每访问一个节点就会增加，访问完叶子节点后??返回，返回过程中将数字写在被访问节点的右边。这样遍历的时候，每个节点的左右都写上了数字。***，我们回到根节点“Food”，在右边写上18。下面是用数字标出的树，遍历的顺序用箭头标出。我们称这些数字为左值和右值（比如“肉”的左值是12，右值是17），这些数字包含了节点之间的关系。由于“Red”的值为3和6，因此它是值为1-18的“Food”节点的后继节点。同理可以推断，凡是左值大于2、右值小于11的节点，都是2-11的“水果”节点的后继节点。这样树的结构就是通过左值和右值来存储的。表的结构这里就不贴了。这种方法不像前两种那样直观。在效率上，查询所有下属的需求很好的解决了，直接下属也可以通过增加父节点id的parent字段来解决。因为左值较大，右值较小的节点为下级节点，反之，左值较小，右值较大的节点为上级节点，所以需求3：直接查询所有类别之间以左值和右值为条件，可以解决两个类别。同样是查询。添加新类别和删除类别需要修改前序遍历中指定节点之后的所有节点，包括非父子节点。移动分类也是如此。这个功能很不友好。在数据量很大的情况下，更改它是非常致命的。查询某个级别的所有类别，查询该类别属于哪个级别。这两个需求是解决不了的，只能通过parent字段按照第一种方式慢慢遍历。综上所述，对于这个项目来说，不如第二个，所以这个非常复杂的方案不得不否决。3.新方案的思考以上方案中最理想的是第二种方案。如果能解决字段长度、不符合范式、需要上层参与的问题就好了。不过别着急，让我们来看看第二种方案优缺点的本质。第二种方案分析开始时提到，为了保证效率，分类信息必须包含上级分类的所有信息，而不仅仅是直属上级，所以有一个用varchar保存列表的字段.但是反过来想想，数据库表本身不就是一种存储结构化数据集合的工具吗？为什么我们不能做一个关联表而不是路径字段呢？在path列表的设计中，key字段path的本质是存储两种信息：一种是所有父类的id，一种是***类到各个父类的距离。于是又增加了一张表，里面包含三个字段：一个是这个类的所有上级的id，一个是这个类的id，加上这个类到每个上级的距离。这样，这张表就可以起到和路径字段一样的作用，又不违背数据库范式。最重要的是它没有字段长度限制！经过一番折腾，终于找到了这个相对安全的方案。其实查阅资料后发现，这个方案早就在一些系统中使用了，叫做ClosureTable。4、基于ClosureTable的顶层分类存储ClosureTable直译为闭包表？不过不重要，ClosureTable把节点之间的关系存储在一个表中，表中包含任意两个相关（上层和下层）节点的关联信息定义关系表CategoryTree，它包含3个字段：ancestorancestor：上级节点的iddescendantdescendant：从属节点的iddistancedistance：后代与祖先的距离，这三个字段的组合是唯一的，因为在树中，一条路径可以标识一个节点，所以可以直接用他们的组合作为首要的关键。以图为例，节点6到其上层节点（节点4）的距离为1，在数据库中存储为ancestor=4，descendant=6，distance=1，到的距离上层节点（节点1）为2，所以有ancestor=1，descendant=6，distance=2，到根节点的距离为3，同理，***还包括一个连接到自身，当然距离为0。这样，无穷无尽的表就包含了所有的路径信息，还包含了路径中每个节点的位置（距离），对于树结构上的普通查询来说可以很方便的处理。让我们看看如何使用它来实现我们的需求。4.1子节点查询查询id为5的节点的直接子节点：SELECTdescendantFROMCategoryTreeWHEREancestor=5ANDdistance=1查询所有子节点：SELECTdescendantFROMCategoryTreeWHEREancestor=5ANDdistance>0查询某个上级节点的子节点，即查询具有指定上级节点，即祖先字段等于上级节点的id。第二个距离决定了查询对象距上层的层级。如果等于1，则表示下一级（直属子节点），如果大于0，则表示所有子节点。节点。两个查询都是一句话完成。4.2路径查询查询根节点到id为10的节点之间的所有节点，按照层级从小到大排序SELECTancestorFROMCategoryTreeWHEREDescendant=10ORDERBYdistanceDESC查询id为10的节点（含）和id为3的节点（不包括）SELECTancestorFROMCategoryTreeWHEREdescendant=10ANDdistance<(SELECTdistanceFROMCategoryTreeWHEREdescendant=10ANDancestor=3)ORDERBYdistanceDESC查询路径，只需要知道后代即可，因为后代字段所在行是记录本节点与其上级节点的关系。如果要过滤掉一些，可以限制distance的值。4.3查询节点的层级（深度）。查询哪个级别是id为5的节点。SELECTdistanceFROMCategoryTreeWHEREdescendant=5ANDancestor=0查询哪个级别是id为10的节点下方id为5的节点。SELECTdistanceFROMCategoryTreeWHEREDescendant=5ANDancestor=10depth）很容易，因为距离字段是。直接以上下级节点id为条件，查询距离。4.4查询某层所有节点查询第三层所有节点SELECTdescendantFROMCategoryTreeWHEREancestor=0ANDdistance=3这个就不细说了，很简单。4.5插入插入和移动不太方便。当一个节点被插入到某个父节点下时，它就会有一个类似于父节点的路径，然后添加一个自连接。所以插入操作需要两条语句，第一条复制父节点的所有记录，并在这些记录的距离上加一，因为子节点到每个父节点的距离都比它的父节点多一。当然后代也要改成自己的。比如在id为5的节点下插入id为10的节点（这里用mysql方言）INSERTINTOCategoryTree(ancestor,descendant,distance)(SELECTancestor,10,distance+1FROMCategoryTreeWHEREdescendant=5)然后添加自己连接的记录.INSERTINTOCategoryTree(ancestor,descendant,distance)VALUES(10,10,0)4.6移动节点的移动没有??很好的解决方案，因为新位置的深度和路径可能不同，导致移动操作不单靠UPDATE语句可以完成，这里选择delete+insert进行移动。另外，在子树的情况下，上层节点的移动也会引起下层节点路径的变化。因此，移动上层节点后，需要修复下层节点的记录，这就需要递归所有的下层节点。删除节点id=5DELETEFROMCategoryTreeWHEREdescendant=5的所有记录，然后配合上节插入操作实现移动。具体实现直接上代码。ClosureTableCategoryStore.java是主要逻辑，这里只展示部分代码/***将一个类别移动到目标类别（成为它的子类别）。被移动分类的子分类会自动上浮（成为指定分类*父分类的子分类），即使目标是指定分类的原始父分类。*
*例如下图（***类略）：*11*|/|\*2345*/|\move(2,7)/\*345--------------->67*/\//|\*6789102*//\*8910**@paramid移动类别的id*@paramtarget目标类别的id*@throwsIllegalArgumentException如果id代表的类别或目标不存在，或id==target*/publicvoidmove(intid,inttarget){if(id==target){thrownewIllegalArgumentException("不能在自己下方移动");}moveSubTree(id,categoryMapper.selectAncestor(id,1));moveNode(id,target);}/***移动目标类别下面的一个类别（成为它的子类别），被移动类别的子类别也会移动。*如果目标分类是被移动分类的子分类，则先将目标分类（带子分类）移动到被移动分类原来的*位置，再移动需要移动的分类。*
*例如下图（略***分类）：*11*||*27*/|\moveTree(2,7)/|\*345--------------->9102*/\/|\*67345*//\|*89106*|*8**@paramididofthemovedcategory*@paramtargettargetcategoryid*@throwsIllegalArgumentExceptionifidortargetindicates的category不存在，或者id==target*/publicvoidmoveTree(intid,inttarget){/*移动分支到自己的子树和不相关的节点*/Integerdistance=categoryMapper.selectDistance(id,target);if如果移动的目标是它的子类，需要先将子类移动到本类的位置moveSubTree(id,id);}/***将指定节点移动到另一个节点，该方法不修改子节点的相关记录，*为了保证数据的完整性，需要在结合moveSubTree()方法。**@paramid指定节点id*@paramparent一个节点id*/privatevoidmoveNode(intid,intparent){categoryMapper.deletePath(id);categoryMapper.insertPath(id,parent);categoryMapper.insertNode(id);}/***将指定节点的所有子树移动到某个节点*如果两个参数相同，相当于重建子树，用于父节点移动后更新路径**@paramid指定节点id*@paramparent某个节点id*/privatevoidmoveSubTree(intid,intparent){int[]subs=categoryMapper.selectSubId(id);for(intsub:subs){moveNode(sub,parent);moveSubTree(sub,sub);}}其中categoryMapper是Mybatis的Mapper，这里只展示了部分代码/***查询一个节点的第N级父节点。如果id指定的节点不存在，操作错误，或者数据库被外部修改，*可能查询不到父节点，此时返回null。**@paramid节点id*@paramn祖先距离（0表示自身，1表示直接父节点）*@return父节点id，不存在则返回null*/@Select("SELECTancestorFROMCategoryTreeWHEREdescendant=#{id}ANDdistance=#{n}")IntegerselectAncestor(@Param("id")intid,@Param("n")intn);/***复制父节点的路径结构，修改后代和距离**@paramid节点id*@paramparent父节点id*/@Insert("INSERTINTOCategoryTree(ancestor,descendant,distance)"+"(SELECTancestor,#{id},distance+1FROMCategoryTreeWHEREdescendant=#{parent})")voidinsertPath(@Param("id")intid,@Param("parent")intparent);/***在关系表中插入到自身的连接**@paramidnodeid*/@Insert("INSERTINTOCategoryTree(ancestor,descendant,distance)VALUES(#{id},#{id},0)")voidinsertNode(intid);/***从树中删除节点的路径。注意指定的节点可能有子树，而该节点上面的子树的节点的路径没有改变，*所以使用该方法后，必须手动修改子节点的路径，以保证树的正确性**@paramidnodeid*/@Delete("DELETEFROMCategoryTreeWHEREdescendant=#{id}")voiddeletePath(intid);5.结论经过分析推理，我最终找到了一种查询简单、效率高的方法，同时也符合数据库设计范式，是真正的军工级分类设计。该方案的写操作虽然需要递归，但相比前序遍历树的效率还是高了很多，而且本博客系统中的分类也不会频繁修改。可以看出，对于关系型数据库存储树的需求，ClosureTable是一个比较完善的解决方案。完整的JAVA实现代码见https://github.com/Kaciras/Examples-java/tree/master/ClosureTable