左右值編碼來存儲無限分級樹形結構的資料庫表設計

采用左右值編碼來存儲無限分級樹形結構的資料庫表設計

該設計方案的優點是：隻用一條查詢語句即可得到某個根節點及其所有子孫節點的先序周遊。由于消除了遞歸，在資料記錄量較大時，可以大大提高清單效率。但是，這種編碼方案由于層資訊位數的限制，限制了每層能所允許的最大子節點數量及最大層數。同時，在添加新節點的時候必須先計算新節點的位置是否超過最大限制。

　　上面的設計方案必須預先設定類别樹的最大層數以及最大子節點數，不是無限分級，在某些場合并不能采用，那麼還有更完美的解決方案嗎？通過 google的搜尋，我又探索到一種全新的無遞歸查詢，無限分級的編碼方案——左右值。原文的程式代碼是用php寫的，但是通過仔細閱讀其資料庫表設計說明及相關的sql語句，我徹底弄懂了這種巧妙的設計思路，并在這種設計中新增了删除節點，同層平移的需求（原文隻提供了清單及插入子節點的sql語句）。

　　下面我力圖用比較簡短的文字，少量圖表，及相關核心sql語句來描述這種設計方案：

　　首先，我們弄一棵樹作為例子：

商品

|---食品

|    |---肉類

|    |    |--豬肉 

|    |---蔬菜類 

|          |--白菜 

|---電器 

     |--電視機 

     |--電冰箱

  采用左右值編碼的儲存該樹的資料記錄如下（設表名為 tree）：

Type_id	Name	Lft	Rgt
1	商品	1	18
2	食品	2	11
3	肉類	3	6
4	豬肉	4	5
5	蔬菜類	7	10
6	白菜	8	9
7	電器	12	17
8	電視機	13	14
9	電冰箱	15	16

  第一次看見上面的資料記錄，相信大部分人都不清楚左值（ Lft）和右值（Rgt）是根據什麼規則計算出來的，而且，這種表設計似乎沒有儲存父節點的資訊。下面把左右值和樹結合起來，請看： 　　　　　　　　　 1商品18 　　　　　+---------------------------------------+                 2食品11                                    12電器17

          +-----------------+                     +---------------------+

    3肉類6          7蔬菜類10          13電視機14       15電冰箱16

    4豬肉5           8白菜9 請用手指指着上圖中的數字，從 1數到18，學習過資料結構的朋友肯定會發現什麼吧？對，你手指移動的順序就是對這棵樹的進行先序周遊的順序。接下來，讓我講述一下如何利用節點的左右值，得到該節點的父節點，子孫節點數量，及自己在樹中的層數。   假定我們要對節點“食品”及其子孫節點進行先序周遊的清單，隻需使用如下一條 sql語句： select * from tree where Lft between 2 and 11 order by Lft asc 查詢結果如下：

Type_id	Name	Lft	Rgt
2	食品	2	11
3	肉類	3	6
4	豬肉	4	5
5	蔬菜類	7	10
6	白菜	8	9

  那麼某個節點到底有多少子孫節點呢？很簡單，子孫總數 ＝（右值 -左值-1）/2  以節點“食品”舉例，其子孫總數＝（ 11-2-1）/ 2 ＝ 4   同時，我們在清單顯示整個類别樹的時候，為了友善使用者直覺的看到樹的層次，一般會根據節點所處的層數來進行相應的縮進，那麼，如何計算節點在樹中的層數呢？還是隻需通過左右值的查詢即可，以節點“食品”舉例， sql語句如下： select count(*) from tree where lft <= 2 and rgt >= 11 為了友善清單，我們可以為 tree表建立一個視圖，添加一個層數列，該類别的層數可以寫一個自定義函數來計算。該函數如下： CREATE   FUNCTION  dbo.CountLayer

(    

     @type_id   int

)

RETURNS   int

AS

begin

     declare   @result   int

     set   @result = 0

     declare   @lft   int

     declare   @rgt   int

     if   exists  ( select   1   from  tree  where  type_id = @type_id )

     begin

         select   @lft = lft, @rgt = rgt  from  tree  where  type_id = @type_id

         select   @result   =   count ( * )  from  tree  where  lft  <=   @lft   and  rgt  >=   @rgt

     end     

     return   @result

