937
[數據庫]數據庫存儲層級結構數據
無論你想建立自己的論壇,在你的網站上從一個郵件列表發布消息,或編寫自己的cms:你將會遇到一種情況：將分層數據（層級結構）存儲在數據庫中。除非你使用一個類似xml的數據庫,通用的關係型數據庫是很難做到這一點。關係型數據庫中的表不分層;他們隻是一個簡單列表。你必須找到一個方法來把層次結構數據轉換為一個簡單文件數據。
存儲樹是一種常見的問題,可以有多個解決方案來實現。有兩種主要方法:鄰接表模型和修改後的樹前序遍曆的算法。
在本文中,我們將探討這兩種方法來存儲層級結構數據。我將使用從一個虛構的在線食品商店虛擬的這棵樹為例。這個食品商店通過類別、顏色以及種類來來組織它的食品。
這顆樹如下：
這篇文章包含一些代碼示例展示了如何保存和檢索數據。原文是使用的PHP，在這我將使用java來演示它的代碼展示。
[一] 鄰接列表模型
我們最先嚐試或者最優雅的方式我們稱為“鄰接表模式”或者我們稱它為“遞歸方法”。
這是一種優雅的方法,因為你隻需要一個簡單的函數就可以遍曆樹。在我們的食品商店的例子中,鄰接表的表可以這樣表示：
如您所見,在鄰接表的方法,你隻保存每個節點的父節點。我們可以從表上清楚的看到,“Pear”是“Green”的一個孩子，同時“Green”又是'Fruit'的孩子。
根節點“Food”沒有父節點。為簡單起見,我使用了“標題”值來確定每個節點。當然,在一個真正的數據庫,可以使用id來標示。
Give Me the Tree
既然我們已經在數據庫中插入我們的樹,是時候寫一個顯示功能。這個函數將不得不從根節點（沒有父節點）開始，應該顯示所有該節點的孩子。對於這些孩子節點來說,這個函數應該檢索和顯示這些孩子節點的所有子節點。然後在顯示這些孩子節點的子節點，遞歸的進行。
public void DisplayTree(int parentId,int level){
String sql = "select NodeId,NodeName,ParentId from Tree where parent-");
}
System.out.println(rs.getString("NodeName"));
DisplayTree(rs.getInt("NodeId"),level+1);
}
} catch (SQLException e) {
e.printStackTrace();
}
}
注：sqlManager類是數據庫操作類。
數據庫存儲的數據：
DisplayTree(0,0)
結果：
如果你隻是想看到一個子樹,你可以告訴函數這個開始節點的Id即可。
例如,顯示“Fruit”子樹,運行DisplayTree(2,0);
The Path to a Node
有時候我們需要知道某個節點所在的路徑。舉例來說，“Cherry”所在的路徑為Food > Fruit > Red > Cherry。在這裏，我們可以從Cherry開始查起，然後遞歸查詢查詢節點前的節點，直到某節點的父節點ID為0。
//獲取某個節點所在路徑
public ArrayList<String> GetPath(int nodeId){
String sql = "select ParentId,NodeName from Tree where NodeId = "+nodeId;
ArrayList<String> path = new ArrayList<String>();
try {
conn = sqlManager.GetConn();
statement = conn.createStatement();
ResultSet rs = statement.executeQuery(sql);
rs.next();
int parentId = rs.getInt("ParentId");
String nodeName = rs.getString("NodeName");
if(parentId != 0){
path.addAll(GetPath(parentId));
}
path.add(nodeName);
} catch (SQLException e) {
e.printStackTrace();
}
return path;
}
ArrayList<String> path = main.GetPath(9);
int index = 0;
for (String node : path) {
if(index != 0){
System.out.print("->");
}
System.out.print(node);
index++;
}
優缺點
我們可以看到，用鄰接表模型確實是個不錯的方法。它簡單易懂，而且實現的代碼寫起來也很容易。那麼，缺點是什麼呢？那就是，在大多數語言中，鄰接表模型執行起來效率低下和緩慢。這主要是由於遞歸引起的，我們查詢樹中的每個節點的時候都需要進行依次數據庫查詢。因為每個查詢需要一些時間,這使得函數非常緩慢的在處理大樹時。
第二個原因是在你可能使用的編程語言這個方法不是那麼快,。對於一門程序語言來說，除了Lisp這種，大多數不是為了遞歸而設計。當一個節點深度為4時，它得同時生成4個函數實例，它們都需要花費時間、占用一定的內存空間。所以，鄰接表模型效率的低下可想而知。
[二] 樹前序遍曆的算法變形
那麼就讓我們來看另外一種存儲樹形結構的方法。如之前所講，我們希望能夠減少查詢的數量，最好是隻做到查詢一次數據庫。
現在我們把樹“橫”著放。如下圖所示，我們首先從根節點（“Food”）開始，先在它左側標記“1”，然後我們到“Fruit”，左側標記“2”，接著按照前序遍曆的順序遍曆完樹，依次在每個節點的左右側標記數字。最後一個數字寫在“Food”節點右邊的。在這張圖片裏,你可以看到用數字標記的整個樹和幾個箭頭指示編號順序。
我們叫這些數字為Left和Right(例如“Food”的Left值是1,Right值是18)。正如你所看到的,這些數字表示每個節點之間的關係。
比如，“Red”節點左邊的數為3、右邊的數為6，它是Food（1-18）的後代。同樣的，我們可以注意到，左數大於2、右數小於11的節點都是“Fruit”的子孫。現在，所有的節點將以左數-右數的方式存儲，這種通過遍曆一個樹、然後給每一個節點標注左數、右數的方式稱為修改過的前序遍曆算法。
在我們繼續之前,讓我們來看看在我們的表的這些值:
注意,“Left”和“Right”在SQL中有特殊的意義。因此,我們必須使用“lft”和“rgt”標識列。還要注意,我們並不真的需要“parent”列了。我們現在有lft和rgt值存儲樹結構。
Retrieve the Tree
SELECT * FROM FoodTree WHERE Lft BETWEEN 2 AND 11;
注：FoodTree是存儲數據的表
返回：
整個樹隻需要一次查詢。
顯示這棵樹就像我們做遞歸函數,我們將不得不ORDER BY子句添加到查詢語句中。如果你從你的表添加和刪除行,你的表可能不會以正確的順序存儲。我們應該按左值進行排序。
SELECT * FROM FoodTree WHERE Lft BETWEEN 2 AND 11 ORDER BY Lft ASC;
現在唯一的問題是縮進問題。
顯示樹結構,孩子應該縮進略高於他們的父母。這裏，我們可以維護一個隻保存右數的棧。每次你從一個節點的孩子節點開始,你將該節點的Rgt值添加到堆棧中。我們知道該節點所有的孩子的Rgt值小於父節點的Rgt值,所以通過比較當前節點的Rgt值和堆棧中最後一個節點的Rgt值。當當前節點的Rgt值大於棧頂元素的值（說明棧頂元素的子樹都以遍曆完畢），這個時候彈出棧頂值。再循環檢查棧頂值，直到棧頂值小於當前查詢節點的Rgt值。這個時候隻要檢查棧中元素，有多少個元素說明當前查詢節點有多少個祖先節點代碼如下：
public void DisplayTree2(String nodeName) {
String sql = "select Lft,Rgt from FoodTree where NodeName ='" + nodeName+"'";
conn = sqlManager.GetConn();
Stack<Integer> RgtStack = new Stack<Integer>();
try {
statement = conn.createStatement();
ResultSet rs = statement.executeQuery(sql);
rs.next();
int lft = rs.getInt("Lft");
int rgt = rs.getInt("Rgt");
sql = "select NodeName,Lft,Rgt from FoodTree where Lft between "+lft+" and "+rgt +" order by Lft asc";
statement = conn.createStatement();
ResultSet rs2 = statement.executeQuery(sql);
while (rs2.next()) {
int rightValue = rs2.getInt("Rgt");
if(RgtStack.size() > 0){
//棧頂元素
int cur = RgtStack.peek();
while(cur < rightValue){
RgtStack.pop();
if(RgtStack.size() > 0){
cur = RgtStack.peek();
}
else{
break;
}
}
}
for(int i = 0;i < RgtStack.size()*2;i++){
System.out.print("-");
}
System.out.println(rs2.getString("NodeName"));
RgtStack.push(rightValue);
}
} catch (SQLException e) {
e.printStackTrace();
}
}
運行代碼，打印結果和之前鄰接表模型打印的結果一樣。但是新方法更快，原因就是：沒有遞歸，且一共隻使用兩次查詢。
The Path to a Node
使用這種新算法,我們還將必須找到一種新的方式去找到一個特定節點的路徑。這條路徑,我們將需要一個列表來保存所有祖先節點。
例如,當你看4 - 5“Cherry”節點,您將看到所有的祖先節點都是左值小於4,右值大於5。得到所有的祖先,我們可以使用這個查詢:
SELECT NodeName,Lft,Rgt FROM FoodTree WHERE Lft < 4 AND Rgt > 5 ORDER BY Lft ASC;
+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+How Many Descendants
如果你給我一個節點的左和右值,我可以利用數學公式告訴你有多少子節點。
descendants = (right - left - 1) / 2
這個簡單的公式,我可以告訴你,2 - 11“Fruit”節點有4個子節點,8 - 9“Banana”節點沒有子節點。
Automating the Tree Traversal
這兒的自動生成表指的是：如何把一個表從鄰接表模型轉換成修改過的前序遍曆模型。我們在開始的臨界表上增加"lft“和”rgt“字段。執行以下代碼，完成轉換：
//鄰接表模型轉換為修改後前序遍曆遍曆算法模型
public int RebuildTree(int parentId,int lft){
int rgt = lft + 1;
String sql = "select NodeId,NodeName from AdjTree where ParentId=" + parentId;
conn = sqlManager.GetConn();
try {
statement = conn.createStatement();
ResultSet rs = statement.executeQuery(sql);
while(rs.next()){
rgt = RebuildTree(rs.getInt("NodeId"), rgt);
}
sql = "update AdjTree set Lft = "+lft+", Rgt = "+rgt + " where NodeId = "+parentId;
statement = conn.createStatement();
statement.executeUpdate(sql);
return rgt + 1;
} catch (SQLException e) {
e.printStackTrace();
return 0;
}
}
結果：
我們所寫的運行函數是一個遞歸函數。對於某一節點，如果其沒有子孫節點，那麼他的右數值等於左數值+1；如果有那麼返回其子樹右數值+1。這個函數稍微有點複雜，不過梳理通了以後就不難理解。
這個函數將會從根節點開始遍曆整個樹。運行了可以發現和我們之前手動所建的表一樣。這裏有個快速檢查的方法：那就是檢查根節點的右數值，如果它等於節點總數的2倍，那就是正確的。
Adding a Node
我們如何將一個節點添加到樹中?這裏有兩種方法:（1）你可以在你的表中保存父節點字段‘ParentId’並重新運行RebuildTree()函數。這是一個簡單但是效率不高的方法;
你可以使用鄰接表的方法進行更新和修改後的前序遍曆樹算法進行檢索。如果你想添加一個新節點,您就將其添加到表並設置父節點。然後,隻需重新運行RebuildTree()函數就可以了。對一個大樹來說這是一個很容易,但不是非常高效方法。
（2）第二種方法為添加、刪除節點時更新新插入節點右邊所有節點的左值和右值。讓我們來看一個例子。我們想添加“Strawberry“到”Red“節點下，那麼“Red”節點的右數就得從6到8，而“Yellow”就得從7-10變成9-12，以此類推。更新Red節點就意味著大於5的左數和右數都要增加2。
UPDATE FoodTree SET Rgt = Rgt+2 WHERE Rgt > 5; UPDATE FoodTree SET Lft = Lft+2 WHERE Lft > 5;
現在我們可以添加一個新的節點“Strawberry”來填補新騰出的空間。這個節點左值為6和右值為7。
INSERT INTO FoodTree (Lft,Rgt,NodeName)values(6,7,'Strawberry');
如果我們運行DisplayTree2()函數,我們將看到新的“Strawberry”節點已經成功插入到樹:
Food
--Fruit
----Red
------Cherry
------Strawberry
----Yellow
------Banana
--Meet
----Beef
----Pork
Disadvantages
首先，修改過的前序遍曆算法似乎更難理解。但是它有著鄰接表模型無法比擬的速度優勢，雖然，在增或著刪數據的時候步驟多了些，但是，查詢的時候隻需要一條SQL語句。不過，這裏我要提醒，當使用前序遍曆算法存儲樹的時候，要注意臨界區問題，就是在增或者刪的時候，不要出現其他的數據庫操作。
注：SqlManager類
package com.sql;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
public class SqlManager {
private String SqlConectionString = "com.microsoft.sqlserver.jdbc.SQLServerDriver";
private String ip = "localhost";
private String databaseName = "SJF";
private String user = "sa";
private String password = "123";
private String url = null;
private Connection conn = null;
public SqlManager(){
//加載驅動
try {
Class.forName(SqlConectionString);
} catch (ClassNotFoundException e) {
e.printStackTrace();
System.out.println("加載數據庫驅動失敗:\n"+e.getMessage());
}
url = "jdbc:sqlserver://" + ip + ":1433;DatabaseName="+databaseName+";";
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
public Connection GetConn(){
try {
conn = DriverManager.getConnection(url, user, password);
} catch (SQLException e) {
e.printStackTrace();
}
return conn;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//關閉
public void CloseConn(){
try {
conn.close();
} catch (SQLException e) {
e.printStackTrace();
}
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
}
最後更新：2017-04-03 08:26:24