編碼表示法表征樹形結(jié)構(gòu)及其在設(shè)備管理系統(tǒng)中的應(yīng)用

褚衍國(guó)

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

0 引言

設(shè)備全生命周期管理系統(tǒng)，是助力企業(yè)設(shè)備管理維護(hù)團(tuán)隊(duì)執(zhí)行標(biāo)準(zhǔn)化維護(hù)管理的最佳實(shí)踐。設(shè)備系統(tǒng)的基礎(chǔ)功能為設(shè)備主數(shù)據(jù)，其中功能位置、設(shè)備分類的數(shù)據(jù)結(jié)構(gòu)均為樹形結(jié)構(gòu)。傳統(tǒng)的表征方法一般是父子ID表征法，雖然理解簡(jiǎn)單，但其無法提供簡(jiǎn)單高效的檢索查詢。

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

1 術(shù)語和定義

樹形結(jié)構(gòu)：即數(shù)據(jù)元素之間存在著“一對(duì)多”的樹形關(guān)系的數(shù)據(jù)結(jié)構(gòu)，是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。

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

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

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

兄弟節(jié)點(diǎn)：同一個(gè)父節(jié)點(diǎn)的同一個(gè)樹級(jí)別的子節(jié)點(diǎn)即為兄弟節(jié)點(diǎn)。

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

2 父子ID表征樹結(jié)構(gòu)分析

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

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

3 編碼表示法闡述

編碼表示法需要4個(gè)字段來表征樹形節(jié)點(diǎn)進(jìn)而表征樹結(jié)構(gòu)，包括樹編碼、樹級(jí)別、兄弟序號(hào)、是否葉子節(jié)點(diǎn)。

樹編碼：表示樹節(jié)點(diǎn)，編碼唯一，其內(nèi)部編碼結(jié)構(gòu)下文詳細(xì)闡述。

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

兄弟序號(hào)：同一個(gè)父節(jié)點(diǎn)下的兄弟節(jié)點(diǎn)之間的順序號(hào)，以此來表征兄弟節(jié)點(diǎn)順序。結(jié)合父節(jié)點(diǎn)的序號(hào)和分隔符可以實(shí)現(xiàn)帶順序的樹形結(jié)構(gòu)?？梢?或者1為順序基準(zhǔn)。

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

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

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

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

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

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

4 編碼表示法下的檢索

定義樹節(jié)點(diǎn)集合存儲(chǔ)的關(guān)系數(shù)據(jù)庫(kù)表名稱為TreeTable，樹節(jié)點(diǎn)字段分別為TreeCode，Treelevel，SNo，IsLeaf。$destreecode為某節(jié)點(diǎn)的樹編碼，$destreelevel為樹級(jí)別。

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

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

可以看出這是標(biāo)準(zhǔn)sql語句，各大關(guān)系數(shù)據(jù)庫(kù)均可支持，且語句簡(jiǎn)單，搭配數(shù)據(jù)庫(kù)索引可以高性能地檢索。

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

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

此處依然使用了標(biāo)準(zhǔn)sql的like語句，但是是倒like。語句仍然極其簡(jiǎn)單。

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

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

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

select*from TreeTable where IsLeaf=True order by TreeCode

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

由此看出，編碼表示法的檢索極其簡(jiǎn)單高效，對(duì)于實(shí)際業(yè)務(wù)應(yīng)用中的報(bào)表統(tǒng)計(jì)來說，極大地簡(jiǎn)化了開發(fā)難度，提高了檢索性能。

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

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

5.1 插入操作

5.1.1 尾部插入

這是最簡(jiǎn)單的一種情況，在某尾部節(jié)點(diǎn)后插入，只需要在原尾部節(jié)點(diǎn)基礎(chǔ)上，將序號(hào)加1，并形成對(duì)應(yīng)的樹節(jié)點(diǎn)編碼即可。

5.1.2 中間插入

某節(jié)點(diǎn)（非尾部和頭部節(jié)點(diǎn)）后插入一個(gè)新節(jié)點(diǎn)C，則需要計(jì)算新序號(hào)CSNo，新序號(hào)的計(jì)算方法如下：

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

根據(jù)Diff，分析得到對(duì)應(yīng)的序號(hào)步進(jìn)值StepV。Diff=1，則StepV=0.1；Diff小于1，且為n位小數(shù)，則StepV=0.{n位0}1；Diff大于1，則StepV=1。

新的樹節(jié)點(diǎn)序號(hào)為CSNo={A的序號(hào)}+{StepV}，得到的值可能是小數(shù)，該序號(hào)值整數(shù)部分補(bǔ)足4位得到最終該級(jí)別字符串值（形如1234.2或0023），為CCurCode。C對(duì)應(yīng)的樹編碼則為｛A的樹編碼｝移除最后一級(jí)編碼+{CCurCode}。

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

5.1.3 頭部插入

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

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

5.2 變更操作

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

5.3 刪除操作

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

6 應(yīng)用

設(shè)備管理系統(tǒng)中設(shè)備主數(shù)據(jù)包括多個(gè)樹形結(jié)構(gòu)，例如設(shè)備分類、設(shè)備功能位置、帶子設(shè)備的設(shè)備檔案，將編碼表示法應(yīng)用到設(shè)備主數(shù)據(jù)的表設(shè)計(jì)中，對(duì)于相關(guān)統(tǒng)計(jì)報(bào)表，例如某產(chǎn)線、裝置下的所有設(shè)備的購(gòu)置值進(jìn)行統(tǒng)計(jì)，對(duì)其下設(shè)備的工單成本進(jìn)行統(tǒng)計(jì)，極大地簡(jiǎn)化了報(bào)表開發(fā)并提高了檢索性能。