吳承輝

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

0 引言

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

1 分類算法類別

1.1 有限級分類

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

1.2 遞歸法無限級分類

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

1.3 路徑法無限級分類

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

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

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

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

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

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

sListName:類別名。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 核心算法代碼

3.1 計(jì)算分類節(jié)點(diǎn)函數(shù)

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

3.2 添加分類節(jié)點(diǎn)值存儲(chǔ)過程。

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

3.3 查詢某節(jié)點(diǎn)值存儲(chǔ)過程。

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

4 結(jié)語

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

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

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

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

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

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

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

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

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