前言

程序設(shè)計(jì)過(guò)程中，我們常常用樹(shù)形結(jié)構(gòu)來(lái)表征某些數(shù)據(jù)的關(guān)聯(lián)關(guān)系，如企業(yè)上下級(jí)部門(mén)、欄目結(jié)構(gòu)、商品分類等等，通常而言，這些樹(shù)狀結(jié)構(gòu)需要借助于數(shù)據(jù)庫(kù)完成持久化。然而目前的各種基于關(guān)系的數(shù)據(jù)庫(kù)，都是以二維表的形式記錄存儲(chǔ)數(shù)據(jù)信息，因此是不能直接將tree存入dbms，設(shè)計(jì)合適的schema及其對(duì)應(yīng)的crud算法是實(shí)現(xiàn)關(guān)系型數(shù)據(jù)庫(kù)中存儲(chǔ)樹(shù)形結(jié)構(gòu)的關(guān)鍵。

理想中樹(shù)形結(jié)構(gòu)應(yīng)該具備如下特征：數(shù)據(jù)存儲(chǔ)冗余度小、直觀性強(qiáng)；檢索遍歷過(guò)程簡(jiǎn)單高效；節(jié)點(diǎn)增刪改查crud操作高效。無(wú)意中在網(wǎng)上搜索到一種很巧妙的設(shè)計(jì)，原文是英文，看過(guò)后感覺(jué)有點(diǎn)意思，于是便整理了一下。本文將介紹兩種樹(shù)形結(jié)構(gòu)的schema設(shè)計(jì)方案：一種是直觀而簡(jiǎn)單的設(shè)計(jì)思路，另一種是基于左右值編碼的改進(jìn)方案。

一、基本數(shù)據(jù)

本文列舉了一個(gè)食品族譜的例子進(jìn)行講解，通過(guò)類別、顏色和品種組織食品，樹(shù)形結(jié)構(gòu)圖如下：

二、繼承關(guān)系驅(qū)動(dòng)的schema設(shè)計(jì)

對(duì)樹(shù)形結(jié)構(gòu)最直觀的分析莫過(guò)于節(jié)點(diǎn)之間的繼承關(guān)系上，通過(guò)顯示地描述某一節(jié)點(diǎn)的父節(jié)點(diǎn)，從而能夠建立二維的關(guān)系表，則這種方案的tree表結(jié)構(gòu)通常設(shè)計(jì)為：{node_id,parent_id}，上述數(shù)據(jù)可以描述為如下圖所示：

這種方案的優(yōu)點(diǎn)很明顯：設(shè)計(jì)和實(shí)現(xiàn)自然而然，非常直觀和方便。缺點(diǎn)當(dāng)然也是非常的突出：由于直接地記錄了節(jié)點(diǎn)之間的繼承關(guān)系，因此對(duì)tree的任何crud操作都將是低效的，這主要?dú)w根于頻繁的“遞歸”操作，遞歸過(guò)程不斷地訪問(wèn)數(shù)據(jù)庫(kù)，每次數(shù)據(jù)庫(kù)io都會(huì)有時(shí)間開(kāi)銷(xiāo)。當(dāng)然，這種方案并非沒(méi)有用武之地，在tree規(guī)模相對(duì)較小的情況下，我們可以借助于緩存機(jī)制來(lái)做優(yōu)化，將tree的信息載入內(nèi)存進(jìn)行處理，避免直接對(duì)數(shù)據(jù)庫(kù)io操作的性能開(kāi)銷(xiāo)。

三、基于左右值編碼的schema設(shè)計(jì)

在基于數(shù)據(jù)庫(kù)的一般應(yīng)用中，查詢的需求總要大于刪除和修改。為了避免對(duì)于樹(shù)形結(jié)構(gòu)查詢時(shí)的“遞歸”過(guò)程，基于tree的前序遍歷設(shè)計(jì)一種全新的無(wú)遞歸查詢、無(wú)限分組的左右值編碼方案，來(lái)保存該樹(shù)的數(shù)據(jù)。

第一次看見(jiàn)這種表結(jié)構(gòu)，相信大部分人都不清楚左值（lft）和右值（rgt）是如何計(jì)算出來(lái)的，而且這種表設(shè)計(jì)似乎并沒(méi)有保存父子節(jié)點(diǎn)的繼承關(guān)系。但當(dāng)你用手指指著表中的數(shù)字從1數(shù)到18，你應(yīng)該會(huì)發(fā)現(xiàn)點(diǎn)什么吧。對(duì)，你手指移動(dòng)的順序就是對(duì)這棵樹(shù)進(jìn)行前序遍歷的順序，如下圖所示。當(dāng)我們從根節(jié)點(diǎn)food左側(cè)開(kāi)始，標(biāo)記為1，并沿前序遍歷的方向，依次在遍歷的路徑上標(biāo)注數(shù)字，最后我們回到了根節(jié)點(diǎn)food，并在右邊寫(xiě)上了18。

