編碼表示法表征樹形結構及其在設備管理系統中的應用

褚衍國

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

0 引言

設備全生命周期管理系統，是助力企業(yè)設備管理維護團隊執(zhí)行標準化維護管理的最佳實踐。設備系統的基礎功能為設備主數據，其中功能位置、設備分類的數據結構均為樹形結構。傳統的表征方法一般是父子ID表征法，雖然理解簡單，但其無法提供簡單高效的檢索查詢。

本文闡述了一種編碼表示法表征樹形結構，以便為企業(yè)信息化中（例如設備管理系統中）的多種樹形結構提供簡單高效的檢索。

1 術語和定義

樹形結構：即數據元素之間存在著“一對多”的樹形關系的數據結構，是一類重要的非線性數據結構。

根節(jié)點：即沒有前驅節(jié)點（父節(jié)點），但是具有多個子節(jié)點，每個子節(jié)點也可具備多個子節(jié)點。

葉子節(jié)點：該節(jié)點沒有后續(xù)節(jié)點，其余每個節(jié)點的后續(xù)節(jié)點數可以是多個。

樹級別：根節(jié)點級別為0，其子節(jié)點級別為0+1，以此類推。

兄弟節(jié)點：同一個父節(jié)點的同一個樹級別的子節(jié)點即為兄弟節(jié)點。

編碼表示法：根據父節(jié)點和樹級別以及兄弟節(jié)點順序來實現編碼表示某一節(jié)點的方法。不同級別的節(jié)點其有效編碼位數不一樣。

2 父子ID表征樹結構分析

在該方法中，節(jié)點數據必須具備兩個字段，即ID和parentID，分別表示本節(jié)點和其父節(jié)點。如果parentID為null，則表示本節(jié)點為根節(jié)點。

另外，對于父子ID表征樹來說，如果需要獲取節(jié)點1下面的所有節(jié)點，需要遞歸獲取每一級的子節(jié)點。眾所周知，遞歸算法的性能消耗極大，對于數據庫來說，標準sql不具備這種能力。對于個別數據庫例如oracle，雖然其提供了start with...connect by方法，但是這種方法性能消耗較大，且不通用。

3 編碼表示法闡述

編碼表示法需要4個字段來表征樹形節(jié)點進而表征樹結構，包括樹編碼、樹級別、兄弟序號、是否葉子節(jié)點。

樹編碼：表示樹節(jié)點，編碼唯一，其內部編碼結構下文詳細闡述。

樹級別：根節(jié)點樹級別為1（也可以0為基準），每增加一級則級別加1，兄弟節(jié)點自然級別一致。

兄弟序號：同一個父節(jié)點下的兄弟節(jié)點之間的順序號，以此來表征兄弟節(jié)點順序。結合父節(jié)點的序號和分隔符可以實現帶順序的樹形結構。可以0或者1為順序基準。

是否葉子節(jié)點：如果本節(jié)點無子節(jié)點則為葉子節(jié)點，方便檢索查詢。

X位編碼表示：一般根據實際業(yè)務情況，如果某節(jié)點下的子節(jié)點數目按照十進制來計算的話，某一級的節(jié)點數目的最大值達到5位數，則為5位編碼表示法。一般來說，4位編碼表示法即9999即可滿足大多數需求。

以4位編碼表示法為例分析如下：

后綴分隔符：此處以英文半角減號為后綴分隔符，方便累進計算樹編碼和后續(xù)的最小化插入和剪接操作。

4位編碼表示法情況下，以1為順序基準，則根節(jié)點自然為“0001-”。根節(jié)點下的子節(jié)點則以根節(jié)點的樹編碼為前綴加上其兄弟序號對應的4位字符串形式加上后綴分隔符，即生成第一級子節(jié)點編碼形如“0001-0001-”“0001-0002-”。同理依次類推，各個節(jié)點下的子節(jié)點可為“0001-0002-0001-”，“0001-0002-0002-”。

可以看出，以分隔符分隔，每一級別的編碼均為該級別下本節(jié)點或本節(jié)點的上級節(jié)點在其兄弟節(jié)點中的序號的4位字符串形式。按照樹編碼來排序，天然表征了帶順序的樹結構。

