[TREE]采用左右值編碼來存儲無限分級樹形結(jié)構(gòu)的數(shù)據(jù)庫表設(shè)計(jì)

1、采用左右值編碼來存儲無限分級樹形結(jié)構(gòu)的數(shù)據(jù)庫表設(shè)計(jì)之前我介紹過一種按位數(shù)編碼保存樹形結(jié)構(gòu)數(shù)據(jù)的表設(shè)計(jì)方法，詳情見：淺談數(shù)據(jù)庫設(shè)計(jì)技巧（上）該設(shè)計(jì)方案的優(yōu)點(diǎn)是：只用一條查詢語句即可得到某個(gè)根節(jié)點(diǎn)及其所有子孫節(jié)點(diǎn)的先序遍歷。由于消除了遞歸，在數(shù)據(jù)記錄量較大時(shí)，可以大大提高列表效率。但是，這種編碼方案由于層信息位數(shù)的限制，限制了每層能所允許的最大子節(jié)點(diǎn)數(shù)量及最大層數(shù)。同時(shí)，在添加新節(jié)點(diǎn)的時(shí)候必須先計(jì)算新節(jié)點(diǎn)的位置是否超過最大限制。php寫上面的設(shè)計(jì)方案必須預(yù)先設(shè)定類別樹的最大層數(shù)以及最大子節(jié)點(diǎn)數(shù)，不是無限分級，在某些場合并不能采用，那么還有更完美的解決方案嗎？通過google的搜索，我又探索到一種全

2、新的無遞歸查詢，無限分級的編碼方案一一左右值。原文的程序代碼是用的，但是通過仔細(xì)閱讀其數(shù)據(jù)庫表設(shè)計(jì)說明及相關(guān)的sql語句，我徹底弄懂了這種巧妙的設(shè)計(jì)思路，并在這種設(shè)計(jì)中新增了刪除節(jié)點(diǎn),同層平移的需求（原文只提供了列表及插入子節(jié)點(diǎn)的sql語句）。下面我力圖用比較簡短的文字，少量圖表，及相關(guān)核心sql語句來描述這種設(shè)計(jì)方案：首先，我們弄一棵樹作為例子：商品|-食品|-肉類|-豬肉|-蔬菜類|卜白菜|-電器|-電視機(jī)|-電冰箱采用左右值編碼的保存該樹的數(shù)據(jù)記錄如下（設(shè)表名為tree）Type_idNameLftRgt1商品1182食品2113肉類364豬肉455蔬菜類7106白菜897電器12178

3、電視機(jī)13149電冰箱1516第一次看見上面的數(shù)據(jù)記錄，相信大部分人都不清楚左值（Lft）和右值（Rgt）是根據(jù)什么規(guī)則計(jì)算出來的，而且，這種表設(shè)計(jì)似乎沒有保存父節(jié)點(diǎn)的信息。下面把左右值和樹結(jié)合起來，請看：1商品18+2食品1112電器17+3肉類67蔬菜類1013電視機(jī)1415電冰箱164豬肉58白菜9請用手指指著上圖中的數(shù)字，從1數(shù)到18,學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的朋友肯定會發(fā)現(xiàn)什么吧？對，你手指移動(dòng)的順序就是對這棵樹的進(jìn)行先序遍歷的順序。接下來，讓我講述一下如何利用節(jié)點(diǎn)的左右值，得到該節(jié)點(diǎn)的父節(jié)點(diǎn)，子孫節(jié)點(diǎn)數(shù)量，及自己在樹中的層數(shù)。假定我們要對節(jié)點(diǎn)食品”及其子孫節(jié)點(diǎn)進(jìn)行先序遍歷的列表，只需使用如下

