昨天有人在QQ小組問起，無(wú)限分層的樹狀結(jié)構(gòu)，數(shù)據(jù)量比較大，在一萬(wàn)條以上，如何設(shè)計(jì)數(shù)據(jù)庫(kù)的結(jié)構(gòu)。其實(shí)這是個(gè)老生常談的問題，一般的做法是有一個(gè) pid字段，為了提高效率，還會(huì)有個(gè)FullPath字段。(一些人還設(shè)置一個(gè)層級(jí)字段，但我不知道這個(gè)字段有何作用)，F(xiàn)ullPath字段可以用 id-id-id….這種方式拼字符串存儲(chǔ)，這樣可以方便地用 like 語(yǔ)句進(jìn)行查詢某個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)。

曾經(jīng)看到過另外一種存儲(chǔ)方式，利用了一般樹結(jié)構(gòu)可以轉(zhuǎn)換二叉樹的這一做法，用二叉樹進(jìn)行存儲(chǔ)，在數(shù)據(jù)量大的情況下，存儲(chǔ)讀效率比上述的常見方案更優(yōu)些，所以特寫此文簡(jiǎn)單介紹一番。

下圖說明了這種方案

如圖所示，在每個(gè)節(jié)點(diǎn)上，有l(wèi)eft ,right兩個(gè)字段，我們看到，圖上從根節(jié)點(diǎn)順著子節(jié)點(diǎn)開始畫一條線，每深入一層left加一，到底后，right=left+1，然后順著節(jié)點(diǎn)回溯，right逐級(jí)加一，一直回到根節(jié)點(diǎn)。

如果要查詢某個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)，比如 fruit 節(jié)點(diǎn) ，條件為 where left between 2 and 11

要查某個(gè)節(jié)點(diǎn)的full path ，比如 banana，條件為 where left<8 and right >9

如果要插入某個(gè)節(jié)點(diǎn)，比如red yellow直接插入一個(gè)節(jié)點(diǎn)，則update left =left+2 where left>=7 ,update right=right+2 where right>7,然后 新節(jié)點(diǎn)的left rigt分別是 7，8。 刪除節(jié)點(diǎn)類似。

這種方式，因?yàn)閕d都是int型數(shù)據(jù)，加上索引后，讀的效率較高。而fullPath字段的方案查詢時(shí)候用的是字符串操作like，效率較低。

在內(nèi)存中，如果要還原樹狀結(jié)構(gòu)，即在每個(gè)節(jié)點(diǎn)上增加pid屬性和children屬性，則稍微麻煩些，可以如下操作：

1. 按left between x and y order by left 取數(shù)據(jù)
2. 順序遍歷數(shù)據(jù)，如果left=上一個(gè)Left+1,則是上一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，設(shè)置兩個(gè)對(duì)象的父子關(guān)系，如果發(fā)生跳號(hào)，則是上一個(gè)節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

OK，大致的方案就介紹到這里

原文鏈接：http://www.cnblogs.com/honghuamin/archive/2011/07/24/2115635.html

【編輯推薦】

1. SQL Server如何動(dòng)態(tài)生成分區(qū)腳本
2. 手把手教你建立SQL數(shù)據(jù)庫(kù)的表分區(qū)
3. 說說抽象SQL(參數(shù)化)的查詢
4. 淺述遠(yuǎn)程Service Broker的實(shí)現(xiàn)
5. 自己動(dòng)手豐衣足食，DIY SQL字符串分解函數(shù)Split