4 編碼表示法下的檢索

定義樹節(jié)點集合存儲的關系數據庫表名稱為TreeTable，樹節(jié)點字段分別為TreeCode，Treelevel，SNo，IsLeaf。$destreecode為某節(jié)點的樹編碼，$destreelevel為樹級別。

（1）正向檢索：即檢索某節(jié)點及其所有子孫節(jié)點。Sql偽碼如下：

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

可以看出這是標準sql語句，各大關系數據庫均可支持，且語句簡單，搭配數據庫索引可以高性能地檢索。

（2）逆向檢索：即檢索某節(jié)點及其所有父輩節(jié)點。Sql偽碼如下：

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

此處依然使用了標準sql的like語句，但是是倒like。語句仍然極其簡單。

（3）同級檢索：即檢索同一級別的節(jié)點。Sql偽碼如下：

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

（4）葉子節(jié)點檢索：即檢索所有葉子節(jié)點。Sql偽碼如下：

select*from TreeTable where IsLeaf=True order by TreeCode

如果需要其他額外檢索條件，可以自行根據需要改變以上sql。

由此看出，編碼表示法的檢索極其簡單高效，對于實際業(yè)務應用中的報表統計來說，極大地簡化了開發(fā)難度，提高了檢索性能。

5 編碼表示法的插入、變更、刪除

雖然編碼表示法提供了簡單高效的檢索，但是在遇到插入、變更情況時將影響很多節(jié)點，本節(jié)將對此進行闡述。

5.1 插入操作

5.1.1 尾部插入

這是最簡單的一種情況，在某尾部節(jié)點后插入，只需要在原尾部節(jié)點基礎上，將序號加1，并形成對應的樹節(jié)點編碼即可。

5.1.2 中間插入

某節(jié)點（非尾部和頭部節(jié)點）后插入一個新節(jié)點C，則需要計算新序號CSNo，新序號的計算方法如下：

某中間節(jié)點A，其后節(jié)點為B，則A與B的序號之差為Diff。

根據Diff，分析得到對應的序號步進值StepV。Diff=1，則StepV=0.1；Diff小于1，且為n位小數，則StepV=0.{n位0}1；Diff大于1，則StepV=1。

新的樹節(jié)點序號為CSNo={A的序號}+{StepV}，得到的值可能是小數，該序號值整數部分補足4位得到最終該級別字符串值（形如1234.2或0023），為CCurCode。C對應的樹編碼則為｛A的樹編碼｝移除最后一級編碼+{CCurCode}。

這種算法的好處是可以在兩個節(jié)點下無限擴充插入新節(jié)點，但是又不至于節(jié)點編碼擴張?zhí)臁＠缍掷奂臃ㄒ部梢詫崿F，但是多次插入后會極大增加樹編碼的長度。

5.1.3 頭部插入

在頭部節(jié)點A前插入新節(jié)點C，則計算A的序號與0的差值Diff，然后參考中間插入算法計算得到C的序號和C的樹編碼即可。

可以看出，插入操作的算法稍微復雜一些，但是影響的節(jié)點只有自身和父節(jié)點。

5.2 變更操作

變更操作，有點類似于樹木的枝干剪接到另一個枝干節(jié)點，即將某節(jié)點A和其下的子孫節(jié)點改變到另一個節(jié)點下。此時可以對A節(jié)點計算得到新的樹編碼和序號、樹級別，A以下的子孫節(jié)點，只需要將樹節(jié)點編碼的A部分替換為A的新編碼，序號不變，樹級別累加固定的差值即可。

5.3 刪除操作

刪除A節(jié)點和其下的子孫節(jié)點，只需要通過標準sql查詢出A以下的樹節(jié)點即可刪除。

6 應用

設備管理系統中設備主數據包括多個樹形結構，例如設備分類、設備功能位置、帶子設備的設備檔案，將編碼表示法應用到設備主數據的表設計中，對于相關統計報表，例如某產線、裝置下的所有設備的購置值進行統計，對其下設備的工單成本進行統計，極大地簡化了報表開發(fā)并提高了檢索性能。