4、一條sql語句：select*fromtreewhereLftbetween2and11orderbyLftasc查詢結(jié)果如下：Type_idNameLftRgt2食品2113肉類364豬肉455蔬菜類7106白菜89那么某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)呢？很簡單，子孫總數(shù)=（右值-左值-1）/2以節(jié)點(diǎn)食品”舉例，其子孫總數(shù)=（11-2-1）/2=4同時(shí)，我們在列表顯示整個(gè)類別樹的時(shí)候，為了方便用戶直觀的看到樹的層次，一般會根據(jù)節(jié)點(diǎn)所處的層數(shù)來進(jìn)行相應(yīng)的縮進(jìn)，那么，如何計(jì)算節(jié)點(diǎn)在樹中的層數(shù)呢？還是只需通過左右值的查詢即可，以節(jié)點(diǎn)寰品"舉例，sql語句如下：selectcount(*)fro

5、mtreewhere1ft<=2andrgt>=11為了方便列表，我們可以為tree表建立一個(gè)視圖，添加一個(gè)層數(shù)列，該類別的層數(shù)可以寫一個(gè)自定義函數(shù)來計(jì)算。該函數(shù)如下：CREATEFUNCTIONdbo.CountLayer(type_idint)RETURNSintASbegindeclareresultintsetresult=0declarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginselectlft=lft,rgt=rgtfromtreewheretype_id=type_ids

6、electresult=count(*)fromtreewherelft<=lftandrgt>=rgtendreturnresultendGO然后，我們建立如下視圖：CREATEVIEWdbo.TreeViewASSELECTtype_id,name,lft,rgt,dbo.CountLayer(type_id)ASlayerFROMdbo.treeORDERBYlftGO給出對于給定某個(gè)節(jié)點(diǎn)，對該節(jié)點(diǎn)及其子孫節(jié)點(diǎn)進(jìn)行先序遍歷的存儲過程：CREATEPROCEDUREdbo.GetTreeListByNode(type_idint-給定節(jié)點(diǎn)標(biāo)識)ASdeclarelftintde

7、clarergtintifexists(select1fromtreewheretype_id=type_id)beginselectlft=lft,rgt=rgtfromtreewheretype_id=type_id口select*fromTreeViewwherelftbetweenlftandrgtorderbylftascIIendgo現(xiàn)在，我們使用上面的存儲過程來列表節(jié)點(diǎn)食品”及其所有子孫節(jié)點(diǎn)，查詢結(jié)果如下:Type_idNameLftRgtLayer2食品21123肉類3634豬肉4545蔬菜類71036白菜894采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行類別樹的遍歷時(shí)，由于只需進(jìn)行2次查

8、詢，消除了遞歸，再加上查詢條件都為數(shù)字比較，效率極高，類別樹的記錄條目越多，執(zhí)行效率越高?？吹竭@里，相信不少人對這種設(shè)計(jì)方案有所心動(dòng)了，下面讓我們接著看看如何在這種表結(jié)構(gòu)中實(shí)現(xiàn)插入、刪除、同層平移節(jié)點(diǎn)（變更同層節(jié)點(diǎn)排序）的功能。假定我們要在節(jié)點(diǎn)肉類”下添加一個(gè)子節(jié)點(diǎn)牛肉”，該樹將變成：1商品18+2+2食品11+212+2電器17+2+3肉類6+27+2蔬菜類10+213+2電視機(jī)14+215+2電冰箱16+2+4豬肉56牛肉78+2白菜9+2看完上圖相應(yīng)節(jié)點(diǎn)左右值的變化后，相信大家都知道該如何寫相應(yīng)的sql腳本吧？下面我給出相對完整的插入子節(jié)點(diǎn)的存儲過程：CREATEPROCEDUREdbo

