编码表示法表征树形结构及其在设备管理系统中的应用

褚衍国

（上海金自天正信息技术有限公司，上海201900）

0 引言

设备全生命周期管理系统，是助力企业设备管理维护团队执行标准化维护管理的最佳实践。设备系统的基础功能为设备主数据，其中功能位置、设备分类的数据结构均为树形结构。传统的表征方法一般是父子ID表征法，虽然理解简单，但其无法提供简单高效的检索查询。

本文阐述了一种编码表示法表征树形结构，以便为企业信息化中（例如设备管理系统中）的多种树形结构提供简单高效的检索。

1 术语和定义

树形结构：即数据元素之间存在着“一对多”的树形关系的数据结构，是一类重要的非线性数据结构。

根节点：即没有前驱节点（父节点），但是具有多个子节点，每个子节点也可具备多个子节点。

叶子节点：该节点没有后续节点，其余每个节点的后续节点数可以是多个。

树级别：根节点级别为0，其子节点级别为0+1，以此类推。

兄弟节点：同一个父节点的同一个树级别的子节点即为兄弟节点。

编码表示法：根据父节点和树级别以及兄弟节点顺序来实现编码表示某一节点的方法。不同级别的节点其有效编码位数不一样。

2 父子ID表征树结构分析

在该方法中，节点数据必须具备两个字段，即ID和parentID，分别表示本节点和其父节点。如果parentID为null，则表示本节点为根节点。

另外，对于父子ID表征树来说，如果需要获取节点1下面的所有节点，需要递归获取每一级的子节点。众所周知，递归算法的性能消耗极大，对于数据库来说，标准sql不具备这种能力。对于个别数据库例如oracle，虽然其提供了start with...connect by方法，但是这种方法性能消耗较大，且不通用。

3 编码表示法阐述

编码表示法需要4个字段来表征树形节点进而表征树结构，包括树编码、树级别、兄弟序号、是否叶子节点。

树编码：表示树节点，编码唯一，其内部编码结构下文详细阐述。

树级别：根节点树级别为1（也可以0为基准），每增加一级则级别加1，兄弟节点自然级别一致。

兄弟序号：同一个父节点下的兄弟节点之间的顺序号，以此来表征兄弟节点顺序。结合父节点的序号和分隔符可以实现带顺序的树形结构。可以0或者1为顺序基准。

是否叶子节点：如果本节点无子节点则为叶子节点，方便检索查询。

X位编码表示：一般根据实际业务情况，如果某节点下的子节点数目按照十进制来计算的话，某一级的节点数目的最大值达到5位数，则为5位编码表示法。一般来说，4位编码表示法即9999即可满足大多数需求。

以4位编码表示法为例分析如下：

后缀分隔符：此处以英文半角减号为后缀分隔符，方便累进计算树编码和后续的最小化插入和剪接操作。

4位编码表示法情况下，以1为顺序基准，则根节点自然为“0001-”。根节点下的子节点则以根节点的树编码为前缀加上其兄弟序号对应的4位字符串形式加上后缀分隔符，即生成第一级子节点编码形如“0001-0001-”“0001-0002-”。同理依次类推，各个节点下的子节点可为“0001-0002-0001-”，“0001-0002-0002-”。

可以看出，以分隔符分隔，每一级别的编码均为该级别下本节点或本节点的上级节点在其兄弟节点中的序号的4位字符串形式。按照树编码来排序，天然表征了带顺序的树结构。

4 编码表示法下的检索

定义树节点集合存储的关系数据库表名称为TreeTable，树节点字段分别为TreeCode，Treelevel，SNo，IsLeaf。$destreecode为某节点的树编码，$destreelevel为树级别。

（1）正向检索：即检索某节点及其所有子孙节点。Sql伪码如下：

select*fromTreeTablewhereTreeCodelike$destreecode+’%’order by TreeCode

可以看出这是标准sql语句，各大关系数据库均可支持，且语句简单，搭配数据库索引可以高性能地检索。

（2）逆向检索：即检索某节点及其所有父辈节点。Sql伪码如下：

select*from TreeTable where$destreecode like TreeCode+’%’order by TreeCode

此处依然使用了标准sql的like语句，但是是倒like。语句仍然极其简单。

（3）同级检索：即检索同一级别的节点。Sql伪码如下：

select * from TreeTable where Treelevel=$destreelevel order by TreeCode

（4）叶子节点检索：即检索所有叶子节点。Sql伪码如下：

select*from TreeTable where IsLeaf=True order by TreeCode

如果需要其他额外检索条件，可以自行根据需要改变以上sql。

由此看出，编码表示法的检索极其简单高效，对于实际业务应用中的报表统计来说，极大地简化了开发难度，提高了检索性能。

5 编码表示法的插入、变更、删除

虽然编码表示法提供了简单高效的检索，但是在遇到插入、变更情况时将影响很多节点，本节将对此进行阐述。

5.1 插入操作

5.1.1 尾部插入

这是最简单的一种情况，在某尾部节点后插入，只需要在原尾部节点基础上，将序号加1，并形成对应的树节点编码即可。

5.1.2 中间插入

某节点（非尾部和头部节点）后插入一个新节点C，则需要计算新序号CSNo，新序号的计算方法如下：

某中间节点A，其后节点为B，则A与B的序号之差为Diff。

根据Diff，分析得到对应的序号步进值StepV。Diff=1，则StepV=0.1；Diff小于1，且为n位小数，则StepV=0.{n位0}1；Diff大于1，则StepV=1。

新的树节点序号为CSNo={A的序号}+{StepV}，得到的值可能是小数，该序号值整数部分补足4位得到最终该级别字符串值（形如1234.2或0023），为CCurCode。C对应的树编码则为｛A的树编码｝移除最后一级编码+{CCurCode}。

这种算法的好处是可以在两个节点下无限扩充插入新节点，但是又不至于节点编码扩张太快。例如二分累加法也可以实现，但是多次插入后会极大增加树编码的长度。

5.1.3 头部插入

在头部节点A前插入新节点C，则计算A的序号与0的差值Diff，然后参考中间插入算法计算得到C的序号和C的树编码即可。

可以看出，插入操作的算法稍微复杂一些，但是影响的节点只有自身和父节点。

5.2 变更操作

变更操作，有点类似于树木的枝干剪接到另一个枝干节点，即将某节点A和其下的子孙节点改变到另一个节点下。此时可以对A节点计算得到新的树编码和序号、树级别，A以下的子孙节点，只需要将树节点编码的A部分替换为A的新编码，序号不变，树级别累加固定的差值即可。

5.3 删除操作

删除A节点和其下的子孙节点，只需要通过标准sql查询出A以下的树节点即可删除。

6 应用

设备管理系统中设备主数据包括多个树形结构，例如设备分类、设备功能位置、带子设备的设备档案，将编码表示法应用到设备主数据的表设计中，对于相关统计报表，例如某产线、装置下的所有设备的购置值进行统计，对其下设备的工单成本进行统计，极大地简化了报表开发并提高了检索性能。