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

2014-10-11

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

最上层的节点叫做根（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字段来维护。

结论：

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

邻接表：简单，但不适用于很深的表；

　　 枚举路径：无法保证引用完整性；

　　 嵌套集：无法保证引用完整性，太复杂；

　　 闭包：需要一个额外的表存储关系；