9、.AddSubNodeByNode(type_idint,namevarchar(50)ASdeclarergtintifexists(select1fromtreewheretype_id=type_id)一beginSETXACT_ABORTONBEGINTRANSACTIONselectrgt=rgtfromtreewheretype_id=type_idupdatetreesetrgt=rgt+2wherergt>=rgt一updatetreesetlft=lft+2wherelft>=rgtinsertintotree(name,lft,rgt)values(name,r

10、gt,rgt+1)COMMITTRANSACTIONSETXACT_ABORTOFFendgo然后，我們刪除節(jié)點(diǎn)電視機(jī)”，再來看看該樹會變成什么情況：1商品20-2+2食品1314電器19-2+3肉類89蔬菜類1217-2電冰箱18-2+4豬肉56牛肉710白菜11相應(yīng)的存儲過程如下：CREATEPROCEDUREdbo.DelNodetype_idintASdeclarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginSETXACT_ABORTONBEGINTRANSACTIONselectlft=lf

11、t,rgt=rgtfromtreewheretype_id=type_iddeletefromtreewherelft>=lftandrgt<=rgtupdatetreesetlft=lft-(rgt-lft+1)wherelft>lft一updatetreesetrgt=rgt-(rgt-lft+1)wherergt>rgtCOMMITTRANSACTIONSETXACT_ABORTOFFEnd注意：因?yàn)閯h除某個(gè)節(jié)點(diǎn)會同時(shí)刪除該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，而這些被刪除的節(jié)點(diǎn)的個(gè)數(shù)為：（被刪節(jié)點(diǎn)的右值-被刪節(jié)點(diǎn)的左值+1）/2，而任何一個(gè)節(jié)點(diǎn)同時(shí)具有唯一的左值和唯一的右值，故刪

12、除作廢節(jié)點(diǎn)后，其他相應(yīng)節(jié)點(diǎn)的左、右值需要調(diào)整的幅度應(yīng)為：減少（被刪節(jié)點(diǎn)的右值-被刪節(jié)點(diǎn)的左值+1）。最后，讓我們看看平移節(jié)點(diǎn)電器”，將其和其所有子孫節(jié)點(diǎn)移動(dòng)到節(jié)點(diǎn)食品”之前后，該樹會變成什么情況：1商品18+14-12電器17-122+4食品13+4+15-12電冰箱16-123+4肉類8+49+4蔬菜類12+4+4+4豬肉5+46+4牛肉7+410+4白菜11+4大家仔細(xì)觀察一下交換后同層2個(gè)節(jié)點(diǎn)和其所有子孫節(jié)點(diǎn)左右值的變化，可以發(fā)現(xiàn)一個(gè)明顯的規(guī)律，那就是，節(jié)點(diǎn)電器”及其所有子孫節(jié)點(diǎn)的左右值均減少12,而節(jié)點(diǎn)食品”及其所有子孫節(jié)點(diǎn)的左右值均增加4o而節(jié)點(diǎn)電器”+其子孫節(jié)點(diǎn)的數(shù)量為2,節(jié)點(diǎn)食品

13、”+其子孫節(jié)點(diǎn)的數(shù)量為6,這其中有什么聯(lián)系嗎?還記得我在刪除節(jié)點(diǎn)的存儲過程后面的注釋嗎？任何一個(gè)節(jié)點(diǎn)同時(shí)具有唯一的左值和唯一的右值。讓我們把節(jié)點(diǎn)數(shù)量*2,正好和節(jié)點(diǎn)左右值需要調(diào)整的幅度相等。由此規(guī)律，我們可以編寫出類似下面的存儲過程來實(shí)現(xiàn)節(jié)點(diǎn)同層前移的功能：CREATEPROCEDUREdbo.MoveNodeUptype_idintASdeclarelftintdeclarergtintdeclarelayerintifexists（select1fromtreewheretype_id=type_id）beginSETXACT_ABORTONBEGINTRANSACTIONselectlf

