之前我介紹過一種按位數(shù)編碼保存樹形結構數(shù)據(jù)的表設計方法，詳情見：
淺談數(shù)據(jù)庫設計技巧(上) 該設計方案的優(yōu)點是：只用一條查詢語句即可得到某個根節(jié)點及其所有子孫節(jié)點的先序遍歷。由于消除了遞歸，在數(shù)據(jù)記錄量較大時，可以大大提高列表效率。但是，這種編碼方案由于層信息位數(shù)的限制，限制了每層能所允許的最大子節(jié)點數(shù)量及最大層數(shù)。同時，在添加新節(jié)點的時候必須先計算新節(jié)點的位置是否超過最大限制。
上面的設計方案必須預先設定類別樹的最大層數(shù)以及最大子節(jié)點數(shù)，不是無限分級，在某些場合并不能采用，那么還有更完美的解決方案嗎？通過 google的搜索，我又探索到一種全新的無遞歸查詢，無限分級的編碼方案——左右值。原文的程序代碼是用php寫的，但是通過仔細閱讀其數(shù)據(jù)庫表設計說明及相關的sql語句，我徹底弄懂了這種巧妙的設計思路，并在這種設計中新增了刪除節(jié)點，同層平移的需求（原文只提供了列表及插入子節(jié)點的sql語句）。
下面我力圖用比較簡短的文字，少量圖表，及相關核心sql語句來描述這種設計方案：
首先，我們弄一棵樹作為例子：
商品
|---食品
|??? |---肉類
|??? |??? |--豬肉
|??? |---蔬菜類
|????????? |--白菜
|---電器
???? |--電視機
???? |--電冰箱
?
采用左右值編碼的保存該樹的數(shù)據(jù)記錄如下（設表名為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 |
?
第一次看見上面的數(shù)據(jù)記錄，相信大部分人都不清楚左值（Lft）和右值（Rgt）是根據(jù)什么規(guī)則計算出來的，而且，這種表設計似乎沒有保存父節(jié)點的信息。下面把左右值和樹結合起來，請看：
1商品18
+---------------------------------------+
??????????????? 2食品11??????????????????????????????????? 12電器17
????????? +-----------------+???????????????????? +---------------------+
??? 3肉類6????????? 7蔬菜類10????????? 13電視機14?????? 15電冰箱16
??? 4豬肉5?????????? 8白菜9
請用手指指著上圖中的數(shù)字，從1數(shù)到18，學習過數(shù)據(jù)結構的朋友肯定會發(fā)現(xiàn)什么吧？對，你手指移動的順序就是對這棵樹的進行先序遍歷的順序。接下來，讓我講述一下如何利用節(jié)點的左右值，得到該節(jié)點的父節(jié)點，子孫節(jié)點數(shù)量，及自己在樹中的層數(shù)。
?
假定我們要對節(jié)點“食品”及其子孫節(jié)點進行先序遍歷的列表，只需使用如下一條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 |
?
那么某個節(jié)點到底有多少子孫節(jié)點呢？很簡單，子孫總數(shù) ＝（右值-左值-1）/2
以節(jié)點“食品”舉例，其子孫總數(shù)＝（11-2-1）/ 2 ＝ 4
?
同時，我們在列表顯示整個類別樹的時候，為了方便用戶直觀的看到樹的層次，一般會根據(jù)節(jié)點所處的層數(shù)來進行相應的縮進，那么，如何計算節(jié)點在樹中的層數(shù)呢？還是只需通過左右值的查詢即可，以節(jié)點“食品”舉例，sql語句如下：
select count(*) from tree where lft <= 2 and rgt >= 11
然后，我們建立如下視圖：
CREATE?VIEW dbo.TreeView
AS
SELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDER?BY lft
GO ?
給出對于給定某個節(jié)點，對該節(jié)點及其子孫節(jié)點進行先序遍歷的存儲過程：
CREATE?PROCEDURE?[dbo].[GetTreeListByNode]
(
??? @type_id?int?--給定節(jié)點標識
)
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
?
現(xiàn)在，我們使用上面的存儲過程來列表節(jié)點“食品”及其所有子孫節(jié)點，查詢結果如下：
| 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 |
?
?
文章來源:
http://x-spirit.spaces.live.com/Blog/cns!CC0B04AE126337C0!370.entry