第一次看見(jiàn)這種表結(jié)構(gòu)，相信大部分人都不清楚左值（lft）和右值（rgt）是如何計(jì)算出來(lái)的，而且這種表設(shè)計(jì)似乎并沒(méi)有保存父子節(jié)點(diǎn)的繼承關(guān)系。但當(dāng)你用手指指著表中的數(shù)字從1數(shù)到18，你應(yīng)該會(huì)發(fā)現(xiàn)點(diǎn)什么吧。對(duì)，你手指移動(dòng)的順序就是對(duì)這棵樹(shù)進(jìn)行前序遍歷的順序，如下圖所示。當(dāng)我們從根節(jié)點(diǎn)food左側(cè)開(kāi)始，標(biāo)記為1，并沿前序遍歷的方向，依次在遍歷的路徑上標(biāo)注數(shù)字，最后我們回到了根節(jié)點(diǎn)food，并在右邊寫(xiě)上了18。

依據(jù)此設(shè)計(jì)，我們可以推斷出所有左值大于2，并且右值小于11的節(jié)點(diǎn)都是fruit的后續(xù)節(jié)點(diǎn)，整棵樹(shù)的結(jié)構(gòu)通過(guò)左值和右值存儲(chǔ)了下來(lái)。然而，這還不夠，我們的目的是能夠?qū)?shù)進(jìn)行crud操作，即需要構(gòu)造出與之配套的相關(guān)算法。

四、樹(shù)形結(jié)構(gòu)crud算法

（1）獲取某節(jié)點(diǎn)的子孫節(jié)點(diǎn)

只需要一條sql語(yǔ)句，即可返回該節(jié)點(diǎn)子孫節(jié)點(diǎn)的前序遍歷列表，以fruit為例：select* from tree where lft between 2 and 11 order by lft asc。查詢結(jié)果如下所示：

那么某個(gè)節(jié)點(diǎn)到底有多少的子孫節(jié)點(diǎn)呢？通過(guò)該節(jié)點(diǎn)的左、右值我們可以將其子孫節(jié)點(diǎn)圈進(jìn)來(lái)，則子孫總數(shù) = (右值 – 左值– 1) / 2，以fruit為例，其子孫總數(shù)為：(11 –2 – 1) / 2 = 4。同時(shí)，為了更為直觀地展現(xiàn)樹(shù)形結(jié)構(gòu)，我們需要知道節(jié)點(diǎn)在樹(shù)中所處的層次，通過(guò)左、右值的sql查詢即可實(shí)現(xiàn)，以fruit為例：selectcount(*) from tree where lft <= 2 and rgt >=11。為了方便描述，我們可以為tree建立一個(gè)視圖，添加一個(gè)層次數(shù)列，該列數(shù)值可以寫(xiě)一個(gè)自定義函數(shù)來(lái)計(jì)算，函數(shù)定義如下：

基于層次計(jì)算函數(shù)，我們創(chuàng)建一個(gè)視圖，添加了新的記錄節(jié)點(diǎn)層次的數(shù)列：

創(chuàng)建存儲(chǔ)過(guò)程，用于計(jì)算給定節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)及相應(yīng)的層次：

現(xiàn)在，我們使用上面的存儲(chǔ)過(guò)程來(lái)計(jì)算節(jié)點(diǎn)fruit所有子孫節(jié)點(diǎn)及對(duì)應(yīng)層次，查詢結(jié)果如下：

從上面的實(shí)現(xiàn)中，我們可以看出采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行樹(shù)的查詢遍歷時(shí)，只需要進(jìn)行2次數(shù)據(jù)庫(kù)查詢，消除了遞歸，再加上查詢條件都是數(shù)字的比較，查詢的效率是極高的，隨著樹(shù)規(guī)模的不斷擴(kuò)大，基于左右值編碼的設(shè)計(jì)方案將比傳統(tǒng)的遞歸方案查詢效率提高更多。當(dāng)然，前面我們只給出了一個(gè)簡(jiǎn)單的獲取節(jié)點(diǎn)子孫的算法，真正地使用這棵樹(shù)我們需要實(shí)現(xiàn)插入、刪除同層平移節(jié)點(diǎn)等功能。

 （2）獲取某節(jié)點(diǎn)的族譜路徑

    假定我們要獲得某節(jié)點(diǎn)的族譜路徑，則根據(jù)左、右值分析只需要一條sql語(yǔ)句即可完成，以fruit為例：select* from tree where lft < 2 and rgt > 11 order by lft asc ，相對(duì)完整的存儲(chǔ)過(guò)程：