end

GO

然後，我們建立如下視圖：

CREATE   VIEW  dbo.TreeView

AS

SELECT  type_id, name, lft, rgt, dbo.CountLayer(type_id)  AS  layer  FROM  dbo.tree  ORDER   BY  lft

GO   給出對于給定某個節點，對該節點及其子孫節點進行先序周遊的存儲過程： CREATE   PROCEDURE   [ dbo ] . [ GetTreeListByNode ]

(

     @type_id   int   -- 給定節點辨別

)

AS

declare   @lft   int

declare   @rgt   int

if   exists  ( select   1   from  tree  where  type_id = @type_id )

     begin

         select   @lft = lft, @rgt = rgt  from  tree  where  type_id = @type_id

         select   *   from  TreeView  where  lft  between   @lft   and   @rgt   order   by  lft  asc

     end

go

  現在，我們使用上面的存儲過程來清單節點“食品”及其所有子孫節點，查詢結果如下：

Type_id	Name	Lft	Rgt	Layer
2	食品	2	11	2
3	肉類	3	6	3
4	豬肉	4	5	4
5	蔬菜類	7	10	3
6	白菜	8	9	4

    采用左右值編碼的設計方案，在進行類别樹的周遊時，由于隻需進行 2次查詢，消除了遞歸，再加上查詢條件都為數字比較，效率極高，類别樹的記錄條目越多，執行效率越高。看到這裡，相信不少人對這種設計方案有所心動了，下面讓我們接着看看如何在這種表結構中實作插入、删除、同層平移節點（變更同層節點排序）的功能。   假定我們要在節點“肉類”下添加一個子節點“牛肉”，該樹将變成：                                      1商品18+2                       +--------------------------------------------+                 2食品11+2                                  12+2電器17+2

          +-----------------+                                    +-------------------------+

    3肉類6+2   7+2蔬菜類10+2         13+2電視機14+2    15+2電冰箱16+2     +-------------+  4豬肉5  6牛肉7  8+2白菜9+2   看完上圖相應節點左右值的變化後，相信大家都知道該如何寫相應的 sql腳本吧？下面我給出相對完整的插入子節點的存儲過程： CREATE   PROCEDURE   [ dbo ] . [ AddSubNodeByNode ]

(

     @type_id   int ,

     @name   varchar ( 50 )

)

AS

declare   @rgt   int

if   exists  ( select   1   from  tree  where  type_id = @type_id )

     begin

        SET  XACT_ABORT  ON

        BEGIN   TRANSACTION

         select   @rgt = rgt  from  tree  where  type_id = @type_id

         update  tree  set  rgt = rgt + 2   where  rgt >= @rgt

         update  tree  set  lft = lft + 2   where  lft >= @rgt

         insert   into  tree (name,lft,rgt)  values  ( @name , @rgt , @rgt + 1 )    

         COMMIT   TRANSACTION

        SET  XACT_ABORT  OFF     

     end

go

  然後，我們删除節點“電視機”，再來看看該樹會變成什麼情況：                                             1商品20-2                        +-----------------------------------+                 2食品13                                14電器19-2

          +-----------------+                

       3肉類8          9蔬菜類12              17-2電冰箱18-2

    +----------+ 4豬肉5  6牛肉7  10白菜11   　　相應的存儲過程如下：

CREATE   PROCEDURE   [ dbo ] . [ DelNode ]  

     @type_id   int

AS

declare   @lft   int

declare   @rgt   int

if   exists  ( select   1   from  tree  where  type_id = @type_id )

     begin

        SET  XACT_ABORT  ON

        BEGIN   TRANSACTION

         select   @lft = lft, @rgt = rgt  from  tree  where  type_id = @type_id

         delete   from  tree  where  lft >= @lft   and  rgt <= @rgt

         update  tree  set  lft = lft - ( @rgt - @lft + 1 )  where  lft > @lft

         update  tree  set  rgt = rgt - ( @rgt - @lft + 1 )  where  rgt > @rgt

         COMMIT   TRANSACTION

        SET  XACT_ABORT  OFF     

