关系数据库中存储操作树形结构

关系数据库中树形结构的存储,决定因素是对于设计的系统,在此树形结构上的操作是什么。尤其对于节点数较大的树形关系,操作性能肯定是第一考虑因素。当然也和树的具体特典有关系,比如是“扁平型”的还是“纵深型”的。最近的工作涉及到一棵近百万个节点的树,一点总结稍作笔记。

树形结构常见操作

下面的操作大部分从MySQL文档中摘录。

  1. 遍历
  2. Finding all Child nodes
  3. Find the Immediate Subordinates of a Node
  4. Finding all the Leaf Nodes
  5. Depth of a Sub-Tree
  6. Aggregate Functions in a Nested Set
  7. Retrieving a Single Path (all ancestors nodes)
  8. Finding the Depth of the Nodes. 相当于7,找到所有父节点。
  9. Adding New Nodes
  10. Deleting Nodes

可简单分类为

  • 向下搜索(1,2,3,4,5,6)
  • 向上搜索(7,8)
  • 修改(9,10)

其中3和2,4等在不同数据结构基础上的实现中,非常不同。以下分别对几种常见的表示方法,作个简单总结。

线性表示

         A
       / | \
      B  C  D
        /|   \
       E  F   G

A(B, C(E, F), D(G,),)

相当于宽度优先的遍历。
“线性表示”的意思是说,在一行文本中,表示整个复杂结构。也许可以用在数据压缩上吧,基本上与这里讲述的关系数据库关系不大。

node-id & parent-node-id

最常见的表示方法,represents a hierarchy is by using parent child relationship
在关系数据库中,一行数据表示树中的一个节点(后面叙述的结构均是如此)。这一行中存储当前节点的ID(NodeId)和它的父节点的ID(ParentNodeId),因为每个节点的父节点是唯一的。在这两个ID上做索引。

此种结构最利于临近层次的节点搜索(常见操作之3)。对于节点的增删修改(常见操作之9,10),也很容易,只要修改单个节点的属性即可。

操作3(Find the Immediate Subordinates of a Node)在展示树型数据时很有用。比如动态展开节点。实际上很多树形控件,其数据结构也正是这样的。比如YUI的TreeView ;MSComctlLib.TreeCtrl;Graphviz;ASP.NET中的Tree view等等。

对于操作2,4,7,8,在SQL Server中可以使用Inline Table-valued FunctionsMultistatement Table-valued Functions 递归调用实现。当然性能上会有损失。

Deep-first Tree

Depth-First Traversal

A B C D E F G
node-id 1 2 3 4 5 6 7
most-right-child-id 7 2 5 4 5 7 7

Deep-first结构中,每条Node记录需要包含node-id和most-right-child-id。

常见操作2,4,7,8可以高效实现。但是对于操作3(immediately children),实现起来比较难,不如parent/child的容易、高效。可以结合使用。

–Get the path from the root to the given node:
SELECT t1.*
FROM employee t1, employee t2
WHERE t1.nodeindex <= i
AND t1.rightchildindex >= t2.rightchildindex
AND t2.nodeindex = i;

增删修改操作性能消耗比较大。

— Insert a node as a child of i: UPDATE employee
SET employee.nodeindex = employee.nodeindex + 1
WHERE employee.nodeindex > parentnode;

UPDATE employee
SET employee.rightchildindex = employee.rightchildindex + 1
WHERE employee.rightchildindex >= parentnode;

No comments yet. Be the first.

Leave a reply

Random posts

  • Questions from Xiaoying
  • 遭遇ARP欺骗病毒
  • Charlie's Angel
  • 四色立方体问题
  • 结构式图片生成服务, DayLight SMI2GIF