在SQL数据库中高效组织层次数据

《在SQL数据库中高效组织层次数据》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、在SQL数据库中高效组织层次数据“嵌套集合”数据结构与算法昆明维智众源企业管理咨询有限公司李维一个层次数据的例子ABEFCDGHI改成容器形式ABFECDGHI水平对齐，并给节点加上两个序号AFB123C45D678E91011G1213H1415I161718恭喜！我们刚刚实现了一个“嵌套集合”！节点的两个序号是关键●容器形式我们怎么编号：●把容器压扁，让所有节点在一条横线上。就是从二维的树转换为一维的数轴●从外层节点的最左侧开始，从左到右编号●树形式我们怎么编号：●从左到右，一次一层，为节点赋右值前先从

2、左到右遍历其子节点给其子节点赋左右值。●这种方法被称作改进的先序遍历算法“嵌套集合”的查询●检索所有叶子节点：●叶子节点的特性是Right=Left+1：select*fromNodeswhereRight=Left+1●递归地检索节点n的节点下所有子节点：●子节点的Left总是位于祖先节点之间：select*fromNodeswhereLeft>n.LeftandLeft

3、连接或非标准SQL扩展就可实现：●查询节点深度●查询子树深度●检索节点下的第一级子节点●....在表中构造与修改NESTED-SETS●表该怎么设计？●任意表添加Left与Right两个整型列后就变成了层次表，推荐加上自关联列ParentID以便访问上级节点。●层次结构的更改操作：●插入节点●删除节点●移动节点插入节点●算法简述：●在任何一处插入n个节点，其右边的所有节点的Left与Right值都必须加n.●第一步：找出插入位置的前一个节点的Left与Right值，如果是空表，则都为0。●第二步：更新插入位置以后所有节点的Left为Left+n，

4、Right为Right+n●第三步：实际插入数据，被插入节点的Left为前一节点的Right+1。插入节点的MySQL例子SELECT@myRight:=RightFROMNodesWHEREName='TELEVISIONS';UPDATENodesSETRight=Right+2WHERERight>@myRight;UPDATENodesSETLeft=Left+2WHERELeft>@myRight;INSERTINTONodes(name,Left,Right)VALUES('NewNode',@myRight+1,@myRight+2

5、);删除节点●删除节点是插入节点的逆操作：●删除节点之后需要将被删除节点右侧的所有节点的Left与Right值都减少被删除节点的宽度。●宽度：节点Right-Left删除节点的MySQL例子SELECT@myLeft:=Left,@myRight:=Right,@myWidth:=Right–Left+1FROMNodesWHEREname='NewNode';DELETEFROMNodesWHERELeftBETWEEN@myLeftAND@myRight;UPDATENodesSETRight=Right-@myWidthWHERERight

6、>@myRight;UPDATENodesSETLeft=Left-@myWidthWHERELeft>@myRight;思考题序号不一定要连续，只需要在数轴上的位置合适即可，如此可以大大提高插入、删除、移动操作的性能。NESTED-SETS的应用●Nested-Sets已被众多的商业和开源产品采用●一如SQL数据库的设计，Nested-Sets查询效率非常高，但是插入与删除节点效率较低（因为存在节点移动），可用于任何层次数据：●会计科目表●产品分类●物料表●....参考资料●《MySQL中分层数据的管理》：http://url.cn/1Ow4I

7、l●“Googleisyourbestfriend.”Q/A感谢！