SQL反模式学习笔记3 单纯的树

2014-10-11 08:59:48

        在树形结构中,实例被称为节点。每个节点都有多个子节点与一个父节点。

        最上层的节点叫做根(root)节点,它没有父节点。

        最底层的没有子节点的节点叫做叶(leaf)

        中间的节点简单地称为非叶节点(nonleaf)

目标:分成存储于查询,比如:系统字典、组织机构、省份区域等树形结构数据或者以层级方式组织的数据。

 

反模式:总是依赖父节点,邻接表。

           最简单的实现方式是添加ParentId字段,引用同一张表的主键ID。

           邻接表维护树比较方便,但是查询很笨拙,如果要找一个节点下的所有子节点,要关联很多次,这个关联次数取决于树的深度,

           所以,邻接表不能用于存储比较深的树。

 

如何识别反模式:当出现以下情况时,可能是反模式

        (1)我们的数结构要支持多少层

        (2)我们总是很害怕接触那些管理树结构的代码

   (3)我需要一个脚本来定期的清理树中的孤立节点数据

 

合理使用反模式:

  邻接表设计的优势在与能快速地获取一个给定节点的直接父子节点,也很容易插入新节点、维护节点、删除节点。

      如果树的分层结构不是很深,可以使用这种模式。

       【 使用CTE通用表表达式来递归查询树形结构数据比较方便,详见“SQL中的CTE通用表表达式 】

 

解决方案:使用其他树模型

  路径枚举:

    用一个path字段保存当前节点的最顶层的祖先到自己的序列(路径)

    优点:查询方便;

    缺点:1、不能保证存储的值的有效性。

                   2、增、删时,要考虑对原位置下的子节点如何处理,比较麻烦。

                   3、如果还要维护一个排序path,那就更麻烦了。

  嵌套集:

    存储子孙节点的相关信息,而不是节点的直接祖先。用nsleft存储所有后台的nsleft中最小的数-1,

          用nsright存储所有后台的nsright中最大的数+1。

    优点:删除时,原来子节点的关系自动上移。

    缺点:1、查询一个节点的直接上级或下级,很困难。

                   2、增、删,困难。

  闭包:记录了树中所有节点间的关系,而不仅仅是只有那些直接的父子关系。

             将树中任何具有“祖先-后代”关系的节点对都存储在TreePath表中的一行,同时增加一行指向节点自己。

            优点:1、能快速的查询给定节点的祖先与后代;

                    2、能更加简单的维护分层信息;

                    3、如果删除了TreePath表中的一条记录,那么并不是真正的删除具体信息表中的记录。这样设计有时候很有用:

                        比如在产品目录的分类或者员工组织架构的图标中,当你改变了节点关系的时候,并不是真的想要删除一个节点。

                        我们把关系路径存储在一个分开独立的表中,使得设计更加灵活。 

            缺点:查询直接父节点或子节点,需要在表中增加Path_Length字段来维护。

 

结论:

        每种设计各有优劣,如何选择设计依赖于应用程序中的哪种操作最需要性能上的优化。

 

        邻接表:简单,但不适用于很深的表;

 

    枚举路径:无法保证引用完整性;

 

    嵌套集:无法保证引用完整性,太复杂;

 

    闭包:需要一个额外的表存储关系;

 

        个人推荐使用用邻接表,或者用邻接表+枚举路径。

SQL反模式学习笔记3 单纯的树

上一篇:MySQL CAST与CONVERT 函数的用法


下一篇:Java中static、final用法小结