我們常常用樹形結(jié)構(gòu)來表征某些數(shù)據(jù)的關(guān)聯(lián)關(guān)系，如企業(yè)上下級部門、欄目結(jié)構(gòu)、商品分類等等，通常而言，這些樹狀結(jié)構(gòu)需要借助于數(shù)據(jù)庫完 成持久化。然而目前的各種基于關(guān)系的數(shù)據(jù)庫，都是以二維表的形式記錄存儲數(shù)據(jù)信息，因此是不能直接將Tree存入DBMS，設(shè)計合適的Schema及其對 應(yīng)的CRUD算法是實現(xiàn)關(guān)系型數(shù)據(jù)庫中存儲樹形結(jié)構(gòu)的關(guān)鍵。
基本數(shù)據(jù)
我們列舉食品族譜的例子進(jìn)行講解，通過類別、顏色和品種組織食品，樹形結(jié)構(gòu)圖如下：
繼承關(guān)系設(shè)計
對樹形結(jié)構(gòu)最直觀的分析莫過于節(jié)點之間的繼承關(guān)系上，通過顯示地描述某一節(jié)點的父節(jié)點，從而能夠建立二維的關(guān)系表，則這種方案的Tree表結(jié)構(gòu)通常設(shè)計為：{Node_id,Parent_id}，上述數(shù)據(jù)可以描述為如下圖所示：
這種方案的優(yōu)點很明顯：設(shè)計和實現(xiàn)自然而然非常直觀和方便。缺點當(dāng)然也是非常的突出：由于直接地記錄了節(jié)點之間的繼承關(guān)系，因此對Tree的任何CRUD操作都將是低效的，這主要歸根于頻繁的“遞歸”操作，遞歸過程不斷地訪問數(shù)據(jù)庫，每次數(shù)據(jù)庫IO都會有時間開銷。當(dāng)然，這種方案并非沒有用武之地，在Tree規(guī)模相對較小的情況下，我們可以借助于緩存機制來做優(yōu)化，將Tree的信息載入內(nèi)存進(jìn)行處理，避免直接對數(shù)據(jù)庫IO操作的性能開銷。
左右值編碼的設(shè)計
在基于數(shù)據(jù)庫的一般應(yīng)用中，查詢的需求總要大于刪除和修改。為了避免對于樹形結(jié)構(gòu)查詢時的“遞歸”過程，基于Tree的前序遍歷設(shè)計一種全新的無遞歸查詢、無限分組的左右值編碼方案，來保存該樹的數(shù)據(jù)。
第一次看見這種表結(jié)構(gòu)，相信大部分人都不清楚左值（Lft）和右值（Rgt）是如何計算出來的，而且這種表設(shè)計似乎并沒有保存父子節(jié)點的繼承關(guān)系。但當(dāng) 你用手指指著表中的數(shù)字從1數(shù)到18，你應(yīng)該會發(fā)現(xiàn)點什么吧。對，你手指移動的順序就是對這棵樹進(jìn)行前序遍歷的順序，如下圖所示。當(dāng)我們從根節(jié)點Food 左側(cè)開始，標(biāo)記為1，并沿前序遍歷的方向，依次在遍歷的路徑上標(biāo)注數(shù)字，最后我們回到了根節(jié)點Food，并在右邊寫上了18。
依據(jù)此設(shè)計，我們可以推斷出所有左值大于2，并且右值小于11的節(jié)點都是Fruit的后續(xù)節(jié)點，整棵樹的結(jié)構(gòu)通過左值和右值存儲了下來。然而，這還不夠，我們的目的是能夠?qū)溥M(jìn)行CRUD操作，即需要構(gòu)造出與之配套的相關(guān)算法。
1. 獲取某節(jié)點的子孫節(jié)點
只需要一條SQL語句，即可返回該節(jié)點子孫節(jié)點的前序遍歷列表，以Fruit為例：SELECT * FROM Tree WHERE Lft BETWEEN 2 AND 11 ORDER BY Lft ASC。查詢結(jié)果如下所示：
那么某個節(jié)點到底有多少的子孫節(jié)點呢？通過該節(jié)點的左、右值我們可以將其子孫節(jié)點圈進(jìn)來，則子孫總數(shù) = (右值 – 左值– 1) / 2，以Fruit為例，其子孫總數(shù)為：(11 –2 – 1) / 2 = 4。同時，為了更為直觀地展現(xiàn)樹形結(jié)構(gòu)，我們需要知道節(jié)點在樹中所處的層次，通過左、右值的SQL查詢即可實現(xiàn)，以Fruit為例：SELECT COUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >=11。
從上面的實現(xiàn)中，我們可以看出采用左右值編碼的設(shè)計方案，在進(jìn)行樹的查詢遍歷時，只需要進(jìn)行2次數(shù)據(jù)庫查詢，消除了遞歸，再加上查詢條件都是數(shù)字的比較，查詢的效率是極高的，隨著樹規(guī)模的不斷擴大，基于左右值編碼的設(shè)計方案將比傳統(tǒng)的遞歸方案查詢效率提高更多。當(dāng)然，前面我們只給出了一個簡單的獲取節(jié)點子孫的算法，真正地使用這棵樹我們需要實現(xiàn)插入、刪除同層平移節(jié)點等功能。
2. 獲取某節(jié)點的族譜路徑
假定我們要獲得某節(jié)點的族譜路徑，則根據(jù)左、右值分析只需要一條SQL語句即可完成，以Fruit為例：SELECT * FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC。
3. 為某節(jié)點添加子孫節(jié)點
假定我們要在節(jié)點“Red”下添加一個新的子節(jié)點“Apple”，該樹將變成如下圖所示，其中紅色節(jié)點為新增節(jié)點。
4. 刪除某節(jié)點
如果我們想要刪除某個節(jié)點，會同時刪除該節(jié)點的所有子孫節(jié)點，而這些被刪除的節(jié)點的個數(shù)為：(被刪除節(jié)點的右值 – 被刪除節(jié)點的左值+ 1) / 2，而剩下的節(jié)點左、右值在大于被刪除節(jié)點左、右值的情況下會進(jìn)行調(diào)整。來看看樹會發(fā)生什么變化，以Beef為例，刪除效果如下圖所示。
5. 總結(jié)
優(yōu)點：在消除了遞歸操作的前提下實現(xiàn)了無限分組，而且查詢條件是基于整形數(shù)字的比較，效率很高。
缺點：節(jié)點的添加、刪除及修改代價較大。
參考文獻(xiàn)：《Storing Hierarchical Data in a Database Article》
轉(zhuǎn)載：http://blog.csdn.net/dreajay/article/details/8894058
