數(shù)據(jù)庫“路徑法”無限級分類節(jié)點算法設(shè)計與實現(xiàn)

吳承輝

(福建省經(jīng)濟信息中心教育培訓(xùn)處,福州350002)

0 引言

信息社會中,數(shù)據(jù)信息大量以數(shù)據(jù)庫為媒介進行存儲,要提高數(shù)據(jù)的檢索速度,除了提高計算機軟、硬件性能,合理設(shè)置使用索引等,亦可以通過進行數(shù)據(jù)信息的類別劃分來提高檢索性能。應(yīng)用系統(tǒng)數(shù)據(jù)庫設(shè)計時,分類設(shè)置可以分為:“固定級分類”和“無限級分類”?！盁o限級分類”常采用“遞歸法”進行設(shè)計,但因“遞歸法”進行“遞歸”操作難度高,效率低。所以本論文主要分析“路徑法”的設(shè)計與實現(xiàn)。

1 分類算法類別

1.1 有限級分類

有限級分類一般是在數(shù)據(jù)庫中建立對應(yīng)數(shù)量的級別表,以主、外鍵關(guān)聯(lián)來實現(xiàn)多個不同的分類級別。這種分類實現(xiàn)簡單,級別間關(guān)系清晰,代碼易于實現(xiàn),但是,它只能實現(xiàn)固定層次的分類,而無法做到無限級別,在特定的場合使用會受到極大的限制。

1.2 遞歸法無限級分類

數(shù)據(jù)庫無限級分類常用“遞歸法”,即僅建立一張分類表,采用“自連接”操作,主鍵、外鍵都在此表上;理論上,表的數(shù)據(jù)行無限,則級別無限,采用循環(huán)遞歸的查詢,就可以把各個級別查詢出來;優(yōu)點是結(jié)構(gòu)簡單清晰,可以無限擴充級別,容易添加級別數(shù)據(jù);缺點是用“遞歸算法”創(chuàng)造的結(jié)構(gòu),對分類數(shù)據(jù)查詢難度高、效率低,要精確查詢某個分類及層次比較困難。

1.3 路徑法無限級分類

無限級分類還可以采用“路徑法”。此算法同樣用一張表就可以實現(xiàn)無限級的分類。類別之間的層次直接使用類別的編號組成的字符串先后秩序來識別。此算法優(yōu)點是數(shù)據(jù)查詢速度快,效率高,容易得到各個分類所在的層次。缺點是:路徑信息維護比較煩瑣,需要依靠專門算法過程來實現(xiàn)來維護;“路徑法”理論上是“無限”級分類,但實際分類的級別會受到路徑字段的長短限制,而無法真正達到絕對“無限級”。

2 “路徑法”分類設(shè)計原理

2.1 表結(jié)構(gòu)及示例數(shù)據(jù)圖

“路徑法”采用一張表保存各個分類,結(jié)構(gòu)如表1所示。

iListID_PK:分類ID號,系統(tǒng)自動編號,并設(shè)置唯一值。

sListGUID:預(yù)留字段,GUID值,可以為每個分類編排一個全球唯一標(biāo)識。

sListName:類別名。

sOrder:排序路徑,此字段設(shè)置為主鍵,用它來進行數(shù)據(jù)類別的先后順序排列?！皊Order”字段內(nèi)保存各個分類級別路徑分類編號的ID值。

iDepth:類別所在的級別和深度,它是計算字段

iVisible:預(yù)留字段,設(shè)置此類別是否可見。

示例數(shù)據(jù)圖如圖1所示。

表1 “路徑法”結(jié)構(gòu)表

圖1 示例數(shù)據(jù)圖

2.2 sOrder排序算法規(guī)則

(1)sOrder為字符串類型,默認值為當(dāng)前iListID_PK轉(zhuǎn)換成長度為10個字符的字符串。

例:類別“中國”的 sOrder為“0000000001”。

(2)若當(dāng)前分類在某一其他分類下,則sOrder數(shù)值則為父節(jié)點的sOrder值合并上本節(jié)點的排序值。

例:“江西省”的值為父節(jié)點的 sOrder值“0000000001”加上本節(jié)點的 sOrder值“0000000002”,所以“江 西省”的 sOrder值為“00000000010000000002” 。

