程式設計過程中，我們常常用樹形結構來表征某些資料的關聯關系，如企業上下級部門、欄目結構、商品分類等等，通常而言，這些樹狀結構需要借助于資料庫完成持久化。然而目前的各種基于關系的資料庫，都是以二維表的形式記錄存儲資料資訊，是以是不能直接将tree存入dbms，設計合适的schema及其對應的crud算法是實作關系型資料庫中存儲樹形結構的關鍵。
理想中樹形結構應該具備如下特征：資料存儲備援度小、直覺性強；檢索周遊過程簡單高效；節點增删改查crud操作高效。無意中在網上搜尋到一種很巧妙的設計，原文是英文，看過後感覺有點意思，于是便整理了一下。本文将介紹兩種樹形結構的schema設計方案：一種是直覺而簡單的設計思路，另一種是基于左右值編碼的改進方案。
一、基本資料
本文列舉了一個食品族譜的例子進行講解，通過類别、顔色和品種組織食品，樹形結構圖如下：
二、繼承關系驅動的schema設計
對樹形結構最直覺的分析莫過于節點之間的繼承關系上，通過顯示地描述某一節點的父節點，進而能夠建立二維的關系表，則這種方案的tree表結構通常設計為：{node_id,parent_id}，上述資料可以描述為如下圖所示：
這種方案的優點很明顯：設計和實作自然而然，非常直覺和友善。缺點當然也是非常的突出：由于直接地記錄了節點之間的繼承關系，是以對tree的任何crud操作都将是低效的，這主要歸根于頻繁的“遞歸”操作，遞歸過程不斷地通路資料庫，每次資料庫io都會有時間開銷。當然，這種方案并非沒有用武之地，在tree規模相對較小的情況下，我們可以借助于緩存機制來做優化，将tree的資訊載入記憶體進行處理，避免直接對資料庫io操作的性能開銷。
三、基于左右值編碼的schema設計
在基于資料庫的一般應用中，查詢的需求總要大于删除和修改。為了避免對于樹形結構查詢時的“遞歸”過程，基于tree的前序周遊設計一種全新的無遞歸查詢、無限分組的左右值編碼方案，來儲存該樹的資料。
第一次看見這種表結構，相信大部分人都不清楚左值（lft）和右值（rgt）是如何計算出來的，而且這種表設計似乎并沒有儲存父子節點的繼承關系。但當你用手指指着表中的數字從1數到18，你應該會發現點什麼吧。對，你手指移動的順序就是對這棵樹進行前序周遊的順序，如下圖所示。當我們從根節點food左側開始，标記為1，并沿前序周遊的方向，依次在周遊的路徑上标注數字，最後我們回到了根節點food，并在右邊寫上了18。
依據此設計，我們可以推斷出所有左值大于2，并且右值小于11的節點都是fruit的後續節點，整棵樹的結構通過左值和右值存儲了下來。然而，這還不夠，我們的目的是能夠對樹進行crud操作，即需要構造出與之配套的相關算法。
四、樹形結構crud算法
（1）擷取某節點的子孫節點
隻需要一條sql語句，即可傳回該節點子孫節點的前序周遊清單，以fruit為例：select* from tree where lft between 2 and 11 order by lft asc。查詢結果如下所示：
那麼某個節點到底有多少的子孫節點呢？通過該節點的左、右值我們可以将其子孫節點圈進來，則子孫總數 = (右值 – 左值– 1) / 2，以fruit為例，其子孫總數為：(11 –2 – 1) / 2 = 4。同時，為了更為直覺地展現樹形結構，我們需要知道節點在樹中所處的層次，通過左、右值的sql查詢即可實作，以fruit為例：selectcount(*) from tree where lft <= 2 and rgt >=11。為了友善描述，我們可以為tree建立一個視圖，添加一個層次數列，該列數值可以寫一個自定義函數來計算，函數定義如下：
[sql] view
plaincopy
create function dbo.countlayer
(
@node_id int
)
returns int
as
begin
declare @result int
set @result = 0
declare @lft int
declare @rgt int
if exists(select node_id from tree where node_id = @node_id)
begin
select @lft = lft, @rgt = rgt from tree where node_id = @node_id
select @result = count(*) from tree where lft <= @lft and rgt >= @rgt
end
return @result
end
go
基于層次計算函數，我們建立一個視圖，添加了新的記錄節點層次的數列：
create view dbo.treeview
select node_id, name, lft, rgt, dbo.countlayer(node_id) as layer from dbo.tree order by lft
建立存儲過程，用于計算給定節點的所有子孫節點及相應的層次：
create procedure [dbo].[getchildrennodelist]
declare @lft int
declare @rgt int
if exists(select node_id from tree where node_id = @node_id)
select * from treeview where lft between @lft and @rgt order by lft asc
現在，我們使用上面的存儲過程來計算節點fruit所有子孫節點及對應層次，查詢結果如下：
從上面的實作中，我們可以看出采用左右值編碼的設計方案，在進行樹的查詢周遊時，隻需要進行2次資料庫查詢，消除了遞歸，再加上查詢條件都是數字的比較，查詢的效率是極高的，随着樹規模的不斷擴大，基于左右值編碼的設計方案将比傳統的遞歸方案查詢效率提高更多。當然，前面我們隻給出了一個簡單的擷取節點子孫的算法，真正地使用這棵樹我們需要實作插入、删除同層平移節點等功能。
（2）擷取某節點的族譜路徑
假定我們要獲得某節點的族譜路徑，則根據左、右值分析隻需要一條sql語句即可完成，以fruit為例：select* from tree where lft < 2 and rgt > 11 order by lft asc ，相對完整的存儲過程：
create procedure [dbo].[getparentnodepath]
select * from treeview where lft < @lft and rgt > @rgt order by lft asc
（3）為某節點添加子孫節點
假定我們要在節點“red”下添加一個新的子節點“apple”，該樹将變成如下圖所示，其中紅色節點為新增節點。
仔細觀察圖中節點左右值變化，相信大家都應該能夠推斷出如何寫sql腳本了吧。我們可以給出相對完整的插入子節點的存儲過程：
create procedure [dbo].[addsubnode]
@node_id int,
@node_name varchar(50)
set xact_abort on
begin transction
select @rgt = rgt from tree where node_id = @node_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(@node_name, @rgt, @rgt + 1)
commit transaction
set xact_abort off
（4）删除某節點
如果我們想要删除某個節點，會同時删除該節點的所有子孫節點，而這些被删除的節點的個數為：(被删除節點的右值 – 被删除節點的左值+ 1) / 2，而剩下的節點左、右值在大于被删除節點左、右值的情況下會進行調整。來看看樹會發生什麼變化，以beef為例，删除效果如下圖所示。
則我們可以構造出相應的存儲過程：
create procedure [dbo].[delnode]
select @lft = lft, @rgt = rgt from tree where node_id = @node_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
五、總結
我們可以對這種通過左右值編碼實作無限分組的樹形結構schema設計方案做一個總結：
（1）優點：在消除了遞歸操作的前提下實作了無限分組，而且查詢條件是基于整形數字的比較，效率很高。
（2）缺點：節點的添加、删除及修改代價較大，将會涉及到表中多方面資料的改動。
當然，本文隻給出了幾種比較常見的crud算法的實作，我們同樣可以自己添加諸如同層節點平移、節點下移、節點上移等操作。有興趣的朋友可以自己動手編碼實作一下，這裡不在列舉了。值得注意的是，實作這些算法可能會比較麻煩，會涉及到很多條update語句的順序執行，如果順序排程考慮不周詳，出現bug的話将會對整個樹形結構表産生驚人的破壞。是以，在對樹形結構進行大規模修改的時候，可以采用臨時表做中介，以降低代碼的複雜度，同時，強烈推薦在做修改之前對表進行完整備份，以備不時之需。在以查詢為主的絕大多數基于資料庫的應用系統中，該方案相比傳統的由父子繼承關系建構的資料庫schema更為适用。