14、t=1ft,rgt=rgt,layer=layerfromTreeViewwhereifexists(select*fromTreeViewwherergt=lft-1andlayertype_id=type_id=layerdlayerdeclaredeclareselect=layerupdatebrother_lftbrother_rgtbrother_lfttreesetintint=lft,brother_rgt=rgtfromTreeViewwherergt=lft-1anlft=lft-(brother_rgt-brother_lft+1)wherelft>=lftandr

15、gtbegin<=rgtupdatetreesetlft=lft+(rgt-lft+1)wherelft>=brother_lftandrgt<=brother_rgtupdatetreesetrgt=rgt-(brother_rgt-brother_lft+1)wherergt>brother_rgtandrgt<=rgtupdatetreesetrgt=rgt+(rgt-lft+1)wherelft>=brother_lft+(rgt-lft+1)andrgt<=brother_rgtendCOMMITTRANSACTIONSETXACTABORT

16、OFFend注意：節(jié)點(diǎn)的同層平移可以采用臨時(shí)表來做中介，降低代碼的復(fù)雜度。不用臨時(shí)表來處理也行，但是update語句順序一定要考慮周詳。否則，一旦出現(xiàn)bug,對整個(gè)類別表的破壞是驚人的，強(qiáng)烈推薦在做上述工作前對類別表進(jìn)行完整備份。同層下移的存儲過程和同層上移類似，有興趣的朋友可以自己動(dòng)手編寫體味一下其中的細(xì)節(jié)，我就不在這里列出來了。最后，我對上面這種左右值編碼實(shí)現(xiàn)無限分級類別樹的方案做一個(gè)總結(jié):優(yōu)點(diǎn)：在消除遞歸的前提下實(shí)現(xiàn)了無限分級，而且查詢條件是基于整形數(shù)字比較的，效率很高。可以進(jìn)行先序列表，添加，修改，刪除，同層平移等常規(guī)操作，基本滿足需求。缺點(diǎn)：由于這種左右值編碼的方式和常見的阿拉伯?dāng)?shù)字

17、直觀排序不同，再加上節(jié)點(diǎn)在樹中的層次，順序不是直觀顯示出來,而必須通過簡單的公式計(jì)算后得到，需要花費(fèi)一定的時(shí)間對其數(shù)學(xué)模型進(jìn)行深入理解。而且，采用該方案編寫相關(guān)存儲過程，新增，刪除，同層平移節(jié)點(diǎn)需要對整個(gè)樹進(jìn)行查詢修改，由此導(dǎo)致的代碼復(fù)雜度，耦合度較高，修改維護(hù)的風(fēng)險(xiǎn)較高。發(fā)表于2007年04月26日16:36:00|評論（4倒）|編輯新一篇：自定義Membershipprovider來利用A2.0Login控件的登陸和修改密碼模塊|舊一篇：分頁存儲過程的一點(diǎn)心得老板心里你有多重？確立職場位置，明確自身重要性Leo教你看清前途老板心里你有多重？確立職場位置，明確自身重要性Leo教你看清前途評論

18、# hometohome發(fā)表于2008-05-0722:17:19IP:123.115.4.*請問該如何根據(jù)子節(jié)點(diǎn)的type_id找出父節(jié)點(diǎn)呢？比如：豬肉的父節(jié)點(diǎn)是肉類、食品、商品# _hometohome發(fā)表于2008-05-0722:38:54IP:123.115.4.*declarergtintselectrgt=rgtfromtreewheretype_id=13select*fromtreewherergt>=rgtandlft<=rgtorderbylft我是樓上的。這么做可否？# greki發(fā)表于2008-10-1117:49:40IP:125.122.194.*非常感謝，試過很好用,另外我不懂存儲過程,CREATEPROCEDUREdbo.GetTreeListByNode(type_idint-給定節(jié)點(diǎn)標(biāo)識)ASdeclarelftintdeclarergtintifexists(select1fromtreewheretype_id=type_id)beginselectlft=lft,rgt=rgtfromtreewheretype_id=type_idselect*fromTreeViewwherelftbetweenlftandrgtorderbylftasc