在數據庫中存儲層級結構
位于分類 技巧集錦
本文參考自 這篇文章 。文章是2003年的，但是現在來看仍然有著實際意義。
層級結構，也叫樹形結構。在實際應用中，你經常需要保存層級結構到數據庫中。比如說：你的網站上的目錄。不過，除非使用類XML的數據庫，通用的關系數據庫很難做到這點。
對于樹形數據的存儲有很多種方案。主要的方法有兩種：鄰接表模型，以及修改過的前序遍歷算法。本文將會討論這兩種方法的實現。這里的例子沿用參考文章中的例子，原文使用的PHP，這里將會用Java替代。（本例使用Mysql數據庫，Java如何連接Mysql，見備注一。）文中使用虛擬的在線食品商店作例子。這個食品商店通過類別、顏色以及種類來來組織它的食品。如圖所示：
1）首先是鄰接表模型。
鄰接表相當簡單。只需要寫一個遞歸函數來遍歷這個樹。我們的食品商店的例子用鄰接表模型存儲時看起來就像是這樣：
通過鄰接表模型存儲法中，我們可以看到Pear，它的父節點是Green，而Green的父節點又是Fruit，以此類推。而根節點是沒有父節點的。這里為了方便觀看，parent字段使用的字符串，實際應用中只要使用每個節點的ID即可。
現在已經在數據庫中插入完畢數據，接下來開始先顯示這棵樹。
打印這棵樹：
這里我們只需要寫一個簡單的遞歸函數就可以實現。打印某節點時，如果該節點有子節點就打印其子節點。源代碼如下：
publicstaticvoiddisplayTree(intparentId,intlevel)????throwsSQLException {????setUp();????ResultSet result = dbc.query(????????"SELECT ID, title FROM `adjacency_list` WHERE parentid="????????+ parentId);????while(result.next()){????????System.out.println(repeatStr("? ", level)????????????+ result.getString("title"));????????displayTree(result.getInt("ID"), level+1);????}}要打印整棵樹，我們只要運行代碼：
displayTree(0,0);這個函數打印出以下結果：
Food Fruit Green Pear Red Cherry Yellow Banana Meat Beef Pork求節點的路徑
有時候我們需要知道某個節點所在的路徑。舉例來說，“Cherry”所在的路徑為Food > Fruit > Red > Cherry。在這里，我們可以從Cherry開始查起，然后遞歸查詢查詢節點前的節點，直到某節點的父節點ID為0。源代碼如下：
publicstaticList<String> getPath(intid)????throwsSQLException{????List<String> paths =newArrayList<String>();????setUp();????ResultSet result = dbc.query(????????"SELECT parentid, title FROM `adjacency_list` WHERE ID="????????+ id);????result.next();????intparentid = result.getInt("parentid");????if(parentid !=0){????????paths.addAll(getPath(parentid));????}????paths.add(result.getString("title"));????returnpaths;}我們用以下代碼來打印結果：
List<String> paths = getPath(6);inti =0;for(String path: paths){????System.out.println("["+ String.valueOf(i) +"] ==> "+ path);????i++;}得到以下結果：
[0] ==> Food [1] ==> Fruit [2] ==> Red [3] ==> Cherry缺點
我們可以看到，用鄰接表模型確實是個不錯的方法。它簡單易懂，而且實現的代碼寫起來也很容易。那么，缺點是什么呢？那就是，鄰接表模型執行起來效率低下。我們對于每個結果，期望只需要一次查詢；可是當使用鄰接表模型時嵌套的遞歸使用了多次查詢，當樹很大的時候，這種慢就會表現得尤為明顯。另外，對于一門程序語言來說，除了Lisp這種，大多數不是為了遞歸而設計。當一個節點深度為4時，它得同時生成4個函數實例，它們都需要花費時間、占用一定的內存空間。所以，鄰接表模型效率的低下可想而知。
就像在程序世界經常遇到的一樣。上帝是公平的，當在執行時效率低下，意味著可以增加預處理的程度。那么就讓我們來看另外一種存儲樹形結構的方法。如之前所講，我們希望能夠減少查詢的數量，最好是只做到查詢一次數據庫。
先來講解一下原理。現在我們把樹“橫”著放。如下圖所示，我們首先從根節點（“Food”）開始，先在它左側標記“1”，然后我們到“Fruit”，左側標記“2”，接著按照前序遍歷的順序遍歷完樹，依次在每個節點的左右側標記數字。
相信你也在圖中發現一些規律，沒錯。比如，“Red”節點左邊的數為3、右邊的數為6，它是Food（1-18）的后代。同樣的，我們可以注意到，左數大于2、右數小于11的節點都是“Fruit”的子孫。現在，所有的節點將以左數-右數的方式存儲，這種通過遍歷一個樹、然后給每一個節點標注左數、右數的方式稱為修改過的前序遍歷算法。
2）修改過的前序遍歷算法
在看完了介紹之后，我們要來討論具體的實現。在這之前，先來看一下，數據庫中表存儲這些數的情況。
在這種存儲方式中，我們實際上是不需要parent這個字段的。
打印樹：
如之前的介紹。如果要想打印樹，你只需要知道你要檢索的節點。比如，想要打印“Fruit”的子樹，可以查詢左數大于2而小于11的節點。SQL語句就像這樣：
SELECT*FROMtreeWHERElftBETWEEN2AND11;返回結果如下：
有時候，如果進行過增、刪的操作，表中的數據可能就不是正確的順序。沒問題，只要使用“ORDER BY”語句就可以了，就像這樣：
SELECT*FROMtreeWHERElftBETWEEN2AND11ORDERBYlftASC;現在唯一的問題是縮進問題。
正如我們面對樹的問題常常會想到的方案——棧。這里，我們可以維護一個只保存右數的棧。當當前節點的右數值大于棧頂元素的值（說明棧頂元素的子樹都以遍歷完畢），這個時候彈出棧頂值。再循環檢查棧頂值，直到棧頂值小于當前查詢節點的右數值。這個時候只要檢查棧中元素，有多少個元素說明當前查詢節點有多少個祖先節點（設為n）。只需要打印n個空格即可。代碼如下：
publicstaticvoiddisplayTree(String root)throwsSQLException{????setUp();????ResultSet result = dbc.query("SELECT lft, rgt "????????+"FROM `modified_preorder_travesal` WHERE title='"????????+ root +"';");????result.next();?????????????Stack<Integer> right =newStack<Integer>();?????????????result = dbc.query("SELECT title, lft, rgt "????????+"FROM `modified_preorder_travesal`"????????+" WHERE lft BETWEEN "????????+ String.valueOf(result.getInt("lft"))????????+" AND "????????+ String.valueOf(result.getInt("rgt"))????????+" ORDER BY lft ASC;");?????????????while(result.next()){????????if(right.size() >0){????????????Integer current = right.peek();????????????while(current < result.getInt("rgt")){????????????????right.pop();????????????????current = right.peek();????????????}????????}?????????????????????System.out.println(repeatStr("? ", right.size())????????????+ result.getString("title"));?????????????????????right.push(result.getInt("rgt"));????}}運行代碼，打印結果和之前鄰接表模型打印的結果一樣。但是新方法更快，原因就是：沒有遞歸，且一共只使用兩次查詢。
求節點的路徑：
在修改過的前序遍歷算法的實現中，我們同樣需要求節點的路徑。不過這不是很困難，對于某節點，我們只需求出左數值小于其左數值、右數大于其右數的所有節點。比如說“Cherry”這個節點（4-5），我們可以這么寫SQL查詢：
SELECTtitleFROMtreeWHERElft < 4ANDrgt > 5ORDERBYlftASC;這里同樣別忘了添加“ORDER BY”語句。執行以后返回結果：
求有多少子孫：
已知某節點的左數和右數，它的子孫的求法也就相當簡單了，用如下方法：
descendants?=?(right - left?-?1)?/?2?
自動生成表：
這兒的自動生成表指的是：如何把一個表從鄰接表模型轉換成修改過的前序遍歷模型。我們在開始的臨界表上增加"lft“和”rgt“字段。執行以下代碼，完成轉換：
publicstaticintrebuildTree(intparentId,intleft)throwsSQLException {????setUp();?????????????intright = left +1;?????????????ResultSet result = dbc.query("SELECT ID, title FROM `adjacency_list` WHERE "????????+"parentid="+ parentId);?????????????while(result.next()){????????right = rebuildTree(result.getInt("ID"), right);????}?????????????dbc.update("UPDATE `adjacency_list` SET lft="+ String.valueOf(left)????????+", rgt="+ String.valueOf(right)????????+" WHERE ID='"+ parentId +"';");?????????????returnright +1;}開始執行只要運行以下代碼：
rebuildTree(1,1);我們所寫的運行函數是一個遞歸函數。對于某一節點，如果其沒有子孫節點，那么他的右數值等于左數值+1；如果有那么返回其子樹右數值+1。這個函數稍微有點復雜，不過梳理通了以后就不難理解。
這個函數將會從根節點開始遍歷整個樹。運行了可以發現和我們之前手動所建的表一樣。這里有個快速檢查的方法：那就是檢查根節點的右數值，如果它等于節點總數的2倍，那就是正確的。
增加節點：
增加節點有兩種方法：1）保留parentid字段，當增加節點后，運行一遍“rebuildTree”方法。這么做看起來很簡單，不過你應該知道，這么做效率低下，尤其是大樹時。那么第二種方法呢？2）首先我們得為添加的節點騰出空間。比如，我們想添加“Strawberry“到”Red“節點下，那么“Red”節點的右數就得從6到8，而“Yellow”就得從7-10變成9-12，以此類推。更新Red節點就意味著大于5的左數和右數都要增加2。
我們先運行以下SQL語句：
UPDATEtreeSETrgt=rgt+2WHERErgt>5;UPDATEtreeSETlft=lft+2WHERElft>5;現在我們可以添加“Strawberry”到“Red”下，其左數為6、右數為7。
INSERTINTOtreeSETlft=6, rgt=7, title='Strawberry';再次運行“displayTree”方法，會發現“Strawberry”已被添加其中。刪除節點有著差不多的步驟，這里就略去不提了。各位感興趣的話可以自己實現。
缺點：
首先，修改過的前序遍歷算法似乎更難理解。但是它有著鄰接表模型無法比擬的速度優勢，雖然，在增或著刪數據的時候步驟多了些，但是，查詢的時候只需要一條SQL語句。不過，這里我要提醒，當使用前序遍歷算法存儲樹的時候，要注意臨界區問題，就是在增或者刪的時候，不要出現其他的數據庫操作。
關于在數據庫中存儲層級數據的內容就講到這里。如果你使用的Python語言的Django框架，應該覺得慶幸。因為已經有開源插件幫你實現了。項目名字叫MPTT，主頁在 這里 。以后，我會對MPTT的用法以及源碼實現作詳細說明。在此之前，如果能力夠，參考 官方文檔 就可以了。
備注一：
各種數據庫的JDBC驅動連接方式及下載，見 這里 。Mysql下載的 快速鏈接 。
下載完解壓縮，把其中的mysql-connector-java-***-bin.jar（***為版本）文件拷貝至"yourjdkpath"/jre/lib/ext，我的路徑為：/usr/lib/jvm/java-6-openjdk/jre/lib/ext/。
這個文件夾是只讀的，修改權限用chmod命令。
連接數據庫的參考代碼：
importjava.io.*;importjava.sql.*;importjava.util.*;?publicclassDBConnection {????privateString driver =null;????privateString url =null;????privateString username =null;????privateString password =null;????privateConnection con =null;?????????publicDBConnection(){????????this.driver ="org.gjt.mm.mysql.Driver";????????this.username ="root";????????this.password ="";????}?????????publicDBConnection(String driver, String url, String username, String password){????????this.driver = driver;????????this.url = url;????????this.username = username;????????this.password = password;????}?????????publicConnection makeConnection(){????????con =null;????????try{????????????Class.forName(driver);????????????con = DriverManager.getConnection(url, username, password);????????????System.out.println("連接Mysql成功");????????}????????catch(SQLException sqle){????????????sqle.printStackTrace();????????}????????catch(ClassNotFoundException ex){????????????ex.printStackTrace();????????}????????returncon;????}?????????publicvoidcloseConnection(){????????try{????????????con.close();????????}????????catch(SQLException sqle){????????????sqle.printStackTrace();?????????????????????}????}?????????publicstaticvoidmain(String[] args){????????DBConnection dbc =newDBConnection();????????dbc.makeConnection();????????dbc.closeConnection();????}}四月 16
4條留言
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
2011年 八月22日 4:46 p.m.
樹的增刪改查會導致整個編碼都更新吧.
2011年 八月22日 5:58 p.m.
這也是前序遍歷算法的問題，增或者刪需要改動非常多的數據，也就是在對數據的處理上需要花費較多的時間。因此，在查詢上花費的時間就相對少了。
2011年 八月25日 1:51 p.m.
所以很難在項目中應用.
2012年 十二月18日 2:01 p.m.
兩種方法都在項目中使用過，由于都是小項目，所以對比效果不明顯。比較折中的辦法，是保存所有父節點id來組成TreeCode，當然，這樣的話也只能應付小項目