在數據庫中存儲層級結構 - 殘陽似血的博客

在數據庫中存儲層級結構

位于分類 技巧集錦

本文參考自 這篇文章 。文章是2003年的，但是現在來看仍然有著實際意義。

層級結構，也叫樹形結構。在實際應用中，你經常需要保存層級結構到數據庫中。比如說：你的網站上的目錄。不過，除非使用類XML的數據庫，通用的關系數據庫很難做到這點。

對于樹形數據的存儲有很多種方案。主要的方法有兩種：鄰接表模型，以及修改過的前序遍歷算法。本文將會討論這兩種方法的實現。這里的例子沿用參考文章中的例子，原文使用的PHP，這里將會用Java替代。（本例使用Mysql數據庫，Java如何連接Mysql，見備注一。）文中使用虛擬的在線食品商店作例子。這個食品商店通過類別、顏色以及種類來來組織它的食品。如圖所示：

1）首先是鄰接表模型。

鄰接表相當簡單。只需要寫一個遞歸函數來遍歷這個樹。我們的食品商店的例子用鄰接表模型存儲時看起來就像是這樣：

通過鄰接表模型存儲法中，我們可以看到Pear，它的父節點是Green，而Green的父節點又是Fruit，以此類推。而根節點是沒有父節點的。這里為了方便觀看，parent字段使用的字符串，實際應用中只要使用每個節點的ID即可。

現在已經在數據庫中插入完畢數據，接下來開始先顯示這棵樹。

打印這棵樹：

這里我們只需要寫一個簡單的遞歸函數就可以實現。打印某節點時，如果該節點有子節點就打印其子節點。源代碼如下：

?

1 2 3 4 5 6 7 8 9 10 11 12

public static void displayTree( int parentId, int level) ???? throws SQLException { ???? 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 ); ???? } }

要打印整棵樹，我們只要運行代碼：

?

1	displayTree( 0 , 0 );

這個函數打印出以下結果：

                Food
      Fruit
        Green
          Pear
        Red
          Cherry
        Yellow
          Banana
      Meat
        Beef
        Pork

          

求節點的路徑

有時候我們需要知道某個節點所在的路徑。舉例來說，“Cherry”所在的路徑為Food > Fruit > Red > Cherry。在這里，我們可以從Cherry開始查起，然后遞歸查詢查詢節點前的節點，直到某節點的父節點ID為0。源代碼如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public static List<String> getPath( int id) ???? throws SQLException{ ???? List<String> paths = new ArrayList<String>(); ???? setUp(); ???? ResultSet result = dbc.query( ???????? "SELECT parentid, title FROM `adjacency_list` WHERE ID=" ???????? + id); ???? result.next(); ???? int parentid = result.getInt( "parentid" ); ???? if (parentid != 0 ){ ???????? paths.addAll(getPath(parentid)); ???? } ???? paths.add(result.getString( "title" )); ???? return paths; }

我們用以下代碼來打印結果：

?

1 2 3 4 5 6

List<String> paths = getPath( 6 ); int i = 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語句就像這樣：

?

1	SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

返回結果如下：

有時候，如果進行過增、刪的操作，表中的數據可能就不是正確的順序。沒問題，只要使用“ORDER BY”語句就可以了，就像這樣：

?

1	SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC ;

現在唯一的問題是縮進問題。

正如我們面對樹的問題常常會想到的方案——棧。這里，我們可以維護一個只保存右數的棧。當當前節點的右數值大于棧頂元素的值（說明棧頂元素的子樹都以遍歷完畢），這個時候彈出棧頂值。再循環檢查棧頂值，直到棧頂值小于當前查詢節點的右數值。這個時候只要檢查棧中元素，有多少個元素說明當前查詢節點有多少個祖先節點（設為n）。只需要打印n個空格即可。代碼如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public static void displayTree(String root) throws SQLException{ ???? setUp(); ???? ResultSet result = dbc.query( "SELECT lft, rgt " ???????? + "FROM `modified_preorder_travesal` WHERE title='" ???????? + root + "';" ); ???? result.next(); ???????? ? ???? Stack<Integer> right = new Stack<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查詢：

?

1	SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC ;

這里同樣別忘了添加“ORDER BY”語句。執行以后返回結果：

求有多少子孫：

已知某節點的左數和右數，它的子孫的求法也就相當簡單了，用如下方法：

descendants?=?(right - left?-?1)?/?2?

自動生成表：

這兒的自動生成表指的是：如何把一個表從鄰接表模型轉換成修改過的前序遍歷模型。我們在開始的臨界表上增加"lft“和”rgt“字段。執行以下代碼，完成轉換：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public static int rebuildTree( int parentId, int left) throws SQLException { ???? setUp(); ???????? ? ???? int right = 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 + "';" ); ???????? ? ???? return right + 1 ; }

開始執行只要運行以下代碼：

?

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語句：

?

1 2	UPDATE tree SET rgt=rgt+2 WHERE rgt>5; UPDATE tree SET lft=lft+2 WHERE lft>5;

現在我們可以添加“Strawberry”到“Red”下，其左數為6、右數為7。

?

1	INSERT INTO tree SET lft=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命令。

連接數據庫的參考代碼：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

import java.io.*; import java.sql.*; import java.util.*; ? public class DBConnection { ???? private String driver = null ; ???? private String url = null ; ???? private String username = null ; ???? private String password = null ; ???? private Connection con = null ; ???? ? ???? public DBConnection(){ ???????? this .driver = "org.gjt.mm.mysql.Driver" ; ???????? this .url = "jdbc: mysql://localhost:3306/Tree " ; ???????? this .username = "root" ; ???????? this .password = "" ; ???? } ???? ? ???? public DBConnection(String driver, String url, String username, String password){ ???????? this .driver = driver; ???????? this .url = url; ???????? this .username = username; ???????? this .password = password; ???? } ???? ? ???? public Connection 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(); ???????? } ???????? return con; ???? } ???? ? ???? public void closeConnection(){ ???????? try { ???????????? con.close(); ???????? } ???????? catch (SQLException sqle){ ???????????? sqle.printStackTrace(); ???????????? ? ???????? } ???? } ???? ? ???? public static void main(String[] args){ ???????? DBConnection dbc = new DBConnection(); ???????? dbc.makeConnection(); ???????? dbc.closeConnection(); ???? } }

分享到

四月 16

文章信息

• Chine
• 12:13 p.m.
• 4個評論
• 持久連接

標簽

• Mysql
• 前序遍歷

4條留言

1. xdyl 說：
   2011年 八月22日 4:46 p.m.

   樹的增刪改查會導致整個編碼都更新吧.
   
   

   回復
   • @秦續業 說：
     2011年 八月22日 5:58 p.m.

     這也是前序遍歷算法的問題，增或者刪需要改動非常多的數據，也就是在對數據的處理上需要花費較多的時間。因此，在查詢上花費的時間就相對少了。

     回復
2. xdyl 說：
   2011年 八月25日 1:51 p.m.

   所以很難在項目中應用.
   
   

   回復
   • 胡驪Fox 說：
     2012年 十二月18日 2:01 p.m.

     兩種方法都在項目中使用過，由于都是小項目，所以對比效果不明顯。比較折中的辦法，是保存所有父節點id來組成TreeCode，當然，這樣的話也只能應付小項目

     回復

在數據庫中存儲層級結構