（3）為某節(jié)點(diǎn)添加子孫節(jié)點(diǎn)

    假定我們要在節(jié)點(diǎn)“red”下添加一個(gè)新的子節(jié)點(diǎn)“apple”，該樹(shù)將變成如下圖所示，其中紅色節(jié)點(diǎn)為新增節(jié)點(diǎn)。

仔細(xì)觀察圖中節(jié)點(diǎn)左右值變化，相信大家都應(yīng)該能夠推斷出如何寫(xiě)sql腳本了吧。我們可以給出相對(duì)完整的插入子節(jié)點(diǎn)的存儲(chǔ)過(guò)程：

（4）刪除某節(jié)點(diǎn)

    如果我們想要?jiǎng)h除某個(gè)節(jié)點(diǎn)，會(huì)同時(shí)刪除該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，而這些被刪除的節(jié)點(diǎn)的個(gè)數(shù)為：(被刪除節(jié)點(diǎn)的右值 – 被刪除節(jié)點(diǎn)的左值+ 1) / 2，而剩下的節(jié)點(diǎn)左、右值在大于被刪除節(jié)點(diǎn)左、右值的情況下會(huì)進(jìn)行調(diào)整。來(lái)看看樹(shù)會(huì)發(fā)生什么變化，以beef為例，刪除效果如下圖所示。

則我們可以構(gòu)造出相應(yīng)的存儲(chǔ)過(guò)程：

五、總結(jié)

我們可以對(duì)這種通過(guò)左右值編碼實(shí)現(xiàn)無(wú)限分組的樹(shù)形結(jié)構(gòu)schema設(shè)計(jì)方案做一個(gè)總結(jié)：

    （1）優(yōu)點(diǎn)：在消除了遞歸操作的前提下實(shí)現(xiàn)了無(wú)限分組，而且查詢條件是基于整形數(shù)字的比較，效率很高。

    （2）缺點(diǎn)：節(jié)點(diǎn)的添加、刪除及修改代價(jià)較大，將會(huì)涉及到表中多方面數(shù)據(jù)的改動(dòng)。

當(dāng)然，本文只給出了幾種比較常見(jiàn)的crud算法的實(shí)現(xiàn)，我們同樣可以自己添加諸如同層節(jié)點(diǎn)平移、節(jié)點(diǎn)下移、節(jié)點(diǎn)上移等操作。有興趣的朋友可以自己動(dòng)手編碼實(shí)現(xiàn)一下，這里不在列舉了。值得注意的是，實(shí)現(xiàn)這些算法可能會(huì)比較麻煩，會(huì)涉及到很多條update語(yǔ)句的順序執(zhí)行，如果順序調(diào)度考慮不周詳，出現(xiàn)bug的話將會(huì)對(duì)整個(gè)樹(shù)形結(jié)構(gòu)表產(chǎn)生驚人的破壞。因此，在對(duì)樹(shù)形結(jié)構(gòu)進(jìn)行大規(guī)模修改的時(shí)候，可以采用臨時(shí)表做中介，以降低代碼的復(fù)雜度，同時(shí)，強(qiáng)烈推薦在做修改之前對(duì)表進(jìn)行完整備份，以備不時(shí)之需。在以查詢?yōu)橹鞯慕^大多數(shù)基于數(shù)據(jù)庫(kù)的應(yīng)用系統(tǒng)中，該方案相比傳統(tǒng)的由父子繼承關(guān)系構(gòu)建的數(shù)據(jù)庫(kù)schema更為適用。

到此這篇關(guān)于樹(shù)形結(jié)構(gòu)數(shù)據(jù)庫(kù)表schema設(shè)計(jì)方案的文章就介紹到這了,更多相關(guān)樹(shù)形結(jié)構(gòu)數(shù)據(jù)庫(kù)表schema設(shè)計(jì)內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

參考文獻(xiàn)：《storing hierarchical data in a database article》

原文鏈接：https://blog.csdn.net/monkey_d_meng/article/details/6647488