例:“南昌市”的值為,父節(jié)點的 sOrder值“00000000010000000002”加上本節(jié)點的 sOrder值“0000000004”,所以“南 昌市”的 sOrder值為“000000000100000000020000000004”

(2)sOrder建立聚集索引。聚集索引的組織形式為Balance Tree,所以分類會嚴(yán)格按照字符串的大小順序排列。

(3)類別順序也是由聚集索引決定。

按照字符串的排序由小到大規(guī)則,“000000000100000000020000000004”一定排列在“000000000100000000020000000008”之前 ,即“南昌市”排列在“吉安市”之前。

若需要調(diào)整“南昌市”和“吉安市”的順序,只需要調(diào)換 sOrder最右邊的 10個字符。即把“0000000004”和“0000000008”調(diào)換即可,不需要改變iListID_PK的值。

(4)類別所在層次用iDepth表示,此字段綁定在一個數(shù)據(jù)庫函數(shù)上,函數(shù)根據(jù)sOrder的長度除10,計算出當(dāng)前類別所在的層次。

3 核心算法代碼

3.1 計算分類節(jié)點函數(shù)

向函數(shù)傳入一個參數(shù),即 sOrder的值,根據(jù)sOrder返回出節(jié)點層次。此函數(shù)綁定在iDepth字段上。

3.2 添加分類節(jié)點值存儲過程。

向存儲過程傳入2個參數(shù),參數(shù)@sListName是分類節(jié)點名稱;參數(shù)@iParentID是父節(jié)點ID,如果父節(jié)點ID為0不存在,則視為創(chuàng)建一個根節(jié)點。

3.3 查詢某節(jié)點值存儲過程。

向此存儲過程傳入3個參數(shù)。參數(shù)@iListID_PK是要查詢的分類節(jié)點ID;參數(shù)@sShowSelf表示是否顯示本節(jié)點,值為“true”表示顯示,“false”表示不顯示;參數(shù)@iListCount是需要查詢的層次,值為-1表示當(dāng)前分類節(jié)點下的所有層次。

4 結(jié)語

無限級分類算法在實際的軟件開發(fā)中具有極高的實際運用價值。本文論述的“路徑法”無限級分類具有結(jié)構(gòu)簡單,查詢運行效率高,分類層次容易識別等特點,可以配合絕大部分的實際系統(tǒng)的分類處理,有較高的實用價值。此算法因路徑為字符串組成,理論上可以達到無限級,此字符串長度受到數(shù)據(jù)庫字段長度的限制,實際分類只能是相對“無限”。本設(shè)計的sOrder長度為900,即只能達到90級,最大行數(shù)編碼為9999999999行,超過10億的大小,這樣的數(shù)量級已可以滿足絕大部分的分類需求。

本論文僅寫出基礎(chǔ)核心算法代碼,分類節(jié)點操作中還有分類節(jié)點位置調(diào)整,分類節(jié)點移動,刪除分類節(jié)點,根據(jù)某節(jié)點分類ID找出父節(jié)點的ID等操作有待讀者進一步挖掘和完善。

[1]Itzik Ben-Gan.Microsoft SQL Server 2008技術(shù)內(nèi)幕[M].北京:電子工業(yè)出版社,2009:346-354.

[2]Robert Vieira.SQ L Server 2005高級程序設(shè)計[M].北京:人民郵電出版社,2008:221-259.

[3]胡百敬,姚巧玫,劉承修.SQL Server 2005 Performance Tuning性能調(diào)校[M].北京:電子工業(yè)出版社.2008:605-619.

[4]李如平.數(shù)據(jù)挖掘中決策樹分類算法的研究[J].東華理工大學(xué)學(xué)報:自然科學(xué)版,2010,33(2):192-196.

[5]趙慧玲,劉美榮.SQL數(shù)據(jù)庫中并發(fā)控制的研究[J].長春工程學(xué)院學(xué)報:自然科學(xué)版,2009,10(2):78-81.

[6]史曉峰,林和平.面向?qū)ο髷?shù)據(jù)庫及其對象查詢處理的研究[J].長春工程學(xué)院學(xué)報:自然科學(xué)版,2008,6(3):66-68.

[7]趙潔紅.購物訂單數(shù)據(jù)庫新息驗證[J].長春工程學(xué)院學(xué)報:自然科學(xué)版,2006,7(1):57-59.