Charlie’s path to dEAth

August 29, 2007

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

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

树形结构常见操作

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

遍历
Finding all Child nodes / 取得所有的下级节点
Find the Immediate Subordinates of a Node
Finding all the Leaf Nodes / 取得所有下级叶子节点
Depth of a Sub-Tree / 取得子树的深度
Aggregate Functions in a Nested Set
Retrieving a Single Path (all ancestors nodes) / 取得当前节点到根节点的路径
Finding the Depth of the Nodes. 相当于7，找到所有父节点。
Adding New Nodes
Deleting Nodes

可简单分类为

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

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

线性表示

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 Functions 或 Multistatement 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;

INSERT INTO employee
(nodeindex, rightchildindex, NAME, comments)
VALUES (parentnode + 1, parentnode + 1, nodename, nodecomments);

-- Delete the node with NodeIndex i: DELETE employee
WHERE employee.nodeindex = i;

UPDATE employee
SET employee.nodeindex = employee.nodeindex - 1
WHERE employee.nodeindex > i;

UPDATE employee
SET employee.rightchildindex = employee.rightchildindex - 1
WHERE employee.rightchildindex > i;

Nested set, 节点左右边缘

左边缘作为node-id，同时记录right-extent。与Deep-first Tree等价。

-- All Leaf nodes (an item with any children) can be
-- identified by Left = Right - 1
SELECT * FROM Employee WHERE [LeftExtent] = [RightExtent] - 1

Build a deep-first tree from parent child relationship

Python code

#{
def process_node( catid ):
    n = retrieve_node( catid )
    dfid = global_increased_id()                # with a increased id
    most_right_child_dfid = dfid
    for child in retrieve_children( n ):
        most_right_child_dfid = process_node( child )
    upd_to_db( catid, dfid, most_right_child_dfid )
    print dfid
    return most_right_child_dfid

The WITH keyword in SQL Server 2005/2008

在SQL Server 2005及以上的版本的中，加入了WITH这个关键字。WITH关键字定义了匿名函数，通过表达式形成表定义common table expression (CTE)，而且可以递归。而 node-id & parent-node-id 模型中的“取得当前节点到根节点的路径”操作，就需要对表值函数进行递归调用。用WITH关键字进行递归操作的例子如下

with HierarchyCTE (NID, PID, Lvl) as
 (select NodeID, ParentID, 0
 from dbo.Hierarchy
 where NodeID = @NodeID_in
 union all
 select NodeID, ParentID, Lvl + 1
 from dbo.Hierarchy
 inner join HierarchyCTE
 on PID = NodeID)
select *
from HierarchyCTE