End   　　注意：因為删除某個節點會同時删除該節點的所有子孫節點，而這些被删除的節點的個數為：(被删節點的右值-被删節點的左值+1)/2，而任何一個節點同時具有唯一的左值和唯一的右值，故删除廢棄節點後，其他相應節點的左、右值需要調整的幅度應為：減少(被删節點的右值-被删節點的左值+1)。    　　最後，讓我們看看平移節點“電器”，将其和其所有子孫節點移動到節點“食品”之前後，該樹會變成什麼情況：   　　　　　　　　　　　　　1商品18 +-----------------------------------+                 14-12電器17-12                      2+4食品13+4

                                                               +----------------------+                

             15-12電冰箱16-12      3+4肉類8+4      9+4蔬菜類12+4        

                                                +-------------------+ 

                                      4+4豬肉5+4     6+4牛肉7+4 10+4白菜11+4   大家仔細觀察一下交換後同層 2個節點和其所有子孫節點左右值的變化，可以發現一個明顯的規律，那就是，節點“電器”及其所有子孫節點的左右值均減少12，而節點“食品”及其所有子孫節點的左右值均增加4。而節點“電器”+其子孫節點的數量為2，節點“食品”+其子孫節點的數量為6，這其中有什麼聯系嗎？還記得我在删除節點的存儲過程後面的注釋嗎？任何一個節點同時具有唯一的左值和唯一的右值。讓我們把節點數量*2，正好和節點左右值需要調整的幅度相等。由此規律，我們可以編寫出類似下面的存儲過程來實作節點同層前移的功能：

CREATE   PROCEDURE   [ dbo ] . [ MoveNodeUp ]  

     @type_id   int

AS

declare   @lft   int

declare   @rgt   int

declare   @layer   int

if   exists  ( select   1   from  tree  where  type_id = @type_id )

     begin

        SET  XACT_ABORT  ON

        BEGIN   TRANSACTION

         select   @lft = lft, @rgt = rgt, @layer = layer  from  TreeView  where  type_id = @type_id

         if   exists  ( select   *   from  TreeView  where  rgt = @lft - 1   and  layer = @layer )

            begin

                declare   @brother_lft   int

                declare   @brother_rgt   int

                select   @brother_lft = lft, @brother_rgt = rgt  from  TreeView  where  rgt = @lft - 1   and  layer = @layer

                update  tree  set  lft = lft - ( @brother_rgt - @brother_lft + 1 )  where  lft >= @lft   and  rgt <= @rgt

                update  tree  set  lft = lft + ( @rgt - @lft + 1 )  where  lft >= @brother_lft   and  rgt <= @brother_rgt

                update  tree  set  rgt = rgt - ( @brother_rgt - @brother_lft + 1 )  where  rgt > @brother_rgt   and  rgt <= @rgt

                update  tree  set  rgt = rgt + ( @rgt - @lft + 1 )  where  lft >= @brother_lft + ( @rgt - @lft + 1 )  and  rgt <= @brother_rgt

            end

         COMMIT   TRANSACTION

        SET  XACT_ABORT  OFF     

     end   　　注意：節點的同層平移可以采用臨時表來做中介，降低代碼的複雜度。不用臨時表來處理也行，但是 update語句順序一定要考慮周詳。否則，一旦出現bug，對整個類别表的破壞是驚人的，強烈推薦在做上述工作前對類别表進行完整備份。   　　同層下移的存儲過程和同層上移類似，有興趣的朋友可以自己動手編寫體味一下其中的細節，我就不在這裡列出來了。   　　最後，我對上面這種左右值編碼實作無限分級類别樹的方案做一個總結： 　　優點：在消除遞歸的前提下實作了無限分級，而且查詢條件是基于整形數字比較的，效率很高。可以進行先序清單，添加，修改，删除，同層平移等正常操作，基本滿足需求。 　　 缺點：由于這種左右值編碼的方式和常見的阿拉伯數字直覺排序不同，再加上節點在樹中的層次，順序不是直覺顯示出來，而必須通過簡單的公式計算後得到，需要花費一定的時間對其數學模型進行深入了解。而且，采用該方案編寫相關存儲過程，新增，删除，同層平移節點需要對整個樹進行查詢修改，由此導緻的代碼複雜度，耦合度較高，修改維護的風險較高。