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字段来维护。
结论：
每种设计各有优劣，如何选择设计依赖于应用程序中的哪种操作最需要性能上的优化。
邻接表：简单，但不适用于很深的表；
枚举路径：无法保证引用完整性；
嵌套集：无法保证引用完整性，太复杂；
闭包：需要一个额外的表存储关系；
个人推荐使用用邻接表，或者用邻接表+枚举路径。