Charlie’s path to dEAth

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

树形结构常见操作

下面的操作大部分从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 Functions 或 Multistatement Table-valued Functions 递归调用实现。当然性能上会有损失。

Deep-first Tree

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;

Filed by charlie at 6:04 pm under DBA, Engineer